学前端要逛那些网站,合肥新闻 今天 最新消息,可以自己做头像的网站,淄博企业网站建设价格key#xff1a;画出决策树#xff08;就是找个简单例子模拟一下的树状决策图#xff09;
dfs传参 or 全局变量#xff1a;
int, double等常量/比较小的变量#xff0c;可以dfs参数传递vector等线性O#xff08;N#xff09;变量#xff0c;要用全局变量 回溯#x…key画出决策树就是找个简单例子模拟一下的树状决策图
dfs传参 or 全局变量
int, double等常量/比较小的变量可以dfs参数传递vector等线性ON变量要用全局变量 回溯 降低时间空间复杂度
dfs主要用途
全排列求子集路径枚举
1.找出所有子集的异或综合再求和
link:1863. 找出所有子集的异或总和再求和 - 力扣LeetCode
就是求子集
code
class Solution {
public:int ret 0;int cur 0;int subsetXORSum(vectorint nums) {dfs(nums, 0);return ret;}void dfs(vectorint nums, int idx)//对idx下标选择取舍{// 出口if(idx nums.size()){printf(ret %d\n, ret);ret cur;return;}// 主题// 不要dfs(nums, idx 1);// 要cur ^ nums[idx];dfs(nums, idx 1);cur ^ nums[idx]; // 回溯}
}; 2.全排列II
link:47. 全排列 II - 力扣LeetCode
不重复全排列
code
class Solution {
public:vectorvectorint ans;vectorint cur;vectorbool used;vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end());used vectorbool(nums.size(), false);dfs(nums, 0);return ans;}void dfs(vectorint nums, int idx)// 选择第idx下标元素{// 出口if(idx nums.size()) {ans.push_back(cur);return;}// 主体for(int i 0; i nums.size(); i){if(!used[i] (i 0 || !used[i-1] || nums[i] ! nums[i-1])){cur.push_back(nums[i]);used[i] true;dfs(nums, idx 1);used[i] false;cur.pop_back(); // 回溯}}}
}; 3.电话号码的字母组合
link:17. 电话号码的字母组合 - 力扣LeetCode
组合
code
class Solution {
public:vectorstring ans;string cur; // 全局变量unordered_mapchar, string map {{2, abc}, {3, def},{4, ghi},{5, jkl},{6, mno}, {7, pqrs},{8, tuv},{9, wxyz}};vectorstring letterCombinations(string digits) {if(!digits.size()) return {};dfs(digits, 0);return ans;}void dfs(string digits, int idx){// 出口if(idx digits.size()){ans.push_back(cur);return;}for(char ch:map[digits[idx]]){cur ch;dfs(digits, idx 1);cur.pop_back();// 回溯}}
}; 4.括号生成
link:22. 括号生成 - 力扣LeetCode
有条件全排列
code
class Solution {
public:vectorstring ans {};string path ;// 全局变量int sum 0;// 全局变量int n;vectorstring generateParenthesis(int _n) {// key: ( 1, ) -1, 令sum属于[0, 3]即可n _n;dfs(0);return ans;}void dfs(int idx){// 出口if(sum 0 || sum n) return;// 剪枝if(idx 2 * n){if(sum ! 0) return;ans.push_back(path);return;}// 主体// (path (;sum 1;dfs(idx 1);sum - 1; // 回溯path.pop_back();// )path );sum -1;dfs(idx 1);sum - -1;path.pop_back(); // 回溯}
}; 5.组合
link:77. 组合 - 力扣LeetCode
组合
code
class Solution {
public:int n, k;vectorvectorint ans;vectorint path;vectorbool used;vectorvectorint combine(int _n, int _k) {n _n;k _k;used vectorbool(n, false);dfs();return ans;}void dfs(){// 出口if(path.size() k) {ans.push_back(path);return;}// 主体for(int i 1; i n; i){if(used[i] ) return;// 剪枝 不用continue 保证path有序倒序path.push_back(i);used[i] true;dfs();used[i] false;path.pop_back(); // 回溯}}
}; 6.目标和
link:494. 目标和 - 力扣LeetCode
满足条件的子集
暴力枚举
code
class Solution {
public:int ans 0;int path 0;vectorint nums;int target;int findTargetSumWays(vectorint _nums, int _target) {nums _nums;target _target;// 类似子集问题 key为每个元素取舍/-)dfs(0);return ans;}void dfs(int idx){// 出口if(idx nums.size()){if(path target) ans;return;}// body// path nums[idx];dfs(idx 1);path - nums[idx];// -path -nums[idx];dfs(idx 1);path - -nums[idx];}
}; 7.组合总数
link:39. 组合总和 - 力扣LeetCode
code
class Solution {
public:vectorvectorint ans;vectorint path;int sum 0;int target;vectorint candidates;vectorvectorint combinationSum(vectorint _candidates, int _target) {candidates _candidates;target _target;sort(candidates.begin(), candidates.end());dfs(0);return ans;}void dfs(int bgn)// 只能从[bgn:]中选择下一个 保证path升序{// 出口if(sum target){if(sum target) ans.push_back(path);return;//剪枝}// bodyfor(int i bgn; i candidates.size(); i){sum candidates[i];path.push_back(candidates[i]);dfs(i);path.pop_back();sum - candidates[i];// 回溯}}
}; 8.字母大小写全排列
link:784. 字母大小写全排列 - 力扣LeetCode
code
class Solution {
public:vectorstring ans;string path;vectorstring letterCasePermutation(string _s) {path _s;dfs(0);return ans;}void dfs(int idx){// 出口if(idx path.size()){ans.push_back(path);return;}// bodychar cp path[idx];// 大小写转换if(isalpha(path[idx])){path[idx] toupper(path[idx]);dfs(idx 1);path[idx] tolower(path[idx]);dfs(idx 1);}else dfs(idx 1);path[idx] cp;// 回溯}
};
9.优美的排列
link:526. 优美的排列 - 力扣LeetCode
求满足条件的全排列的个数及时剪枝即可
求满足条件的全排列 及时剪枝
code
class Solution {
public:int ans 0;vectorbool used;int countArrangement(int n) {// 虽然是dfs暴力枚举但只要及时剪枝 复杂度就并不高used vectorbool(n 1, false);dfs(1, n);return ans;}void dfs(int idx, int n){// 出口if(idx n){ans;return;}// bodyfor(int i 1; i n; i){if(used[i] || (i % idx ! 0 idx % i ! 0)) continue;//剪枝used[i] true;dfs(idx 1, n);used[i] false;// 回溯}}
};
10.N皇后
link:51. N 皇后 - 力扣LeetCode
全排列 剪枝
code
class Solution {
public:vectorvectorstring ans;vectorstring path;vectorbool used;unordered_setint set1, set2;vectorvectorstring solveNQueens(int n) {path vectorstring(n, string(n, .));used vectorbool(n, false);dfs(0);return ans;}void dfs(int col){// 出口if(col path.size()){ans.push_back(path);return;}// bodyfor(int i 0; i path.size(); i){if(used[i] || !check(col, i)) continue;// 剪枝set(col, i);path[col][i] Q;dfs(col 1);path[col][i] .;reset(col, i);// 回溯}}void set(int col, int row){used[row] true;set1.insert(colrow);set2.insert(col-row);}void reset(int col, int row){used[row] false;set1.erase(colrow);set2.erase(col-row);}bool check(int col, int row){return (!set1.count(col row)) (!set2.count(col - row));}
};
11.有效的数独
link:36. 有效的数独 - 力扣LeetCode
和dfs没什么关系 就是模拟题 为下题做铺垫
code
class Solution {
public:bool isValidSudoku(vectorvectorchar board) {// rows检查for(vectorchar vc:board){if(repeat(vc)) return false;}// cols检查for(int col 0; col 9; col){vectorchar tmp {};for(int row 0; row 9; row){tmp.push_back(board[row][col]);}if(repeat(tmp)) return false;}// 方块检查for(int row 0; row 9; row3)for(int col 0; col 9; col3){vectorchar tmp {};for(int r 0; r 3; r)for(int c 0; c 3; c){tmp.push_back(board[rowr][colc]);}if(repeat(tmp)) return false;}return true;}bool repeat(vectorchar nums){vectorbool used(10, false);for(char ch:nums){if(ch .) continue;if(used[ch-0]) return true;used[ch-0] true;}return false;}
}; 12.解数独
Link:37. 解数独 - 力扣LeetCode
全排列 剪枝
code
class Solution {
public:vectorvectorchar board;bool row[9][10];bool col[9][10];bool grid[3][3][10];void set(int r, int c, int num){row[r][num] true;col[c][num] true;grid[r / 3][c / 3][num] true;}void reset(int r, int c, int num){row[r][num] false;col[c][num] false;grid[r / 3][c / 3][num] false;}bool check(int r, int c, int num){return (!row[r][num]) (!col[c][num]) (!grid[r / 3][c / 3][num]);}void solveSudoku(vectorvectorchar _board) {memset(row, false, sizeof row);memset(col, false, sizeof col);memset(grid, false, sizeof grid);// 录入已有信息board _board;for(int i 0; i 9; i)for(int j 0; j 9; j){if(board[i][j] .) continue;set(i, j, board[i][j] - 0);}if(!dfs()) printf(error!! 未找到\n);_board board;}bool dfs(){for(int i 0; i 9; i)for(int j 0; j 9; j){if(board[i][j] ! .) continue;for(int num 1; num 9; num){if(check(i, j, num))// 剪枝{set(i, j, num);board[i][j] num 0;if(dfs()) return true;// 及时返回board[i][j] .;reset(i, j, num);// 回溯}}return false;// 剪枝}return true;}}; 13.单词搜索
link:79. 单词搜索 - 力扣LeetCode
dfs枚举 剪枝
注意dfs(i, j, idx)作用再board[i][j]旁边找word[idx]
每次使用dfs前后都要set/reset
code
class Solution {
public:vectorvectorchar board; string word;vectorvectorbool used;vectorpairint, int add {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};bool exist(vectorvectorchar _board, string _word) {board _board;word _word;used vectorvectorbool (board.size(), vectorbool(board[0].size(), false));for(int i 0; i board.size(); i){for(int j 0; j board[0].size(); j){if(board[i][j] ! word[0]) continue;used[i][j] true;if(dfs(i, j, 1)) return true;used[i][j] false;}}return false;}bool dfs(int row, int col, int idx){// 出口if(idx word.size()) return true;// bodyfor(auto[addx, addy] : add){auto[x, y] make_pair(row addx, col addy);if(x 0 || x board.size() || y 0 || y board[0].size() || used[x][y] || board[x][y] ! word[idx]) continue;used[x][y] true;if(dfs(x, y, idx 1)) return true;// 及时上传trueused[x][y] false;// 回溯}return false;}
};
14.黄金矿工
link:1219. 黄金矿工 - 力扣LeetCode
dfs枚举
code
class Solution {
public:int ans 0;int path 0;int getMaximumGold(vectorvectorint grid) {for(int i 0; i grid.size(); i)for(int j 0; j grid[0].size(); j){if(grid[i][j] 0) continue;int cp grid[i][j];path cp;grid[i][j] 0;dfs(i, j, grid);grid[i][j] cp;path - cp;}return ans;}vectorint dx {0, 0, 1, -1};vectorint dy {1, -1, 0, 0};void dfs(int row, int col, vectorvectorint grid){ ans max(ans, path);// 每次更新// bodyfor(int i 0; i 4; i){int x row dx[i], y col dy[i];if(x 0 || x grid.size() || y 0 || y grid[0].size() ||grid[x][y] 0) continue;// 及时判断int cp grid[x][y];grid[x][y] 0;path cp;dfs(x, y, grid);path - cp;grid[x][y] cp; // 回溯}}
}; 15.不同路径III
link:980. 不同路径 III - 力扣LeetCode
dfs枚举
code
class Solution {
public:int ans 0;int path 0;// 已经走过的格子数int m, n;int cnt 0;// -1个数vectorvectorbool used;int uniquePathsIII(vectorvectorint grid) {m grid.size();n grid[0].size();used vectorvectorbool(m, vectorbool(n, false));int x 0, y 0;for(int i 0; i m; i)for(int j 0; j n; j){cnt (grid[i][j] -1);if(grid[i][j] 1){x i;y j;}}used[x][y] true;path 1;dfs(x, y, grid);path - 1;used[x][y] false;return ans;}vectorint dx {0, 0, 1, -1};vectorint dy {1, -1, 0, 0};void dfs(int row, int col, vectorvectorint grid){// 出口if(grid[row][col] 2){if(path m * n - cnt) ans;return;}// bodyfor(int i 0; i 4; i){int x row dx[i], y col dy[i];if(x 0 || x m || y 0 || y n || used[x][y] || grid[x][y] -1) continue;// 剪枝used[x][y] true;path 1;dfs(x, y, grid);path - 1;used[x][y] false;// 回溯}}
};
