做视频的网站多少钱,为自己家秘方做网站,wordpress网关支付,网页设计作业欣赏目录base code棋盘问题51. N 皇后37. 解数独组合问题77. 组合未剪枝优化剪枝优化216. 组合总和 III未剪枝优化剪枝优化17. 电话号码的字母组合39. 组合总和未剪枝优化剪枝优化40. 组合总和 II,挺重要的#xff0c;涉及到去重了切割问题131. 分割回文串子集问题78. 子集90. 子集… 目录base code棋盘问题51. N 皇后37. 解数独组合问题77. 组合未剪枝优化剪枝优化216. 组合总和 III未剪枝优化剪枝优化17. 电话号码的字母组合39. 组合总和未剪枝优化剪枝优化40. 组合总和 II,挺重要的涉及到去重了切割问题131. 分割回文串子集问题78. 子集90. 子集 II,有树层去重491. 递增子序列也需要数层去重使用unordered_set排列问题46. 全排列47. 全排列 II 数层去重行程安排高级容器的使用现在还没吃透 base code
回溯法大致思路
void backtracking(参数)
{if(终止条件) {存放结果;return;}for(选择本层集合中的元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径选择列表); //递归回溯撤销处理结果}
}棋盘问题
51. N 皇后
https://leetcode-cn.com/problems/n-queens/
class Solution {
private:vectorvectorstring result;
public:bool isValid(int row, int col, vectorstring chessboard, int n){//检查列for(int i 0; i row; i){if(chessboard[i][col] Q) return false;}//检查左上方有无for(int i row - 1,j col - 1; i 0 j 0; i--, j--){if(chessboard[i][j] Q) return false;}//检查右上方有无for(int i row - 1, j col 1; i 0 j n; i--, j){if(chessboard[i][j] Q) return false;}return true;}//n表示棋盘边长row表示当前遍历到第几层了void backtracking(int n, int row, vectorstring chessboard){//当递归到棋盘最底层的时候收集结果if(row n){result.push_back(chessboard);return;}//单层逻辑,递归深度row控制行每一层for循环col控制列for(int col 0; col n; col){if(isValid(row,col,chessboard,n) true){chessboard[row][col] Q; //放置皇后backtracking(n,row1,chessboard);chessboard[row][col] .;}}return ;}vectorvectorstring solveNQueens(int n) {result.clear();//注意一下棋盘的初始化方式vectorstring chessboard(n,string(n,.));backtracking(n,0,chessboard);return result;}
};37. 解数独
https://leetcode-cn.com/problems/sudoku-solver/
class Solution {
public:bool isValid(int row, int col, char val,vectorvectorchar board){//判断同行是否重复for(int i 0; i 9; i){if(board[row][i] val) return false;}//判断同列是否重复for(int i 0; i 9; i){if(board[i][col] val) return false;}//判断9方格里是否重复int startRow (row / 3) * 3;int startCol (col / 3) * 3;for(int i startRow; i startRow 3; i){for(int j startCol; j startCol 3; j){if(board[i][j] val) return false;}}//如果都没错return true;}bool backtracking(vectorvectorchar board){for(int i 0; i board.size(); i){for(int j 0; j board[0].size(); j){//如果已经填入continueif(board[i][j] ! .) continue;for(char k 1; k 9; k) //观察(i,j)这个位置放置k是否合适{if(isValid(i,j,k,board)){board[i][j] k; //放置if(backtracking(board)) return true; //如果找到一组合适的解立刻返回board[i][j] .; //回溯撤销k}}return false; //9个数都试完了都不行返回false;}}return true; //遍历完没有返回false说明找到了合适的棋盘}void solveSudoku(vectorvectorchar board) {backtracking(board);}
};组合问题
77. 组合
未剪枝优化
https://leetcode-cn.com/problems/combinations/ 逻辑树同一层从左向右取数取过的数不再重复取 n相当于树宽k相当于树深度。 每次搜索到叶子节点就找到了一个结果。
class Solution {
private:
vectorvectorint result; //用来存放结果集合
vectorint path; //用来存放结果
public:void backtracking(int n, int k, int startIndex){if(path.size() k){result.push_back(path);return;}//单层逻辑for(int i startIndex; i n; i) //控制树的横向遍历{path.push_back(i);backtracking(n,k,i1); //下一层搜索从i1开始path.pop_back(); //回溯} }vectorvectorint combine(int n, int k) {result.clear();path.clear();backtracking(n,k,1);return result;}
};剪枝优化
单层逻辑中 如果for循环选择的起始位置之后的元素个数已经不足就没有必要再次搜索。 已经选择path.size(),还需要k - path.size(),所以可以这样写
for(int i startIndex; i n -(k - path.size()) 1; i)216. 组合总和 III
https://leetcode-cn.com/problems/combination-sum-iii/
未剪枝优化
class Solution {
public:vectorvectorint result;vectorint path;// 目标和 树深度 当前path路径和 本层起始点 void backtracking(int targetSum, int k, int sum, int startIndex){if(path.size() k) //到达树底部{if(sum targetSum) result.push_back(path);return;}for(int i startIndex; i 9; i){sum i;path.push_back(i);backtracking(targetSum,k,sum,i1);path.pop_back();sum - i;}}vectorvectorint combinationSum3(int k, int n) {result.clear();path.clear();backtracking(n,k,0,1);return result;}
};剪枝优化
如果sum targetSum ,那么往后遍历就没有意义了。于是在backtracking函数一开始加上
if(sum targetSum) return;17. 电话号码的字母组合
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/ 细节 数字与字母的映射.与前两题不同的是本题是求不同集合之间的组合前两题是求同一个集合中的组合。
class Solution {
private:const string letterMap[10] {, //0, //1abc, //2def, //3ghi, //4jkl, //5mno, //6pqrs, //7tuv, //8wxyz, //9
};
public:vectorstring result;string s;void backtracking(const string digits, int index){if(index digits.size()){result.push_back(s);return;}int digit digits[index] - 0;string letters letterMap[digit];for(int i 0; i letters.size(); i){s.push_back(letters[i]);backtracking(digits,index 1); //下一层处理下一个数s.pop_back();}}vectorstring letterCombinations(string digits) {s.clear();result.clear();if(digits.size() 0) return result;backtracking(digits,0);return result;}
};39. 组合总和
https://leetcode-cn.com/problems/combination-sum/ 需要注意的点 组合没有数量要求元素可以无限重复选取。
未剪枝优化
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex){if(sum target) return;if(sum target) {result.push_back(path);return;}for(int i startIndex; i candidates.size(); i){sum candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);path.pop_back();sum - candidates[i];}}vectorvectorint combinationSum(vectorint candidates, int target) {result.clear();path.clear();backtracking(candidates,target,0,0);return result;}
};剪枝优化
对总集合先排序如果本层sum candidates[i] 已经大于target就没有必要再向本层之后的元素遍历了。
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex){if(sum target) return;if(sum target) {result.push_back(path);return;}for(int i startIndex; i candidates.size() candidates[i] sum target; i){sum candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);path.pop_back();sum - candidates[i];}}vectorvectorint combinationSum(vectorint candidates, int target) {result.clear();path.clear();sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);return result;}
};40. 组合总和 II,挺重要的涉及到去重了
这一题和上一题有区别 本题candidates中的每个数字再每个组合中只能用一次并且candidates中有元素是重复的并且解集中不能包含重复的组合。要在搜索的过程中就去掉重复组合。 去重使用过的元素不能重复选取。注意组合问题的逻辑树有两个维度深度和广度 元素在同一个组合内可以重复但是两个组合不能相同显然是树层广度上的去重。 同时注意对于树层去重不需要使用辅助数组。
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex){if(sum target) return;if(sum target){result.push_back(path);return;}for(int i startIndex; i candidates.size() sum candidates[i] target; i){//去重if(i startIndex candidates[i] candidates[i - 1]) continue;sum candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i1);path.pop_back();sum - candidates[i];}}vectorvectorint combinationSum2(vectorint candidates, int target) {result.clear();path.clear();//首先排序sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);return result;}
};切割问题
切割问题类似于组合问题。
131. 分割回文串
https://leetcode-cn.com/problems/palindrome-partitioning/
class Solution {
public:vectorvectorstring result;vectorstring path;bool isHuiWen(const string s,int start,int end){int i start;int j end;while(i j){if(s[i] ! s[j]) return false;i;j--;}return true;}void backtracking(const string s,int startIndex){if(startIndex s.size()){result.push_back(path);return;}for(int i startIndex; i s.size(); i){//如果是回文子串if(isHuiWen(s,startIndex,i)){//获取子串string str s.substr(startIndex,i - startIndex 1);path.push_back(str);backtracking(s,i1);path.pop_back();}}}vectorvectorstring partition(string s) {result.clear();path.clear();backtracking(s,0);return result;}
};子集问题
子集问题也是一种组合问题。不过不同的是组合问题是在到达叶子节点时候才将path送入result。而子集问题每次进入这一层就要把path加入result这才是子集。
78. 子集
https://leetcode-cn.com/problems/subsets/
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex){//result.push_back(path);if(startIndex nums.size()) return;for(int i startIndex; i nums.size(); i){path.push_back(nums[i]);backtracking(nums,i1);path.pop_back();}}vectorvectorint subsets(vectorint nums) {result.clear();path.clear();backtracking(nums,0);return result;}
};90. 子集 II,有树层去重
https://leetcode-cn.com/problems/subsets-ii/ 比之前加上一个树层去重
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex){//result.push_back(path);if(startIndex nums.size()) return;for(int i startIndex; i nums.size(); i){//树层去重if(i startIndex nums[i-1] nums[i]) continue;path.push_back(nums[i]);backtracking(nums,i1);path.pop_back();}}vectorvectorint subsetsWithDup(vectorint nums) {result.clear();path.clear();sort(nums.begin(),nums.end());backtracking(nums,0);return result;}
};491. 递增子序列也需要数层去重使用unordered_set
https://leetcode-cn.com/problems/increasing-subsequences/ 去重逻辑 1、使用unordered_set用来记录本层元素是否重复重复则continue 2、观察待插入的元素nums[i]是否是比path尾部元素大等的否则构成不了递增序列。
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex){//子序列长度2if(path.size() 1)result.push_back(path);if(startIndex nums.size()) return;unordered_setint uset;for(int i startIndex; i nums.size(); i){//树层去重if(!path.empty() nums[i] path.back()) continue;if(uset.find(nums[i]) ! uset.end()) continue;uset.insert(nums[i]);path.push_back(nums[i]);backtracking(nums,i1);path.pop_back();}}vectorvectorint findSubsequences(vectorint nums) {result.clear();path.clear();backtracking(nums,0);return result;}
};排列问题
46. 全排列
https://leetcode-cn.com/problems/permutations/ 与组合的区别在于for循环从0开始但是需要注意取过的元素不能再取这里使用used数组进行记录。
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums, vectorbool used){if(path.size() nums.size()) {result.push_back(path);return;}for(int i 0; i nums.size(); i){//用过的元素不需要使用if(used[i] true) continue;used[i] true;path.push_back(nums[i]);backtracking(nums,used);path.pop_back();used[i] false;}}vectorvectorint permute(vectorint nums) {result.clear();path.clear();vectorbool used(nums.size(),false);backtracking(nums,used);return result;}
};47. 全排列 II 数层去重
https://leetcode-cn.com/problems/permutations-ii/
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums, vectorbool used){if(path.size() nums.size()) {result.push_back(path);return;}for(int i 0; i nums.size(); i){//去重,同一层nums[i-1]使用过的话直接跳过if(i 0 nums[i] nums[i-1] used[i-1] true) continue;//用过的元素不需要使用if(used[i] true) continue;used[i] true;path.push_back(nums[i]);backtracking(nums,used);path.pop_back();used[i] false;}}vectorvectorint permuteUnique(vectorint nums) {result.clear();path.clear();sort(nums.begin(),nums.end());vectorbool used(nums.size(),false);backtracking(nums,used);return result;}
};行程安排高级容器的使用现在还没吃透
https://leetcode-cn.com/problems/reconstruct-itinerary/ 还得再多看看。
class Solution {
public://unordered_map出发机场,map到达机场,航班次数 targets;unordered_mapstring,mapstring,int targets;//还有多少航班 tickets//由于只需要找到一个行程所以找到直接返回使用bool正好bool backtracking(int ticketNum,vectorstring result){if(result.size() ticketNum 1) return true;for(pairconst string,int target : targets[result[result.size() - 1]]){if(target.second 0) {result.push_back(target.first);target.second--;if(backtracking(ticketNum,result)) return true;result.pop_back();target.second;}}return false;}vectorstring findItinerary(vectorvectorstring tickets) {targets.clear();vectorstring result;//初始化targetsfor(const vectorstring vec : tickets){targets[vec[0]][vec[1]]; //记录映射关系}result.push_back(JFK); //起始机场backtracking(tickets.size(),result);return result;}
};
