当前位置：首页 > news >正文

DFS：深搜+回溯+剪枝实战解决OJ问题

news 2024/11/15 13:49:50

✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

文章目录

前言

一排列、子集问题

1.1 全排列I

1.2 子集I

1.3 找出所有子集的异或总和

1.4 全排列II

1.5 字母大小写全排列

1.6 优美的排列

二组合问题

2.1 电话号码的数字组合

2.2 括号生成

2.3 组合

2.4 目标和

2.5 组合总和

三矩阵搜索问题

3.1 N皇后

3.2 有效的数独

3.3 解数独

3.4 单词搜素

3.5 黄金矿工

3.6 不同路径III

总结

前言

本篇详细介绍了进一步介绍DFS，让使用者对DFS有更加深刻的认知，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！

我们在做DFS的题目时，首先要把决策树（通过策略把结果不重不漏的枚举得到）画下，缕清思路，设计代码自然水到渠成

一排列、子集问题

1.1 全排列I

46. 全排列 - 力扣（LeetCode）

class Solution {vector<vector<int>> ret;vector<int> path;bool check[7];
public:vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}void dfs(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);return;}for(int i = 0;i<nums.size();i++){if(check[i] == false){path.push_back(nums[i]);check[i] = true;dfs(nums);//回溯-> 恢复现场path.pop_back();check[i] = false;}}}
};

1.2 子集I

78. 子集 - 力扣（LeetCode）

解法一：

class Solution {vector<vector<int>> ret;vector<int> path;
public:vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}void dfs(vector<int>& nums,int n){if(n == nums.size()){ret.push_back(path);return;}//选path.push_back(nums[n]);dfs(nums,n+1);path.pop_back();//不选dfs(nums,n+1);}
};

解法二：

class Solution {vector<vector<int>> ret;vector<int> path;
public:vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}void dfs(vector<int>& nums,int pos){ret.push_back(path);for(int i = pos;i<nums.size();i++){path.push_back(nums[i]);dfs(nums,i+1);path.pop_back();}}
};

1.3 找出所有子集的异或总和

1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）

class Solution {int sum;int path;
public:int subsetXORSum(vector<int>& nums) {dfs(nums,0);return sum;}void dfs(vector<int>& nums,int pos){sum += path;for(int i = pos;i<nums.size();i++){path^=nums[i];dfs(nums,i+1);path^=nums[i];       }}
};

1.4 全排列II

47. 全排列 II - 力扣（LeetCode）

class Solution {vector<vector<int>> ret;vector<int> path;bool check[9];
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());dfs(nums);return ret;}void dfs(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);return;}for(int i = 0;i<nums.size();i++){if(check[i] == false && (i==0 || nums[i] != nums[i-1] ||check[i-1] == true)){path.push_back(nums[i]);check[i] = true;dfs(nums);path.pop_back();check[i] = false;}}}
};

1.5 字母大小写全排列

784. 字母大小写全排列 - 力扣（LeetCode）

