leecode Hot100之回溯算法【C++速查】
文章目录
- [46. 全排列](https://leetcode.cn/problems/permutations/)
- [78. 子集](https://leetcode.cn/problems/subsets/)
- [17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)
- [39. 组合总和](https://leetcode.cn/problems/combination-sum/)
- [22. 括号生成](https://leetcode.cn/problems/generate-parentheses/)[子集](https://leetcode.cn/problems/subsets/)
- [79. 单词搜索](https://leetcode.cn/problems/word-search/)
- [131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/)
- [51. N 皇后](https://leetcode.cn/problems/n-queens/)
46. 全排列
class Solution {
public:
vector<vector<int>> res; // 记录所有排列结果
vector<int> track; // 用于记录当前的排列
vector<bool> vis; // 标记数字是否已被使用
int n;
vector<vector<int>> permute(vector<int>& nums) {
n = nums.size();
// track.clear();
//如果要用track[curr]=...就必须先给其赋初值
track.assign(n, 0);
vis.assign(n, false);
dfs(nums, 0); // 从第一个位置开始递归
return res;
}
void dfs(vector<int>& nums, int curr) {
// 如果当前排列已经完整
if (curr == n) {
res.push_back(track); // 将当前排列加入结果
return;
}
for (int i = 0; i < n; i++) {
if (vis[i]) continue; // 如果该元素已被使用，跳过
// 做选择
// track.push_back(nums[i]);
track[curr]=nums[i];
vis[i] = true;
// 递归调用
dfs(nums, curr + 1);
// 回溯
// track.pop_back();
vis[i] = false;
}
}
};
78. 子集
class Solution {
public:
vector<vector<int>> res;
vector<int> track;
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums,0,track);
return res;
}
void dfs(vector<int>& nums,int curr,vector<int>& track){
if(curr==nums.size()){
res.push_back(track);
return;
}
//不选当前的元素
dfs(nums,curr+1,track);
//选当前的元素
track.push_back(nums[curr]);
dfs(nums,curr+1,track);
track.pop_back();
}
};
17. 电话号码的字母组合
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
if(digits.empty()) return res;
vector<string> list{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
string t;
//传入数字串，当前位置，对应list，结果
dfs(digits,0,t,list,res);
return res;
}
void dfs(const string& digits,int curr,string t,const vector<string>& list,vector<string>& res){
if(curr==digits.length()){
res.push_back(t);
return;
}
//得到数字对应的list下标id
int idx=digits[curr]-'0'-2;
for(char c:list[idx]){
dfs(digits,curr+1,t+c,list,res);
}
}
};
39. 组合总和
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<int> state;//当前状态
dfs(candidates,target,0,state);
return res;
}
void dfs(vector<int>& candidates, int target,int start,vector<int>& state){
if(target==0){
res.push_back(state);
return;
}
//继续选择
for(int i=start;i<candidates.size();i++){
if(target-candidates[i]<0) return;
state.push_back(candidates[i]);
dfs(candidates,target-candidates[i],i,state);
state.pop_back();
}
}
};
22. 括号生成子集
class Solution {
public:
vector<string> res;
vector<string> generateParenthesis(int n) {
string state;
dfs(n,n,state);
return res;
}
void dfs(int left,int right,string state){
if(!left&&!right){
state.push_back(0);
res.push_back(state);
}
if(left>=0){
state+='(';
dfs(left-1,right,state);
state.pop_back();
}
if(right>left){
state+=')';
dfs(left,right-1,state);
//string删除最后一个字符
state.pop_back();
}
}
};
79. 单词搜索
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
//多起点dfs查找
if(dfs(board,word,0,i,j)) return true;
}
}
return false;
}
int idx[4]={0,1,0,-1};
int idy[4]={1,0,-1,0};
bool dfs(vector<vector<char>>& board, string word,int curr,int x,int y){
if(board[x][y]!=word[curr]) return false;
if(word.size()-1==curr) return true;
//标记为已访问
char t=board[x][y];
board[x][y]='.';
for(int i=0;i<4;i++){
// dfs(board,word,curr+1,x+idx[i],y+idy[i]);
int a=x+idx[i],b=y+idy[i];
if(a<0||a>board.size()-1||b<0||b>board[0].size()-1||board[a][b]=='.') continue;
if(dfs(board,word,curr+1,a,b)) return true;
}
//恢复
board[x][y]=t;
return false;
}
};
131. 分割回文串
const int N=1005;
bool f[N][N];
class Solution {
public:
vector<vector<string>> res;
vector<vector<string>> partition(string s) {
int n = s.length();
vector<string> current;
// 初始化动态规划数组
memset(f, 0, sizeof(f));
// 每个单字符子串是回文
for (int i = 0; i < n; i++) f[i][i] = 1;
//枚举每个长度
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
if (s[l] == s[r] && (len == 2 || f[l+1][r-1])) f[l][r] = 1;
}
}
// 回溯
backtrack(s, 0, current);
return res;
}
private:
void backtrack(const string &s, int start, vector<string> ¤t) {
if (start == s.length()) {
res.push_back(current);
return;
}
for (int i = start; i < s.length(); i++) {
if (f[start][i]) {//判断是否为回文字符串
current.push_back(s.substr(start, i - start + 1)); // 记录当前回文子串
backtrack(s, i + 1, current); // 继续回溯
current.pop_back(); // 回溯时去掉最后一个回文子串
}
}
}
};
51. N 皇后
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> board(n, string(n, '.'));
vector<int> cols(n, 0); // 列的占用状态
vector<int> diag1(2 * n - 1, 0); // 主对角线的占用状态
vector<int> diag2(2 * n - 1, 0); // 副对角线的占用状态
dfs(0, n, board, cols, diag1, diag2, res);
return res;
}
private:
void dfs(int row, int n, vector<string>& board, vector<int>& cols, vector<int>& diag1, vector<int>& diag2, vector<vector<string>>& res) {
if (row == n) {
res.push_back(board); // 找到一个解，将其加入结果
return;
}
for (int col = 0; col < n; col++) {
int d1 = row - col + n - 1; // 计算主对角线编号
int d2 = row + col; // 计算副对角线编号
if (cols[col] || diag1[d1] || diag2[d2]) continue; // 如果该位置被占用，跳过
board[row][col] = 'Q'; // 放置皇后
cols[col] = 1; // 标记该列占用
diag1[d1] = 1; // 标记主对角线占用
diag2[d2] = 1; // 标记副对角线占用
dfs(row + 1, n, board, cols, diag1, diag2, res); // 递归尝试下一行
board[row][col] = '.'; // 恢复棋盘
cols[col] = 0; // 恢复列占用状态
diag1[d1] = 0; // 恢复主对角线占用状态
diag2[d2] = 0; // 恢复副对角线占用状态
}
}
};
原文地址：https://blog.csdn.net/weixin_74257347/article/details/147234379
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！