Posts tagged as “sum”

花花酱 LeetCode 1. Two Sum

By zxi on November 23, 2017

Problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Idea:

Brute force / Hashtable

Solution1:

Brute force / C++

Time complexity: O(n^2)

Space complexity: O(1)

// Author: Huahua

// Runtime: 166 ms

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

for (int i = 0; i < nums.size(); ++i) {

for (int j = i + 1;j < nums.size(); ++j) {

int sum = nums[i] + nums[j];

if (sum == target) {

return {i, j};

}

return {};

}

};

Solution 2:

Hashtable / C++

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> indies;

for (int i = 0; i < nums.size(); ++i)

indies[nums[i]] = i;

for (int i = 0; i < nums.size(); ++i) {

int left = target - nums[i];

if (indies.count(left) && indies[left] != i) {

return {i, indies[left]};

}

return {};

}

};

花花酱 LeetCode 216. Combination Sum III

By zxi on November 3, 2017

题目大意：输出所有用k个数的和为n的组合。可以使用的元素是1到9。

Problem:

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

1	[[1,2,6], [1,3,5], [2,3,4]]

Idea:

DFS + backtracking

bit

Solution:

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

vector<int> cur;

dfs(k, n, 1, cur, ans);

return ans;

}

private:

// Use k numbers (>= s) to sum up to n

void dfs(int k, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

if (k == 0) {

if (n == 0) ans.push_back(cur);

return;

}

for (int i = s; i <= 9; ++i) {

if (i > n) return;

cur.push_back(i);

dfs(k - 1, n - i, i + 1, cur, ans);

cur.pop_back();

}

};

C++ / binary

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

// 2^9, generate all combinations of [1 .. 9]

for (int i = 0; i < (1 << 9); ++i) {

vector<int> cur;

int sum = 0;

// Use j if (j - 1)-th bit is 1

for (int j = 1; j <= 9; ++j)

if (i & (1 << (j - 1))) {

sum += j;

cur.push_back(j);

}

if (sum == n && cur.size() == k)

ans.push_back(cur);

}

return ans;

}

};

Python

class Solution:

def combinationSum3(self, k, n):

def dfs(k, n, s, cur, ans):

if k == 0 and n == 0:

ans.append(list(cur))

for i in range(s, min(n + 1, 10)):

dfs(k - 1, n - i, i + 1, cur + [i], ans)

ans = []

dfs(k, n, 1, [], ans)

return ans

Related problems:

花花酱 LeetCode 40. Combination Sum II

By zxi on October 15, 2017

Problem:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[

[1, 7],

[1, 2, 5],

[2, 6],

[1, 1, 6]

]

Idea:

DFS

Solution:

C++ / set

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

set<vector<int>> ans;

std::sort(candidates.begin(), candidates.end());

vector<int> curr;

dfs(candidates, target, 0, ans, curr);

return vector<vector<int>>(ans.begin(), ans.end());

}

private:

void dfs(const vector<int>& candidates,

int target, int s,

set<vector<int>>& ans,

vector<int>& curr) {

if (target == 0) {

ans.insert(curr);

return;

}

for (int i = s; i < candidates.size(); ++i) {

int num = candidates[i];

if (num > target) return;

curr.push_back(num);

dfs(candidates, target - num, i + 1, ans, curr);

curr.pop_back();

}

};

C++ / vector

// Author: Huahua

// Runtime: 9ms

class Solution {

public:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

vector<vector<int>> ans;

std::sort(candidates.begin(), candidates.end());

vector<int> curr;

dfs(candidates, target, 0, ans, curr);

return ans;

}

private:

void dfs(const vector<int>& candidates,

int target, int s,

vector<vector<int>>& ans,

vector<int>& curr) {

if (target == 0) {

ans.push_back(curr);

return;

}

for (int i = s; i < candidates.size(); ++i) {

int num = candidates[i];

if (num > target) return;

if (i > s && candidates[i] == candidates[i - 1]) continue;

curr.push_back(num);

dfs(candidates, target - num, i + 1, ans, curr);

curr.pop_back();

}

};

花花酱 LeetCode 304. Range Sum Query 2D – Immutable