class Solution {vector<string> ret;string path;
public:vector<string> letterCasePermutation(string s) {dfs(s,0);return ret;}void dfs(string s,int pos){if(pos == s.size()){ret.push_back(path);return;}char ch = s[pos];//不改变path += ch;dfs(s,pos+1);path.pop_back();//改变if(ch<'0' || ch>'9'){char tmp = change(ch);path += tmp;dfs(s,pos+1);path.pop_back();}}char change(char ch){if(ch>='a'&&ch<='z')    ch-=32;else    ch+=32;return ch;}
};

1.6 优美的排列

526. 优美的排列 - 力扣（LeetCode）

class Solution {bool check[16];int ret;
public:int countArrangement(int n) {dfs(n,1);return ret;}void dfs(int n, int pos){if(pos == n+1){ret++;return;}for(int i = 1; i<=n;i++){if(check[i] == false&&(i % pos == 0 || pos % i == 0)){check[i] = true;dfs(n,pos+1);check[i] = false;}}}
};

二组合问题

2.1 电话号码的数字组合

17. 电话号码的字母组合 - 力扣（LeetCode）

class Solution {string path;vector<string> ret;vector<string> hash = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:vector<string> letterCombinations(string digits) {if(digits.size() == 0)    return ret;dfs(digits,0);return ret;}void dfs(string digits,int pos){if(pos == digits.size()){ret.push_back(path);return;}for(auto& ch : hash[digits[pos] - '0']){path.push_back(ch);dfs(digits,pos+1);path.pop_back();}}
};

2.2 括号生成

22. 括号生成 - 力扣（LeetCode）

class Solution {vector<string> ret;string path;int count; //记录有效括号的对数
public:vector<string> generateParenthesis(int n) {count = n;dfs(0,0);return ret;}void dfs(int left,int right){if(path.size() == 2*count){ret.push_back(path);return;}if(left<count){path.push_back('(');dfs(left+1,right);path.pop_back();}if(right<left){path.push_back(')');dfs(left,right+1);path.pop_back();}}
};

2.3 组合

77. 组合 - 力扣（LeetCode）

class Solution {vector<vector<int>> ret;vector<int> path;int n, k;
public:vector<vector<int>> combine(int _n, int _k) {n = _n;k = _k;dfs(1);return ret;}void dfs(int pos){if(path.size() == k){ret.push_back(path);return;}for(int i = pos; i<=n; ++i){path.push_back(i);dfs(i+1);path.pop_back();}}
};

2.4 目标和

494. 目标和 - 力扣（LeetCode）

class Solution {int ret;int target;
public:int findTargetSumWays(vector<int>& nums, int _target) {target = _target;dfs(nums,0,0);return ret;}void dfs(vector<int>& nums, int pos, int prev){if(pos == nums.size()){if(prev == target)ret++;return;}dfs(nums,pos+1,prev+nums[pos]);dfs(nums,pos+1,prev-nums[pos]);}
};

2.5 组合总和

39. 组合总和 - 力扣（LeetCode）

解法一：

class Solution {vector<vector<int>> ret;vector<int> path;int target;
public:vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0,0);return ret;}void dfs(vector<int>& candidates,int sum, int pos){if(sum>target)  return;if(sum == target){ret.push_back(path);return;}for(int i = pos;i<candidates.size();i++){path.push_back(candidates[i]);dfs(candidates,sum+candidates[i],i);path.pop_back();}}
};

解法二：

class Solution {vector<vector<int>> ret;vector<int> path;int target;
public:vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0,0);return ret;}void dfs(vector<int>& candidates,int sum, int pos){if(sum == target){ret.push_back(path);return;}if(sum>target || pos == candidates.size())  return;for(int k = 0;k*candidates[pos]+sum<=target;k++){if(k)   path.push_back(candidates[pos]);dfs(candidates,sum+k*candidates[pos],pos+1);}for(int k = 1;k*candidates[pos]+sum<=target;k++){path.pop_back();}}
};

三矩阵搜索问题

3.1 N皇后

51. N 皇后 - 力扣（LeetCode）

class Solution {bool checkCol[10], checkDig1[20], checkDig2[20];vector<vector<string>> ret;vector<string> path;
public:vector<vector<string>> solveNQueens(int n) {path.resize(n);for(int i = 0;i<n;i++)path[i].append(n,'.');dfs(n,0);return ret;}void dfs(int n, int row){if(row == n){ret.push_back(path);return;}for(int col = 0;col<n;col++){if(!checkCol[col]&&!checkDig1[row-col+n]&&!checkDig2[row+col]){path[row][col] = 'Q';checkCol[col] = checkDig1[row-col+n] = checkDig2[row+col] = true;dfs(n,row+1);path[row][col] = '.';checkCol[col] = checkDig1[row-col+n] = checkDig2[row+col] = false;}}}
};

