网站建设工具的品牌,如何做网,企业门户网站建设现状,商丘免费网站建设开发公司学习文档#xff1a;代码随想录 (programmercarl.com)
视频链接#xff1a;代码随想录算法公开课 | 最强算法公开课 | 代码随想录 (programmercarl.com) Leetcode 77. 组合
题目描述
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以…学习文档代码随想录 (programmercarl.com)
视频链接代码随想录算法公开课 | 最强算法公开课 | 代码随想录 (programmercarl.com) Leetcode 77. 组合
题目描述
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1
输入n 4, k 2
输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
示例 2
输入n 1, k 1
输出[[1]]提示
1 n 201 k n 解题思路 这是回溯算法的经典题目可以将题目抽象为N叉树来理解回溯算法。这颗树的初始集合就是[1,2,3,4]从左往右取数取过的数就不再取避免出现重复集合每个节点需要一个for循环来遍历所以需要一个startindex来控制遍历的起始值需要用一维数组来存放结果用二维数组来存放所有满足的结果。 图中可以发现n相当于树的宽度k相当于树的深度。
回溯算法三部曲
1. 确定递归函数的返回值合参数
n,k是题目给出startIndex来控制每次for循环的起始位置
vectorvectorint result; // 存放符合条件结果的集合
vectorint path; // 用来存放符合条件单一结果
void backtracking(int n, int k, int startIndex)
2.确定回溯函数的终止条件
当path这个数组的大小如果达到k说明找到了一个子集大小为k的组合了在图中path存的就是根节点到叶子节点的路径。
if (path.size() k) {result.push_back(path);return;
}
3.确定单层搜索的过程
回溯法的搜索过程就是一个树型结构的遍历过程在图中可以看出for循环用来横向遍历递归的过程是纵向遍历。
for (int i startIndex; i n; i) { // 控制树的横向遍历path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归控制树的纵向遍历注意下一层搜索要从i1开始path.pop_back(); // 回溯撤销处理的节点
}
完整代码
class Solution {
private:vectorvectorint result; // 存放符合条件结果的集合vectorint path; // 用来存放符合条件结果void backtracking(int n, int k, int startIndex) {if (path.size() k) {result.push_back(path);return;}for (int i startIndex; i n; i) {path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {result.clear(); // 可以不写path.clear(); // 可以不写backtracking(n, k, 1);return result;}
};
剪枝优化
回溯法虽然是暴力搜索但也有时候可以有点剪枝优化一下的
举一个例子n 4k 4的话那么第一层for循环的时候从元素2开始的遍历都没有意义了。 在第二层for循环从元素3开始的遍历都没有意义了。 可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了那么就没有必要搜索了 已经选择的元素个数path.size(); 还需要的元素个数为: k - path.size(); 在集合n中至多要从该起始位置 : n - (k - path.size()) 1开始遍历
为什么有个1呢因为包括起始位置我们要是一个左闭的集合。
所以优化之后的for循环是
for (int i startIndex; i n - (k - path.size()) 1; i) // i为本次搜索的起始位置 完整代码
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(int n, int k, int startIndex) {if (path.size() k) {result.push_back(path);return;}for (int i startIndex; i n - (k - path.size()) 1; i) { // 优化的地方path.push_back(i); // 处理节点backtracking(n, k, i 1);path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {backtracking(n, k, 1);return result;}
}; Leetcode 216. 组合总和 III
题目描述
找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
示例 1:
输入: k 3, n 7
输出: [[1,2,4]]
解释:
1 2 4 7
没有其他符合的组合了。
示例 2:
输入: k 3, n 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 2 6 9
1 3 5 9
2 3 4 9
没有其他符合的组合了。
示例 3:
输入: k 4, n 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字我们可以得到的最小和是1234 10因为10 1没有有效的组合。提示:
2 k 91 n 60
解题思路 这题相对于上一题就是多了一个限制要找到和为n的k个整数整个集合是固定的。
完整代码
class Solution {
vectorvectorint result;
vectorint path;
void backtracking(int targetSum, int k, int sum, int startIndex) {if (path.size() k) {if(sum targetSum) {result.push_back(path);}return; // 如果path.size() k 但sum ! targetSum 直接返回}for (int i startIndex; i 9; i) { sum i;path.push_back(i); backtracking(targetSum, k, sum, i 1); // 注意i1调整startIndexsum - i; // 回溯path.pop_back(); // 回溯撤销处理的节点}
}
public:vectorvectorint combinationSum3(int k, int n) {backtracking(n, k, 0, 1);return result;}
};剪枝优化
已选元素总和如果已经大于n图中数值为4了那么往后遍历就没有意义了直接剪掉 那么剪枝的地方可以放在递归函数开始的地方剪枝代码如下
if (sum targetSum) { // 剪枝操作return;
}
完整代码
class Solution {
private:vectorvectorint result; // 存放结果集vectorint path; // 符合条件的结果void backtracking(int targetSum, int k, int sum, int startIndex) {if (sum targetSum) { // 剪枝操作return; }if (path.size() k) {if (sum targetSum) result.push_back(path);return; // 如果path.size() k 但sum ! targetSum 直接返回}for (int i startIndex; i 9 - (k - path.size()) 1; i) { // 剪枝sum i; // 处理path.push_back(i); // 处理backtracking(targetSum, k, sum, i 1); // 注意i1调整startIndexsum - i; // 回溯path.pop_back(); // 回溯}}public:vectorvectorint combinationSum3(int k, int n) {result.clear(); // 可以不加path.clear(); // 可以不加backtracking(n, k, 0, 1);return result;}
}; Leetcode 17. 电话号码的字母组合
题目描述
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2
输入digits
输出[]示例 3
输入digits 2
输出[a,b,c]提示
0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。
解题思路
可以使用map或者定义一个二维数组例如string letterMap[10]来做映射
const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9
}; 图中可以看出遍历的深度就是输入23的长度而叶子节点就是我们要收集的结果输出[ad, ae, af, bd, be, bf, cd, ce, cf]。
回溯三部曲
1.确定回溯函数的参数 参数指定是有题目中给的string digits然后还要有一个参数就是int型的index这个index与之前的startIndex不同这个index是记录遍历第几个数字了例如输入“23”可以用来表示现在是遍历“2”对应的字符还是“3”就是用来遍历digits的题目中给出数字字符串同时index也表示树的深度。
vectorstring result;
string s;
void backtracking(const string digits, int index)
2.确定终止条件
例如输入用例23两个数字那么根节点往下递归两层就可以了叶子节点就是要收集的结果集。那么终止条件就是如果index 等于 输入的数字个数digits.size了本来index就是用来遍历digits的。然后收集结果结束本层递归。
if (index digits.size()) {result.push_back(s);return;
}
3.确定单层遍历逻辑
首先要取index指向的数字并找到对应的字符集手机键盘的字符集。然后for循环来处理这个字符集代码如下
int digit digits[index] - 0; // 将index指向的数字转为int
string letters letterMap[digit]; // 取数字对应的字符集
for (int i 0; i letters.size(); i) {s.push_back(letters[i]); // 处理backtracking(digits, index 1); // 递归注意index1一下层要处理下一个数字了s.pop_back(); // 回溯
} 完整代码
class Solution {
private:const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};
public:vectorstring result;string s;void backtracking(const string digits, int index) {if (index digits.size()) {result.push_back(s);return;}int digit digits[index] - 0; // 将index指向的数字转为intstring letters letterMap[digit]; // 取数字对应的字符集for (int i 0; i letters.size(); i) {s.push_back(letters[i]); // 处理backtracking(digits, index 1); // 递归注意index1一下层要处理下一个数字了s.pop_back(); // 回溯}}vectorstring letterCombinations(string digits) {s.clear();result.clear();if (digits.size() 0) {return result;}backtracking(digits, 0);return result;}
};
