脚本宝典收集整理的这篇文章主要介绍了LeetCode 刷题 (九)算法入门--回溯,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
77. 组合77. 组合77. 组合
给定两个整数 n
和 k
,返回范围 [1, n]
中所有可能的 k
个数的组合。
你可以按 任何顺序 返回答案。
思路:
如果解决一个问题有多个步骤,每一个步骤有多种方法,题目又要我们找出所有的方法,可以使用回溯算法; 回溯算法是在一棵树上的 深度优先遍历(因为要找所有的解,所以需要遍历);
为什么说是在一棵树上的深度优先遍历呢?比如说,你现在要解决一个问题,这个问题被分为了若干的步骤,对于每一个步骤都有多个方法到下一个步骤。(听君一席话,就是一席话,嘿嘿嘿!!)。就是说我们么一个步骤的选择都是可以返回来更换的。
就拿本题来说:
比如说给了4和3这两个数据;我们要从1,2,3,4,这4个数里面取3个数。很容易分析出来:当我们第一个数取1的时候,第二个数可以去2,3,4,.........。一次推下去。我们会得到一棵一棵的树。样子就是这个样子(这个不是我画的,我去LeetCode的题解上找到哈哈哈哈!!)
想明白这个过程,那我们的解题办法就来了。对于[1 n]里面的每一个数,在最后选择的k个数里面的只有两种状态,要么它在,要么它不在。所以我们只需要去遍历这n个数,然后用一个数组temp把放入最后结果的数记录下来。由于我们是从小到大遍历,所以当我们把当前元素在最后结果里面的记录完以后,后面再记录的结果就不会再包含当前元素了。
class Solution {
public:
//temp 用来存放每一个可能的结果
vector<int> temp;
//最终结果
vector<vector<int>> ans;
//深度优先遍历
void dfs(int cur, int n, int k) {
// 剪枝:当遍历到底cur个数是,如果temp的元素个数s+剩余元素个数t<k时,就不满足条件了
if (temp.size() + (n - cur + 1) < k) {
return;
}
// temp中元素个数达到k,表示深度优先遍历到达最深处了。此时需要回溯了。
if (temp.size() == k) {
ans.push_back(temp);
return;
}
// 选择当前位置,加入temp
temp.push_back(cur);
dfs(cur + 1, n, k);
// 不选择当前位置,从temp里面删除
temp.pop_back();
dfs(cur + 1, n, k);
}
vector<vector<int>> combine(int n, int k) {
dfs(1, n, k);
return ans;
}
};
46. 全排列
思路:通过上一题,这一题理解起来就更方便了。全部排列顺序,就是上面的那个图,第二次先选择了2以后还可以继续选择1;所以我们只需要把每次选取的元素交换到数组左边,这样就可以和上一题的流程一样了,不过记住记住排列的时候,未选择的元素都可以来占当前cur的位置,由于我们将未选择的元素都交换到cur的右边,所以从cur遍历一遍就可以了。就是这么简单,k默认为n就可以了。
class Solution {
public:
void dfs(vector<vector<int>>& res, vector<int>& output, int cur, int len){
// 所有数都填完了
if (cur == len) {
res.emplace_back(output);
return;
}
//这里每一个数组右边的数都可以当做第cur个元素
for (int i = cur; i < len; ++i) {
// 动态维护数组,将未选取的元素交换到数组右边
swap(output[i], output[cur]);
// 继续递归填下一个数
dfs(res, output, cur + 1, len);
// 撤销交换操作
swap(output[i], output[cur]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
dfs(res, nums, 0, (int)nums.size());
return res;
}
};
784. 字母大小写全排列
给定一个字符串S
,通过将字符串S
中的每个字母转变大小写,我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
思路: 注意理解题目要求,题目是说每个子母可以进行大小写变换,但是没有说可以改变位置哦。
class Solution {
public:
void dfs(vector<string> &res,int cur,string &s,int len){
//数字不变
while(cur<len&&s[cur] >= '0' && s[cur] <= '9')
cur++;
if(cur == len){
res.emplace_back(s);
return ;
}
//子母转变大小写
if(s[cur]>='a'&&s[cur]<='z')
s[cur] = toupper(s[cur]);
else
s[cur] = tolower(s[cur]);
dfs(res,cur+1,s,len);
//子母不转变大小写
if(s[cur]>='a'&&s[cur]<='z')
s[cur] = toupper(s[cur]);
else
s[cur] = tolower(s[cur]);
dfs(res,cur+1,s,len);
}
vector<string> letterCasePermutation(string s) {
vector<string> res;
int len = s.length();
dfs(res,0,s,len);
return res;
}
};
芜湖~~~~~~~~~
以上是脚本宝典为你收集整理的LeetCode 刷题 (九)算法入门--回溯全部内容,希望文章能够帮你解决LeetCode 刷题 (九)算法入门--回溯所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。