By zxi on September 18, 2017

https://leetcode.com/problems/range-sum-query-2d-immutable/description/

Problem:

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [

[3, 0, 1, 4, 2],

[5, 6, 3, 2, 1],

[1, 2, 0, 1, 5],

[4, 1, 0, 1, 7],

[1, 0, 3, 0, 5]

]

sumRegion(2, 1, 4, 3) : 8

sumRegion(1, 1, 2, 2) : 11

sumRegion(1, 2, 2, 4) : 12

Note:

You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

Idea:

Dynamic programming

Time complexity:

O(n^2)

sumRegion: O(1)

Solution:

// Author: Huahua

// Time complexity:

// constructor: O(n^2)

// sumRegion: O(1)

// Running time: 22 ms 9/2017

class NumMatrix {

public:

NumMatrix(const vector<vector<int>>& matrix) {

sums_.clear();

if (matrix.empty()) return;

int m = matrix.size();

int n = matrix[0].size();

// sums_[i][j] = sum(matrix[0][0] ~ matrix[i-1][j-1])

sums_ = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));

for (int i = 1; i <= m; ++i)

for (int j = 1; j <= n; ++j)

sums_[i][j] = matrix[i - 1][j - 1]

+ sums_[i - 1][j]

+ sums_[i][j - 1]

- sums_[i - 1][j - 1];

}

int sumRegion(int row1, int col1, int row2, int col2) {

return sums_[row2 + 1][col2 + 1]

- sums_[row2 + 1][col1]

- sums_[row1][col2 + 1]

+ sums_[row1][col1];

}

private:

vector<vector<int>> sums_;

};

/**

* Your NumMatrix object will be instantiated and called as such:

* NumMatrix obj = new NumMatrix(matrix);

* int param_1 = obj.sumRegion(row1,col1,row2,col2);

花花酱 LeetCode 221. Maximal Square

By zxi on September 18, 2017

Problem:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Idea:

Dynamic programming

Solution 0: O(n^5)

Solution 1: O(n^3)

Solution 2: O(n^2)

Solution 1:

// Author: Huahua

// Time complexity: O(n^3)

// Running time: 39 ms

class Solution {

public:

int maximalSquare(vector<vector<char>>& matrix) {

if (matrix.empty()) return 0;

int m = matrix.size();

int n = matrix[0].size();

// sums[i][j] = sum(matrix[0][0] ~ matrix[i-1][j-1])

vector<vector<int>> sums(m + 1, vector<int>(n + 1, 0));

for (int i = 1; i <= m; ++i)

for (int j = 1; j <= n; ++j)

sums[i][j] = matrix[i - 1][j - 1] - '0'

+ sums[i - 1][j]

+ sums[i][j - 1]

- sums[i - 1][j - 1];

int ans = 0;

for (int i = 1; i <= m; ++i)

for (int j = 1; j <= n; ++j)

for (int k = min(m - i + 1, n - j + 1); k > 0; --k) {

int sum = sums[i + k - 1][j + k - 1]

- sums[i + k - 1][j - 1]

- sums[i - 1][j + k - 1]

+ sums[i - 1][j - 1];

// full of 1

if (sum == k*k) {

ans = max(ans, sum);

break;

}

return ans;

}

};

Solution 2:

// Author: Huahua

// Time complexity: O(n^2)

// Running time: 6 ms

class Solution {

public:

int maximalSquare(vector<vector<char>>& matrix) {

if (matrix.empty()) return 0;

int m = matrix.size();

int n = matrix[0].size();

vector<vector<int>> sizes(m, vector<int>(n, 0));

int ans = 0;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

sizes[i][j] = matrix[i][j] - '0';

if (!sizes[i][j]) continue;

if (i == 0 || j == 0) {

// do nothing

} else if (i == 0)

sizes[i][j] = sizes[i][j - 1] + 1;

else if (j == 0)

sizes[i][j] = sizes[i - 1][j] + 1;

else

sizes[i][j] = min(min(sizes[i - 1][j - 1],

sizes[i - 1][j]),

sizes[i][j - 1]) + 1;

ans = max(ans, sizes[i][j]*sizes[i][j]);

}

return ans;

}

};