第十八天
我使用的C++,错误的地方请见谅,文章初衷仅用来督促本人学习,如果恰巧能够给你带来帮助,我会十分开心。
文章目录
- 第十八天
- 一、77. 组合
- 二、46. 全排列
- 三、784. 字母大小写全排列
一、77. 组合
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
class Solution {
public:
vector<vector<int>> ans;
vector<int> temp;
vector<vector<int>> combine(int n, int k) {
//排列组合,输出一个二维数组,
dfs(1, n, k);
return ans;
}
void dfs(int cur, int n, int k){
if (temp.size() + (n - cur + 1) < k){//剪枝
return;
}
if (temp.size() == k){//合法答案
ans.push_back(temp);
return;
}
temp.push_back(cur);
dfs(cur + 1, n, k);
temp.pop_back();
dfs(cur + 1, n, k);
}
};
递归问题一生之敌啊!!!
二进制枚举问题
二、46. 全排列
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
没能特别理解回溯法
class Solution {
public:
void back(vector<vector<int>>& ans, vector<int>& out, int cur, int n){
if (cur == n){
ans.push_back(out);//压入正确解
return;
}
for (int i = cur; i < n; ++i){//将数组分为两部分,依次填数
swap(out[cur], out[i]);
back(ans, out, cur + 1, n);
swap(out[cur], out[i]);//还原顺序,为下一次交换
}
}
vector<vector<int>> permute(vector<int>& nums) {
//数组全排列,返回二维数组
vector<vector<int>> ans;
back(ans, nums, 0, nums.size());
return ans;
}
};
swap来实现动态更新真不错!只是要记得撤销操作
三、784. 字母大小写全排列
给定一个字符串S,通过将字符串S中的每个字母转变大小写,我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
class Solution {
public:
void back(vector<string>& ans, int cur, int n, string s){
if (cur == n){
ans.push_back(s);
return;
}
else if (s[cur] >= 'a' && s[cur] <= 'z'){
s[cur] -= 32;
back(ans, cur + 1, n, s);
s[cur] += 32;
}
else if (s[cur] >= 'A' && s[cur] <= 'Z'){
s[cur] += 32;
back(ans, cur + 1, n, s);
s[cur] -= 32;
}
{
back(ans, cur + 1, n, s);
}
}
vector<string> letterCasePermutation(string s) {
//同样是全排列,只不过换成了对字母大小写的排列
vector<string> ans;
back(ans, 0, s.size(), s);
return ans;
}
};
稍微有一点理解回溯了