視頻鏈接生成網(wǎng)站國(guó)通快速建站
???學(xué)習(xí)的道路很枯燥，希望我們能并肩走下來(lái)!
文章目錄
目錄
文章目錄
前言
一??排列、子集問(wèn)題
1.1??全排列I
1.2? 子集I?
?1.3? 找出所有子集的異或總和
1.4? 全排列II
1.5? 字母大小寫(xiě)全排列
1.6? 優(yōu)美的排列
二? 組合問(wèn)題?
2.1? 電話(huà)號(hào)碼的數(shù)字組合
?2.2? 括號(hào)生成
2.3? 組合?
2.4? 目標(biāo)和
2.5? 組合總和
三? 矩陣搜索問(wèn)題
3.1? N皇后?
3.2? 有效的數(shù)獨(dú)
3.3? 解數(shù)獨(dú)?
3.4? 單詞搜素
3.5? 黃金礦工
3.6? 不同路徑III
總結(jié)
前言
本篇詳細(xì)介紹了進(jìn)一步介紹DFS，讓使用者對(duì)DFS有更加深刻的認(rèn)知，而不是僅僅停留在表面，更好的模擬，為了更好的使用. 文章可能出現(xiàn)錯(cuò)誤，如有請(qǐng)?jiān)谠u(píng)論區(qū)指正，讓我們一起交流，共同進(jìn)步！
我們?cè)谧鯠FS的題目時(shí)，首先要把決策樹(shù)（通過(guò)策略把結(jié)果不重不漏的枚舉得到）畫(huà)下，縷清思路，設(shè)計(jì)代碼自然水到渠成
一??排列、子集問(wèn)題
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);//回溯-> 恢復(fù)現(xiàn)場(chǎng)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? 字母大小寫(xiě)全排列
784. 字母大小寫(xiě)全排列 - 力扣（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? 優(yōu)美的排列
526. 優(yōu)美的排列 - 力扣（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;}}}
};二? 組合問(wèn)題?
2.1? 電話(huà)號(hào)碼的數(shù)字組合
17. 電話(huà)號(hào)碼的字母組合 - 力扣（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? 括號(hào)生成
22. 括號(hào)生成 - 力扣（LeetCode）
class Solution {vector<string> ret;string path;int count; //記錄有效括號(hào)的對(duì)數(shù)
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? 目標(biāo)和
494. 目標(biāo)和 - 力扣（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();}}
};三? 矩陣搜索問(wèn)題
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? 有效的數(shù)獨(dú)
36. 有效的數(shù)獨(dú) - 力扣（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? 解數(shù)獨(dú)?
37. 解數(shù)獨(dú) - 力扣（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; //判斷當(dāng)前所填的數(shù)是否有效board[i][j] = '.';row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;}}return false; //無(wú)法填數(shù)時(shí)，則說(shuō)明之前的填的數(shù)錯(cuò)誤，返回錯(cuò)誤}}}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）
?本題的算法原理和單詞搜索同，只不過(guò)多了一兩個(gè)變量
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;}}}
};總結(jié)
???各位讀友，本篇分享到內(nèi)容是否更好的讓你理解DFS，如果對(duì)你有幫助給個(gè)👍贊鼓勵(lì)一下吧！！
🎉🎉🎉世上沒(méi)有絕望的處境，只有對(duì)處境絕望的人。
感謝每一位一起走到這的伙伴，我們可以一起交流進(jìn)步！！！一起加油吧！！