avatar

Leetcode-202009

77. Combinations-20200908

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints:

1 <= n <= 20
1 <= k <= n

首先想着用循环做… 刚开始刷题都没什么思想,想了想行不通,实际上这道题应该用回溯来做,第一个算法是看题解做的(TwT脑子还没转过来),第二个用的是离散树章的前缀码,数据结构中也有讲到,选择或者不选择,就可以组合出不重复的前缀码。

class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> ret;
if (n <= 0) {
return ret;
}
vector<int> cur;
// DFSSolve(ret, cur, n, k, 1);
DFSanother(ret, cur, 1, 0, n, k);

return ret;
}

void DFSSolve(vector<vector<int>> &ret, vector<int>cur, int n, int k, int level) {
if (cur.size() == k) {
ret.push_back(cur);
return;
}
if (cur.size() > k) {
return;
}

for (int i = level; i <= n; i++) {
cur.push_back(i);
DFSSolve(ret, cur, n, k, i+1);
cur.pop_back();
}
}

void DFSanother(vector<vector<int>> &ret, vector<int>&cur, int step, int selected, int n, int k) {
if (selected == k) {
ret.push_back(cur);
return;
}
if (step == n + 1) {
return;
}

DFSanother(ret, cur, step+1, selected, n, k); // not select
cur.push_back(step); // select
DFSanother(ret, cur, step+1, selected+1, n, k);
cur.pop_back();
}
};

第二个解法本来是有样例[20, 16]没有通过(tle),后来问了问dl发现是cur没有被引用,导致复制的时间边长了,加上引用就过了。

image-20200909201805608

33. Combination sum-20200909

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

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

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

Constraints:

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
Each element of candidate is unique.
1 <= target <= 500

这道题跟昨天的类似,一样用回溯,一开始写好了程序发现样例有[2,2,3]的重复,原因在第二层递归的时候重新把前面的元素加进去,导致了重复,只要添加一个begin变量,每次递归的时候从当前的idx开始循环(不是下一个,因为元素可以重复),添加后成功通过。

class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ret;
vector<int> cur;
int sum = 0;

D(ret, cur, candidates, candidates.size(), target, 0, sum);
return ret;

}

void D(vector<vector<int>> &ret, vector<int> &cur, vector<int> &candidates, int size, int target, int step, int &sum) {
if (sum == target) {
ret.push_back(cur);

return;
}
if (sum > target) {
return;
}


for (int i = step; i < size; i++) {
cur.push_back(candidates[i]);
sum+=candidates[i];
D(ret, cur, candidates, size, target, i, sum);
sum -= cur.back(); // backtracking
cur.pop_back();
}
}
};

也有逐个减去target的写法,就是sum和0的区别。

image-20200909202500458

40. Combination Sum II - 20200910

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

Each number in candidates 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.
Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]

这道题与昨天的区别在于candidates中会出现重复的数字而不能对某一index的元素重复选择,一开始我考虑用一个pend的布尔数组来做,但是写不出来,看了看题解,发现和昨天的区别不大,只是先对candidates进行排序,然后加上一个判定条件即可。

class Solution {
public:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ret;
vector<int> cur;
int sum = 0;
sort(candidates.begin(), candidates.end());// 先进行排序

D(ret, cur, candidates, candidates.size(), target, 0, sum);
return ret;

}

void D(vector<vector<int>> &ret, vector<int> &cur, vector<int> &candidates, int size, int target, int step, int &sum) {
if (sum == target) {
ret.push_back(cur);
return;
}
if (sum > target) {
return;
}

for (int i = step; i < size; i++) {
if (i>step && candidates[i-1] == candidates[i]) continue; // 相同的分支(在前一个元素的下一层),避免重复
cur.push_back(candidates[i]);
sum+=candidates[i];
D(ret, cur, candidates, size, target, i+1, sum);
sum -= cur.back();
cur.pop_back();
}
}
};

此外也可以通过hashmap来进行操作,先排序,然后建立一个candidates元素的数量map,像搭积木一样,从不加到加到能加的最大值。