3.2 有效的数独

36. 有效的数独 - 力扣（LeetCode）

class Solution {bool row[9][10];bool col[9][10];bool grid[3][3][10];
public:bool isValidSudoku(vector<vector<char>>& board) {for(int i = 0;i<9;i++){for(int j = 0;j<9;j++){if(board[i][j] != '.'){int num = board[i][j] -'0';if(row[i][num] || col[j][num] || grid[i/3][j/3][num])return false;row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}}return true;}
};

3.3 解数独

37. 解数独 - 力扣（LeetCode）

class Solution {bool row[9][10];bool col[9][10];bool grid[3][3][10];
public:void solveSudoku(vector<vector<char>>& board) {for(int i = 0;i<9;i++){for(int j = 0;j<9;j++){if(board[i][j] != '.'){int num = board[i][j] -'0';row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}}dfs(board);}bool dfs(vector<vector<char>>& board){for(int i = 0;i<9;i++){for(int j = 0;j<9;j++){if(board[i][j] == '.'){for(int num = 1; num<=9; num++){if(!row[i][num]&&!col[j][num]&&!grid[i/3][j/3][num]){board[i][j] = num + '0';row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;if(dfs(board) == true)  return true;  //判断当前所填的数是否有效board[i][j] = '.';row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;}}return false;  //无法填数时，则说明之前的填的数错误，返回错误}}}return true;}
};

3.4 单词搜素

79. 单词搜索 - 力扣（LeetCode）

class Solution {bool vis[7][7];int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int m,n;
public:bool exist(vector<vector<char>>& board, string word) {m = board.size(),n = board[0].size();for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){if(board[i][j] == word[0]){vis[i][j] = true;if(dfs(board,word,i,j,1))   return true;vis[i][j] = false;}}}return false;}bool dfs(vector<vector<char>>& board, string word,int i,int j,int pos){if(pos == word.size())  return true;for(int k = 0;k<4;k++){int x = i + dx[k],y = j + dy[k];if(x >=0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == word[pos]){vis[x][y] = true;if(dfs(board,word,x,y,pos+1))   return true;vis[x][y] = false;}}return false;}
};

3.5 黄金矿工

1219. 黄金矿工 - 力扣（LeetCode）

本题的算法原理和单词搜索同，只不过多了一两个变量

class Solution {bool vis[16][16];int dx [4] = {0,0,1,-1};int dy [4] = {1,-1,0,0};int m,n,path,ret;
public:int getMaximumGold(vector<vector<int>>& grid) {m = grid.size(),n = grid[0].size();for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){if(grid[i][j] != 0){vis[i][j] = true;dfs(grid,i,j,grid[i][j]);vis[i][j] = false;}}}return ret;}void dfs(vector<vector<int>>& grid,int i,int j,int path){ret = max(ret,path);for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >=0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != 0){vis[x][y] = true;dfs(grid,x,y,path+grid[x][y]);vis[x][y] = false;}}}
};

3.6 不同路径III

980. 不同路径 III - 力扣（LeetCode）

class Solution {bool vis[21][21];int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int m,n,step;int ret;
public:int uniquePathsIII(vector<vector<int>>& grid) {int bx,by;m = grid.size(),n = grid[0].size();for(int i = 0;i<m;i++){for(int j = 0; j < n;j++){if(grid[i][j] == 0)     step++;else if(grid[i][j] == 1){bx = i;by = j;}}}step += 2;vis[bx][by] = true;dfs(grid,bx,by,1);return ret;}void dfs(vector<vector<int>>& grid,int i,int j,int count){if(grid[i][j] == 2){if(count == step) //判断是否合法ret++;return;}for(int k = 0;k < 4;k++){int x = i + dx[k],y = j + dy[k];if(x >=0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != -1){vis[x][y] = true;dfs(grid,x,y,count + 1);vis[x][y] = false;}}}
};