目录
1.找出所有子集的异或总和再求和
2.全排列2
3.电话号码的字母组合
4.括号生成
5.组合
6.目标和
1.path作为全局变量
2.path用于传参
7.组合总和
方法一:按照每个空选什么数字进行递归
方法二:按照每个数字选几个进行递归
8.字母大小写全排列
9.优美的排列
10.N皇后问题
11.有效的数独
12.解数独
13.单词搜索
14.黄金矿工
15.不同路径3
1.找出所有子集的异或总和再求和
1863. 找出所有子集的异或总和再求和 - 力扣(LeetCode)
它的决策树是这样子的,也是每个节点都作为一个结果,没有边界条件。 因为异或运算具有重复相消除的性质,因此我们回溯的时候只需要再异或一次即可
class Solution {
public:int mysum = 0;int path;int subsetXORSum(vector<int>& nums) {dfs(nums,0);return mysum;}void dfs(vector<int>& nums, int pos){mysum += path;for(int i = pos; i < nums.size(); i++){path ^= nums[i];dfs(nums, i + 1);path ^= nums[i];}}
};
2.全排列2
.LCR 084. 全排列 II - 力扣(LeetCode)
class Solution {
public:vector<vector<int>> ret;vector<int> path;int check[9];vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return ret;}void dfs(vector<int> nums, int pos){if(pos == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(check[i] == true || (i != 0 && nums[i] == nums[i-1] && check[i-1] == false))continue;else{path.push_back(nums[i]);check[i] = 1;dfs(nums,pos + 1);path.pop_back();check[i] = 0;}}}
};
3.电话号码的字母组合
17. 电话号码的字母组合 - 力扣(LeetCode)
这道题主要是考虑一下数字和字符的映射关系,我们弄一个数组把字符装进去就可以了
class Solution {
public:string hash[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};string path;vector<string> ret;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();}}
};
4.括号生成
LCR 085. 括号生成 - 力扣(LeetCode)
整体代码只需要看一次深搜是怎么样的,就怎么样写就行 ,比如看最左侧那列
class Solution {
public:int left,right;string path;vector<string> ret;vector<string> generateParenthesis(int n) {dfs(n);return ret;}void dfs(int n){if(right == n){ret.push_back(path);return;}//leftleft++;if(left <= n){path += '(';dfs(n);path.pop_back();}left--;right++;if(right <= left){path += ')';dfs(n);path.pop_back();}right--;}
};
5.组合
LCR 080. 组合 - 力扣(LeetCode)
只要递归的时候从下一个位置递归,自然就进行了剪枝 ,即这里的 dfs(n,k,i+1);
class Solution {
public:vector<int> path;vector<vector<int>> ret;vector<vector<int>> combine(int n, int k) {dfs(n,k, 1);return ret;}void dfs(int n,int k, int pos){if(path.size() == k){ret.push_back(path);return;}for(int i = pos; i <= n; i++){path.push_back(i);dfs(n,k,i+1);path.pop_back();}}
};
6.目标和
LCR 102. 目标和 - 力扣(LeetCode)
1.path作为全局变量
class Solution {
public:int ret = 0;int path = 0;int aim;int findTargetSumWays(vector<int>& nums, int target) {aim = target;dfs(nums, 0);return ret;}void dfs(vector<int>& nums ,int pos){if(pos == nums.size()){if(path == aim)ret++;return;}path += nums[pos];dfs(nums, pos + 1);path -= nums[pos];path -= nums[pos];dfs(nums, pos + 1);path += nums[pos];}
};
2.path用于传参
这里因为参数本身的性质,就不需要恢复现场
(当全局变量为int类型时,我们可以把它放进参数里面)
class Solution {
public:int ret = 0;int aim;int findTargetSumWays(vector<int>& nums, int target) {aim = target;int path = 0;dfs(nums, 0 , path);return ret;}void dfs(vector<int>& nums, int pos, int path){if(pos == nums.size()){if(path == aim)ret++;return;}dfs(nums, pos + 1, path + nums[pos]);dfs(nums, pos + 1, path - nums[pos]);}
};
7.组合总和
39. 组合总和 - 力扣(LeetCode)
方法一:按照每个空选什么数字进行递归
因为一个元素可以无限次数地去用,因此递归到下一层的时候仍然可以从当前位置开始继续
即dfs(candidates, i);
临界条件是tmp >= target,要是等于的话可以加入ret,否则直接return即可
class Solution {
public:vector<vector<int>> ret;vector<int> path;int tmp;int target;vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0);return ret;}void dfs(vector<int>& candidates,int pos){if(tmp >= target){if(tmp == target){ret.push_back(path);}return;}for(int i = pos; i < candidates.size(); i++){path.push_back(candidates[i]);tmp += candidates[i];dfs(candidates, i);path.pop_back();tmp -= candidates[i];}}
};
方法二:按照每个数字选几个进行递归
值得注意的是,这里的恢复现场要等这个数字的选择全部结束后再一次性恢复。因为例如选两个,它就是在选一个的基础上再进行选择的
class Solution {
public:vector<vector<int>> ret;vector<int> path;int tmp;int target;vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0);return ret;}void dfs(vector<int>& candidates,int pos){if(tmp >= target){if(tmp == target){ret.push_back(path);}return;}if(pos == candidates.size())return;for(int i = 0; i * candidates[pos] <= target; i++){if(i) {path.push_back(candidates[pos]);tmp += candidates[pos];}dfs(candidates, pos + 1);}for(int i = 1; i * candidates[pos] <= target; i++){path.pop_back();tmp -= candidates[pos];}}
};
8.字母大小写全排列
784. 字母大小写全排列 - 力扣(LeetCode)
这里依照每个位置改变和不改变的分类方式去写代码,但是只有字母字符才能改变,条件判断一下即可
class Solution {
public:string path;vector<string> ret;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;}//不改变path.push_back(s[pos]);dfs(s,pos + 1);path.pop_back();//改变if(s[pos] < '0' || s[pos] > '9'){path.push_back(change(s[pos]));dfs(s,pos + 1);path.pop_back();} }char change(char ch){if(islower(ch))return toupper(ch);else return tolower(ch);}
};
这里则是按照数字和字母的分类去写代码,数字不改变,字母字符有改变和不改变两种状态
class Solution {
public:string path;vector<string> ret;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;}if(s[pos] < '0' || s[pos] > '9'){path.push_back(change(s[pos]));dfs(s,pos + 1);path.pop_back();path.push_back(s[pos]);dfs(s,pos + 1);path.pop_back();} else{path.push_back(s[pos]);dfs(s,pos + 1);path.pop_back();}}char change(char ch){if(islower(ch))return toupper(ch);else return tolower(ch);}
};
9.优美的排列
526. 优美的排列 - 力扣(LeetCode)
class Solution {
public:int ret = 0;int n;int check[16];int countArrangement(int _n) {n = _n;dfs(1);return ret;}void dfs(int pos){if(pos == n + 1){ret++;return;}for(int i = 1; i <= n; i++){if(check[i] == 0 && (i % pos == 0 || pos % i == 0)){check[i] = 1;dfs(pos + 1);check[i] = 0;}}}
};
10.N皇后问题
51. N 皇后 - 力扣(LeetCode)
我们只需要注意剪枝的判断条件即可,我们引入一个坐标系,使用row和i(这里的i实际上就是col)的函数对应关系来标记对角线上是否有皇后。在相减产生负数的时候我们可以同时加上n。
class Solution {
public:bool col[10];bool dig1[20];bool dig2[20];vector<string> pathret;vector<vector<string>> ret;int n;vector<vector<string>> solveNQueens(int _n) {n = _n;dfs(0);return ret;}void dfs(int row){if(row == n){ret.push_back(pathret);}for(int i = 0; i < n; i++){if(col[i] == 0 && dig1[row - i + n] == 0 && dig2[row + i] == 0){string tmp;for(int j = 0; j < n; j++){if(j == i)tmp.push_back('Q');else tmp.push_back('.');}pathret.push_back(tmp);col[i] = 1 ;dig1[row - i + n] = 1 ;dig2[row + i] = 1;dfs(row + 1);pathret.pop_back();col[i] = 0 ;dig1[row - i + n] = 0 ;dig2[row + i] = 0;}}}
};
11.有效的数独
36. 有效的数独 - 力扣(LeetCode)
本题作为解数独前置题目。
本题的关键是剪枝策略,我们用三个数组来表示某行,某列,某个小的3*3方格中有没有某个数字
class Solution {
public:bool row[9][10];bool col[9][10];bool grid[3][3][10];bool isValidSudoku(vector<vector<char>>& board) {for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] == '.')continue;else{int num = board[i][j]-'0';if(row[i][num] || col[j][num] || grid[i/3][j/3][num])return false;else{row[i][num] = col[j][num] = grid[i/3][j/3][num] = 1;}}}}return true;}
};
12.解数独
37. 解数独 - 力扣(LeetCode)
这题的决策树和其它题目没有本质不同
我们的思路是遍历全部的格子,遇到‘.’ 就往里面依次尝试填入数字。
但是有可能填到最后发现这种策略是不行的,因此我们需要让函数有一个返回值帮助我们判断。
当正确填完,就会依次一轮轮返回true。
如果在某种填法下我们发现这种填法最终是不行的,那么我们返回false被最上层接收时,会进行恢复路径,即 board[i][j] = '.';
row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;
当某个空位1-9填入后都不行,那么我们就返回false,说明上层的填值出现了问题。
当我们遍历完所有格子出了循环,那么说明成功填完了,我们就返回true。
class Solution {
public:bool row[9][10];bool col[9][10];bool grid[3][3][10];void solveSudoku(vector<vector<char>>& board) {for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] == '.')continue;else{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))return true;board[i][j] = '.';row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;}}return false;}}}return true;}
};
13.单词搜索
79. 单词搜索 - 力扣(LeetCode)
决策树
这题和解数独那题类似,都需要返回值判断这种情况行不行。
我们首先找到首字符然后进入dfs。在这里我们需要遍历上下左右四个位置来找到下一个位置。为了避免重复遍历,我们仍然需要一个标记数组check【】【】。
解数独那题是遍历完九个数字之后,如果找不到填入的数字那么这种情况不行,返回false。
这题则是遍历完四个位置之后,如果找不到就返回false。每找四周的一个位置都需要重复标记check数组,恢复路径。(这里注意要定义新的变量不能直接改x和y,否则会影响到其它位置)
最终的判断条件是 if(pos == s.size())return true;
class Solution {
public:bool check[10][10];int m, n;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]){check[i][j] = true;if(dfs(board,i,j,word,1))return true;check[i][j]= false;}}}return false;}int dx[4] = {0 , 0, -1, 1};int dy[4] = {1 , -1 ,0 , 0};bool dfs(vector<vector<char>>& board, int x, int y, string s, int pos){if(pos == s.size())return true;for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && check[i][j] == false && board[i][j] == s[pos]){check[i][j] = true;if(dfs(board,i,j,s,pos+1))return true;check[i][j] = false;}}return false;}
};
14.黄金矿工
1219. 黄金矿工 - 力扣(LeetCode)
找到一个非零位置我们就去深度优先去找,因此在大框架里面我们需要遍历一次数组。
仍然需要一个check数组标记是否遍历 ,和单词搜索一样,我们是遍历上下左右四格。
因为这个函数最后一定会走到终点,所以我们不需要返回值来标记情况。
我们用一个参数来记录 金矿的和 这样就不需要恢复现场了。
等到我们从上下左右四格都出来,说明已经走到死路了,这时候把tmpsum加入我们的ret数组即可
class Solution {
public:int check[15][15];int m, n;int dx[4] = {0 , 0, -1, 1};int dy[4] = {1 , -1 ,0 , 0};vector<int> ret;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]){check[i][j] = true;dfs(grid, i, j, grid[i][j]);check[i][j] = false;}}}int maxret = 0;for(int i = 0; i < ret.size(); i++){if(ret[i] >= maxret)maxret = ret[i];}return maxret;}void dfs(vector<vector<int>>& grid, int x, int y,int tmpsum){for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && check[i][j] == false && grid[i][j]){check[i][j] = true;dfs(grid,i,j,tmpsum + grid[i][j]);check[i][j] = false;}}ret.push_back(tmpsum);}
};
15.不同路径3
980. 不同路径 III - 力扣(LeetCode)
代码与黄金矿工等非常类似。我们只需要标记我们遍历一次需要走的步数作为终止条件即可。
我们通过一次遍历,把数字为0或者2的部分加入aimcount即可。
class Solution {
public:int check[25][25];int m, n;int dx[4] = {0 , 0, -1, 1};int dy[4] = {1 , -1 ,0 , 0};int aimcount = 0;int pathcount = 0;int ret = 0;int uniquePathsIII(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();int initx;int inity;for(int i = 0; i < m; i++){for(int j = 0; j < n ; j++){if(grid[i][j] == 0|| grid[i][j] == 2){aimcount++;}else if(grid[i][j] == 1 ){initx = i;inity = j;}}}check[initx][inity] = true;dfs(grid,initx, inity);return ret;}void dfs(vector<vector<int>>& grid, int x, int y){if(grid[x][y] == 2){if(pathcount == aimcount)ret++;return;}for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && check[i][j] == false && grid[i][j] != -1){check[i][j] = true;pathcount++;dfs(grid,i,j);pathcount--;check[i][j] = false;}}}
};