class Solution
{
public:
vector<pair<int, int>> freq;
vector<vector<int>> ans;
vector<int> tmpqueue;

vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
{
sort(candidates.begin(), candidates.end());
for (int i : candidates)
{
if (freq.empty() || i != freq.back().first)
{
freq.emplace_back(i, 1);
}
else
{
freq.back().second++;
}
}
dfs(0, target);
return ans;
}

void dfs(int pos, int rest)
{
if (rest == 0)
{
ans.push_back(tmpqueue);
return;
}
if (pos == freq.size() || rest < freq[pos].first)
return;

dfs(pos + 1, rest); // pos处的数字没有被选择

int cnt = min(rest / freq[pos].first, freq[pos].second);
for (int i = 1; i <= cnt; i++)
{
tmpqueue.push_back(freq[pos].first);
dfs(pos + 1, rest - i * freq[pos].first);
}
for (int i = 0; i < cnt; i++)
tmpqueue.pop_back();
}
};

216. Combination Sum III - 20200911

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.

Note:

All numbers will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Example 2:

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

这道题还挺简单的,直接上代码应该能够直接看懂

class Solution {
public:
vector<vector<int>> ret;
vector<int> cur;

vector<vector<int>> combinationSum3(int k, int n) {
dfs(k, n, 1, 0);
return ret;
}

void dfs(int size, int rest, int step, int cnt) {
if (cnt == size && rest == 0) {
ret.push_back(cur);
return;
}
// two condition can't be switched, if rest == 0, it meets the 'rest < step' condition.
if (cnt > size || rest < step) {
return;
}
for (int i = step; i <= 9; i++) {
cur.push_back(i);
rest -= i;
dfs(size, rest, i+1, cnt+1);
cur.pop_back(); // backtrack
rest += i;
}
}
};

然后看题解。。。果然if判断还是比较耗时,减少一层,上方的12-19行代码换为

if (cnt >= size) {
if (cnt == size && rest == 0)
ret.push_back(cur);
return;
}
if(rest < step) {
return;
}

image-20200911234952856

0ms也太帅辣!

637. Average of Levels in Binary Tree - 20200912

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:

Input:

​ 3

/ \

9 20

​ / \

​ 15 7

Output: [3, 14.5, 11]

Explanation:
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Note:
The range of node’s value is in the range of 32-bit signed integer.

解法一:非递归BFS

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<double> ret;
queue<TreeNode*> nodeQueue;
double tmp;

vector<double> averageOfLevels(TreeNode* root) {
bfs(root);
return ret;
}

void bfs(TreeNode* root) {
int curCnt = 0, nextCnt = 0;
nodeQueue.push(root);
TreeNode* node;
curCnt = 1;
int cnt = 1;
while(!nodeQueue.empty()) {
node = nodeQueue.front();
nodeQueue.pop();
tmp+=node->val;
curCnt -= 1;
if (node->left){ nodeQueue.push(node->left);nextCnt+=1; }
if (node->right) {nodeQueue.push(node->right);nextCnt+=1; }
if (curCnt == 0) {
ret.push_back(tmp / cnt);
tmp=0;
cnt = curCnt = nextCnt;
nextCnt=0;
}
}
}
};

解法二:DFS

这个思路比较简单,就是遍历到所有的结点然后计算

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<double> ret;
vector<int> cntArr;
vector<pair<int, int>> nodes;
int cnt;

vector<double> averageOfLevels(TreeNode* root) {
dfs(root, 0);
ret = vector<double>(cnt+1, 0);
cntArr = vector<int>(cnt+1, 0);
for (int i = 0; i < nodes.size(); i++) {
ret[nodes[i].second] += nodes[i].first;
cntArr[nodes[i].second]++;
}
for (int i = 0; i <= cnt; i++) {
ret[i] /= cntArr[i];
}
return ret;
}

void dfs(TreeNode* root, int level) {
nodes.push_back({root->val, level});
if (cnt < level) { cnt = level; }
if (root->left) { dfs(root->left, level+1); }
if (root->right) { dfs(root->right, level+1); }
return;
}
}

image-20200912103053113

79. Word Search - 20200913

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]

Given word = “ABCCED”, return true.
Given word = “SEE”, return true.
Given word = “ABCB”, return false.

Constraints:

board and word consists only of lowercase and uppercase English letters.

1 <= board.length <= 200

1 <= board[i].length <= 200

1 <= word.length <= 10^3

