数据处理网站开发,免费 网站 cms,网络科技公司网站首页,网站建设网页设计培训学校目录
1 39. 组合总和
2 22. 括号生成
3 79. 单词搜索 菜鸟做题#xff0c;语言是 C#xff0c;感冒快好版
关于对回溯算法的理解请参照我的上一篇博客#xff1b;
在之后的博客中#xff0c;我将只分析回溯算法中的 for 循环。 1 39. 组合总和
题眼#xff1a;c…目录
1 39. 组合总和
2 22. 括号生成
3 79. 单词搜索 菜鸟做题语言是 C感冒快好版
关于对回溯算法的理解请参照我的上一篇博客
在之后的博客中我将只分析回溯算法中的 for 循环。 1 39. 组合总和
题眼candidates 中的同一个数字可以无限制重复被选取。
根据题眼for 循环结构如下
for (int i begin; i candidates.size(); i) {output.push_back(candidates[i]);sum candidates[i];helper(candidates, target, output, i, sum);sum - candidates[i];output.pop_back();
} 与之前题解的唯一不同之处在于递归时传的不再是 begin 1而是 i 。这是由于每个字母都可以被重复使用因此我们可以从当前字母开始选择而非跳过它。 思路说明图 假设 target 8 。在第一层函数中i begin 0即从 2 开始选择再将 i 传给第二层函数在第二层函数中i begin 0即从 2 开始选择再将 i 传给第三层函数以此类推。直到第五层函数此时 sum 2 2 2 2 8即继续加下去也永远无法得到 target 。因此返回到第四层函数i 1即考虑 3 是否可行。以此类推。
由上述分析可得递归终止条件为
if (sum target) return;
if (sum target) {ans.push_back(output);return;
}
一是当前 sum 已经大于 target不能再增加下去了二是当前 sum 已经等于 target也不能再增加下去了区别在于我们要将成功的组合记录下来。
class Solution {
public:vectorvectorint ans;void helper(vectorint candidates, int target,vectorint output, int begin, int sum) {if (sum target) return;if (sum target) {ans.push_back(output);return;}for (int i begin; i candidates.size(); i) {output.push_back(candidates[i]);sum candidates[i];helper(candidates, target, output, i, sum);sum - candidates[i];output.pop_back();}}vectorvectorint combinationSum(vectorint candidates, int target) {vectorint output;helper(candidates, target, output, 0, 0);return ans;}
}; 你可能会认为传递的参数太多那你可以把它们都定义成全局变量。 2 22. 括号生成
for 循环结构如下
output.push_back(();
l;
helper(output, n, l, r);
output.pop_back();
--l;
output.push_back());
r;
helper(output, n, l, r);
output.pop_back();
--r;
这种写法和 78. 子集 很像。在 78. 子集 中只有两种选择即是否让当前字母进入子集同样地在本题中也只有两种选择即当前坑位填左括号还是右括号我们还设置了变量来记录当前左右括号的个数。
递归终止条件为
if (l n || r n || r l) return;
if (l n r n) {ans.push_back(output);return;
}
一是如果当前左或右括号的个数大于所需的个数则返回二是如果当前右括号的个数大于当前左括号的个数则返回这是因为该右括号肯定找不到配对的左括号三是如果左右括号的个数都等于所需的个数了则记录成功的组合并返回。
class Solution {
public:vectorstring ans;void helper(string output, int n, int l, int r) {if (l n || r n || r l) return;if (l n r n) {ans.push_back(output);return;}output.push_back(();l;helper(output, n, l, r);output.pop_back();--l;output.push_back());r;helper(output, n, l, r);output.pop_back();--r;}vectorstring generateParenthesis(int n) {string output;helper(output, n, 0, 0);return ans;}
}; 3 79. 单词搜索
非典型 for 循环结构如下
visited[r][c] 1;bool up false, down false, left false, right false;
if (r - 1 0 !visited[r - 1][c]) left helper(board, word, r - 1, c, i 1);
if (r 1 nr !visited[r 1][c]) right helper(board, word, r 1, c, i 1);
if (c - 1 0 !visited[r][c - 1]) up helper(board, word, r, c - 1, i 1);
if (c 1 nc !visited[r][c 1]) down helper(board, word, r, c 1, i 1);visited[r][c] 0;return up || down || left || right;
这里的 “选择” 就是 “从当前位置出发有四个方向可以走”。本来想写个 for 循环来遍历四个方向的无奈这里有返回值因此无法一概而论。这里的结构还是满足 “处理-递归-清除” 的格式只是最后多了一个返回值。只要有一个方向能走得通我们都返回 true 。 它不像之前的题一样每个坑位/位置管好自己即可而是要和后面的坑位/位置共荣辱。 递归终止条件
if (board[r][c] ! word[i]) return false;
if (i word.size() - 1) return true;
一是当前字母与 word 中的字母不同返回 false二是已经找到了所有字母返回 true 。 这道题感觉像是图论和回溯的杂合体啊啊啊。之前的题都是只有一个方向右而这道题有四个方向上下左右。 class Solution {
public:int nr, nc;vectorvectorint visited;bool helper(vectorvectorchar board, string word, int r, int c, int i) {if (board[r][c] ! word[i]) return false;if (i word.size() - 1) return true;visited[r][c] 1;bool up false, down false, left false, right false;if (r - 1 0 !visited[r - 1][c])left helper(board, word, r - 1, c, i 1);if (r 1 nr !visited[r 1][c])right helper(board, word, r 1, c, i 1);if (c - 1 0 !visited[r][c - 1])up helper(board, word, r, c - 1, i 1);if (c 1 nc !visited[r][c 1])down helper(board, word, r, c 1, i 1);visited[r][c] 0;return up || down || left || right;}bool exist(vectorvectorchar board, string word) {nr board.size();nc board[0].size();visited.resize(nr);for (auto v : visited)v.resize(nc);for (int i 0; i nr; i) {for (int j 0; j nc; j) {if (helper(board, word, i, j, 0)) return true;}}return false;}
};
说明我们认为每个位置都有可能是 word 的起始点因此使用双重 for 循环进行遍历。不过只有当找完了 word 时才返回 true反之会走向最后的 false 。代码如下
for (int i 0; i nr; i) {for (int j 0; j nc; j) {if (helper(board, word, i, j, 0)) return true;}
}return false; 最好取 row 和 column 的首字母来定义变量否则把自己都绕晕了。
