Day18 OK,继续追今天的打卡!第十八天
- 以下是今日份的总结
- 如何理解回溯法
- 组合
- 组合总和III
- 电话号码的字母组合
以下是今日份的总结
77 组合
216 组合总和III
17 电话号码的字母组合
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构,指的是所有回溯法的问题都可以抽象为树形结构!
因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度就构成了树的深度。
递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。
今天的题目难度不低,尽量还是写一些简洁代码 ^ _ ^
组合
思路:
每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围。
n相当于树的宽度,k相当于树的深度。
值得注意的是
每次搜索到了叶子节点,我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来,就可以求得 n个数中k个数的组合集合。
递归
vector<vector<int>> result;
vector<int> path;
void backTrack(int n,int k, int start){
//终止条件
if(path.size()==k){
result.push_back(path);
return;
}
//开始遍历
for(int i = start;i<=n;i++){//根据题意 i从1开始,所以<=n
path.push_back(i);
backTrack(n, k, i+1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
//判空
if(k>n||k==0||n==0) return vector<vector<int>>();
backTrack(n, k, 1);
return result;
}
for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了,那么就没有必要搜索了,优化如下:
vector<vector<int>> result;
vector<int> path;
void backTrack(int n,int k, int start){
//终止条件
if(path.size()==k){
result.push_back(path);
return;
}
//开始遍历
//i至多遍历到n-(k-path.size())+1,往后就没有意义了
for(int i = start;i<=n-(k-path.size())+1;i++){
path.push_back(i);
backTrack(n, k, i+1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
//判空
if(k>n||k==0||n==0) return vector<vector<int>>();
backTrack(n, k, 1);
return result;
}
组合总和III
思路:
回溯法,和上一题思路一样,在回溯的过程中加入了总和的加减
值得注意的是
总和的加减分别对应了push和pop
递归
int sum = 0;
vector<vector<int>>res;
vector<int>vec;
void backTrack(int k, int n, int start){
//终止条件
if(sum == n&&vec.size()==k){
res.push_back(vec);
return;
}
//遍历
for(int i = start; i<=9;i++){
vec.push_back(i);
sum+=i;//累加当前值,以便查找符合条件的数组
backTrack(k, n, i+1);
vec.pop_back();
sum -= i; //回溯的时候把累加的值也减去
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backTrack(k, n, 1);
return res;
}
电话号码的字母组合
思路:
回溯法,但是每层的分支是已知的,只需要按顺序遍历即可
值得注意的是
遍历string是char,char转int
递归
vector<vector<char>> keyboard = {
{},
{'a', 'b', 'c'}, // 2
{'d', 'e', 'f'}, // 3
{'g', 'h', 'i'}, // 4
{'j', 'k', 'l'}, // 5
{'m', 'n', 'o'}, // 6
{'p', 'q', 'r', 's'}, // 7
{'t', 'u', 'v'}, // 8
{'w', 'x', 'y', 'z'} // 9
};
vector<string> res;
string s;
void backTrack(string str,int start) {
if(str=="")return;
// 终止条件
if (str.size() == s.size()) {
res.push_back(s);
return;
}
// 遍历
//外层遍历digits
for (int i = start; i < str.size(); i++) {
int num = str[i]-'0';//char转int
//为了遍历对应按键的字母
for (int j = 0; j < keyboard[num-1].size(); j++) {
s.push_back(keyboard[num-1][j]);//末尾加上选择的字符
backTrack(str,i+1);
s.pop_back();//回溯,弹出string末尾的字符
}
}
}
vector<string> letterCombinations(string digits) {
backTrack(digits,0);
return res;
}
写在最后
----OK,今日份的博客就写到这里,这一期的回溯法很巧秒啊,明天继续加油!!!
—看了看下期的题,但是我的栈还有一节没写;
–追上时间进度了吗?如追,从欠三天变成欠二天!!(笑
-今天不知道有没有。