过程中可以使用一个tmp来代替pend数组,然后就可以通过tmp回溯。

class Solution {
public:
int m, n;
int wordLen;
bool exist(vector<vector<char>>& board, string word) {
m = board.size();
n = board[0].size();
wordLen = word.length();
for (int i = 0;i<m;i++)
pend.push_back(vector<int>(n, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (recur(board, i, j, word, 0)) return true;
}
return false;
}

bool recur(vector<vector<char>> &board, int i, int j, string &word, int idx) {
if (i < 0 || i >= m || j < 0 || j >= n || word[idx] != board[i][j])
return false;

if (idx == wordLen-1)
return true;

char tmp = board[i][j]; // save tmp for backtracking
board[i][j]='!';
if (
(recur(board, i - 1, j, word, idx+1) ||
recur(board, i + 1, j, word, idx+1) ||
recur(board, i, j - 1, word, idx+1) ||
recur(board, i, j + 1, word, idx+1))
)
return true;
else {
board[i][j]=tmp;
return false;
}
}

};

94. Binary Tree Inorder Traversal - 20200914

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]

1

​ \

​ 2

​ /

3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

算是复习吧,非递归的不记得了还去翻代码了。。数据结构白给。

但有什么比下雨天喝咖啡刷题更棒的呢。

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> ret;

vector<int> inorderTraversal(TreeNode* root) {
traversal(root);
return ret;
}

// void recur(TreeNode* root) {

// if (!root)
// return;
// else {
// if (root->left) recur(root->left);
// ret.push_back(root->val);
// if (root->right) recur(root->right);
// }
// return;
// }

void traversal(TreeNode* root) {
if (!root) return;
TreeNode* node = root;
vector<TreeNode*> nodes;

while (!nodes.empty() || node) {
while (node) {
nodes.push_back(node);
node=node->left;
}
if (!nodes.empty()) {
node = nodes.back();
nodes.pop_back();
ret.push_back(node->val);
node=node->right;
}
}
}
};

image-20200914152845648

由于是学过的内容所以再来一道

377. Combination Sum IV - 20200914

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

有一个dp的解法,但是c++由于超范围了用不了

int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1, 0);
dp[0] = 1;
for (int i = 0; i <= target; i++)
for (int x: nums)
if (x <= i) {

dp[i] += dp[i-x];
// cout << "dp[" << i <<"] += dp[" << i-x << "] -- dp[" << i << "] is " << dp[i] << endl;
}
return dp[target];
}

然后看提交记录里的,竟然也有用这个算法解的

class Solution {
public:

int combinationSum4(vector<int>& nums, int target) {
int len = nums.size();
vector<long long> dp(target+1, 0);
for(int i=1; i<=target; i++){
for(int j=0; j<len; j++){
if(i-nums[j]==0){
dp[i] += 1;
}
else if(i-nums[j]>0 && dp[i-nums[j]]!=0){
dp[i] += dp[i-nums[j]];
}
}
dp[i] = dp[i]%10000000000;
}
return dp[target];
}
};

简化一下

class Solution {
public:

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

int len = nums.size();
// 加入边界判断
if (len == 0 || target == 0) return 0;
vector<long long> dp(target+1, 0);
dp[0] = 1;
for(int i=1; i<=target; i++){
for(int j=0; j<len; j++){
if (i-nums[j] >= 0) {
dp[i] += dp[i-nums[j]];
}
}
dp[i] = dp[i]%10000000000;
}
return dp[target];
}
};

还可以用键值对来存储,这个采用递归,也采用了记忆化的方法。

class Solution {
public:
int ret;
int size;
unordered_map<int, int> dp;

int combinationSum4(vector<int>& nums, int target) {
this->ret = 0;
this->size = nums.size();
return count(nums, target);
}

int count(const vector<int> &nums, int target) {
if (target == 0) return 1;
if (dp.count(target) != 0) return dp[target];
int res = 0;
for (int i=0; i<size;i++)
if (target-nums[i]>=0)
res+=count(nums, target-nums[i]);
dp[target] = res;
return dp[target];
}
};
文章作者: X Mεl0n
文章链接: http://www.zrzz.site/2020/09/09/Leetcode-202009/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 X Mεl0n | 随手记

评论