上海个人网站制作公司,电商运营是销售吗,关注网站制作,襄阳商城网站建设✨✨✨学习的道路很枯燥#xff0c;希望我们能并肩走下来! 文章目录 目录
文章目录
前言
一 排列、子集问题
1.1 全排列I
1.2 子集I 1.3 找出所有子集的异或总和
1.4 全排列II
1.5 字母大小写全排列
1.6 优美的排列
二 组合问题
2.1 电话号码的数字组合 … ✨✨✨学习的道路很枯燥希望我们能并肩走下来! 文章目录 目录
文章目录
前言
一 排列、子集问题
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 {vectorvectorint ret;vectorint path;bool check[7];
public:vectorvectorint permute(vectorint nums) {dfs(nums);return ret;}void dfs(vectorint nums){if(path.size() nums.size()){ret.push_back(path);return;}for(int i 0;inums.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 {vectorvectorint ret;vectorint path;
public:vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}void dfs(vectorint nums,int n){if(n nums.size()){ret.push_back(path);return;}//选path.push_back(nums[n]);dfs(nums,n1);path.pop_back();//不选dfs(nums,n1);}
};
解法二 class Solution {vectorvectorint ret;vectorint path;
public:vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}void dfs(vectorint nums,int pos){ret.push_back(path);for(int i pos;inums.size();i){path.push_back(nums[i]);dfs(nums,i1);path.pop_back();}}
}; 1.3 找出所有子集的异或总和
1863. 找出所有子集的异或总和再求和 - 力扣LeetCode class Solution {int sum;int path;
public:int subsetXORSum(vectorint nums) {dfs(nums,0);return sum;}void dfs(vectorint nums,int pos){sum path;for(int i pos;inums.size();i){path^nums[i];dfs(nums,i1);path^nums[i]; }}
};
1.4 全排列II
47. 全排列 II - 力扣LeetCode class Solution {vectorvectorint ret;vectorint path;bool check[9];
public:vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(),nums.end());dfs(nums);return ret;}void dfs(vectorint nums){if(path.size() nums.size()){ret.push_back(path);return;}for(int i 0;inums.size();i){if(check[i] false (i0 || 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 {vectorstring ret;string path;
public:vectorstring 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,pos1);path.pop_back();//改变if(ch0 || ch9){char tmp change(ch);path tmp;dfs(s,pos1);path.pop_back();}}char change(char ch){if(chachz) ch-32;else ch32;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 n1){ret;return;}for(int i 1; in;i){if(check[i] false(i % pos 0 || pos % i 0)){check[i] true;dfs(n,pos1);check[i] false;}}}
};
二 组合问题
2.1 电话号码的数字组合
17. 电话号码的字母组合 - 力扣LeetCode class Solution {string path;vectorstring ret;vectorstring hash {,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};
public:vectorstring 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,pos1);path.pop_back();}}
}; 2.2 括号生成
22. 括号生成 - 力扣LeetCode class Solution {vectorstring ret;string path;int count; //记录有效括号的对数
public:vectorstring 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(leftcount){path.push_back(();dfs(left1,right);path.pop_back();}if(rightleft){path.push_back());dfs(left,right1);path.pop_back();}}
};
2.3 组合
77. 组合 - 力扣LeetCode class Solution {vectorvectorint ret;vectorint path;int n, k;
public:vectorvectorint 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; in; i){path.push_back(i);dfs(i1);path.pop_back();}}
};
2.4 目标和
494. 目标和 - 力扣LeetCode class Solution {int ret;int target;
public:int findTargetSumWays(vectorint nums, int _target) {target _target;dfs(nums,0,0);return ret;}void dfs(vectorint nums, int pos, int prev){if(pos nums.size()){if(prev target)ret;return;}dfs(nums,pos1,prevnums[pos]);dfs(nums,pos1,prev-nums[pos]);}
};
2.5 组合总和
39. 组合总和 - 力扣LeetCode 解法一 class Solution {vectorvectorint ret;vectorint path;int target;
public:vectorvectorint combinationSum(vectorint candidates, int _target) {target _target;dfs(candidates,0,0);return ret;}void dfs(vectorint candidates,int sum, int pos){if(sumtarget) return;if(sum target){ret.push_back(path);return;}for(int i pos;icandidates.size();i){path.push_back(candidates[i]);dfs(candidates,sumcandidates[i],i);path.pop_back();}}
}; 解法二 class Solution {vectorvectorint ret;vectorint path;int target;
public:vectorvectorint combinationSum(vectorint candidates, int _target) {target _target;dfs(candidates,0,0);return ret;}void dfs(vectorint candidates,int sum, int pos){if(sum target){ret.push_back(path);return;}if(sumtarget || pos candidates.size()) return;for(int k 0;k*candidates[pos]sumtarget;k){if(k) path.push_back(candidates[pos]);dfs(candidates,sumk*candidates[pos],pos1);}for(int k 1;k*candidates[pos]sumtarget;k){path.pop_back();}}
};
三 矩阵搜索问题
3.1 N皇后
51. N 皇后 - 力扣LeetCode class Solution {bool checkCol[10], checkDig1[20], checkDig2[20];vectorvectorstring ret;vectorstring path;
public:vectorvectorstring solveNQueens(int n) {path.resize(n);for(int i 0;in;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;coln;col){if(!checkCol[col]!checkDig1[row-coln]!checkDig2[rowcol]){path[row][col] Q;checkCol[col] checkDig1[row-coln] checkDig2[rowcol] true;dfs(n,row1);path[row][col] .;checkCol[col] checkDig1[row-coln] checkDig2[rowcol] false;}}}
};
3.2 有效的数独
36. 有效的数独 - 力扣LeetCode class Solution {bool row[9][10];bool col[9][10];bool grid[3][3][10];
public:bool isValidSudoku(vectorvectorchar board) {for(int i 0;i9;i){for(int j 0;j9;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(vectorvectorchar board) {for(int i 0;i9;i){for(int j 0;j9;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(vectorvectorchar board){for(int i 0;i9;i){for(int j 0;j9;j){if(board[i][j] .){for(int num 1; num9; 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(vectorvectorchar board, string word) {m board.size(),n board[0].size();for(int i 0;im;i){for(int j 0;jn;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(vectorvectorchar board, string word,int i,int j,int pos){if(pos word.size()) return true;for(int k 0;k4;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,pos1)) 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(vectorvectorint grid) {m grid.size(),n grid[0].size();for(int i 0;im;i){for(int j 0;jn;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(vectorvectorint 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,pathgrid[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(vectorvectorint grid) {int bx,by;m grid.size(),n grid[0].size();for(int i 0;im;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(vectorvectorint 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;}}}
}; 总结
✨✨✨各位读友本篇分享到内容是否更好的让你理解DFS如果对你有帮助给个赞鼓励一下吧 世上没有绝望的处境只有对处境绝望的人。 感谢每一位一起走到这的伙伴我们可以一起交流进步一起加油吧
