devbox
空白诗007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

day 9 回溯算法

作者：空白诗007 | 2024-08-09 06:59:41

赞

踩

day 9 回溯算法

77. 组合

  1. class Solution {
  2. public:
  3.     vector<int> path;
  4.     vector<vector<int>> res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(int n,int k,int startIndex){
  7.         //确定终止条件
  8.         if(path.size()==k){
  9.             res.push_back(path);
  10.             return;
  11.         }
  12.  
  13.         //确定单层递归逻辑
  14.         for(int i=startIndex;i<=n;i++){
  15.             path.push_back(i);
  16.             backtracking(n,k,i+1);
  17.             path.pop_back();
  18.         }
  19.     }
  20.     vector<vector<int>> combine(int n, int k) {
  21.         backtracking(n,k,1);
  22.         return res;
  23.     }
  24. };

剪枝优化：（对每层循环遍历的范围进行了缩小）

  1. class Solution {
  2. public:
  3.     vector<int> path;
  4.     vector<vector<int>> res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(int n,int k,int startIndex){
  7.         //确定终止条件
  8.         if(path.size()==k){
  9.             res.push_back(path);
  10.             return;
  11.         }
  12.  
  13.         //确定单层递归逻辑
  14.         for(int i=startIndex;i<=n-(k-path.size())+1;i++){//优化的地方
  15.             path.push_back(i);
  16.             backtracking(n,k,i+1);
  17.             path.pop_back();
  18.         }
  19.     }
  20.     vector<vector<int>> combine(int n, int k) {
  21.         backtracking(n,k,1);
  22.         return res;
  23.     }
  24. };

216. 组合总和 III

  1. class Solution {
  2. public:
  3.     vector<int>path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(int k,int n,int startIndex){
  7.         //确定终止条件
  8.         if(path.size()==k){
  9.             if(n==0){
  10.                 res.push_back(path);
  11.                 return;
  12.             }
  13.         }
  14.  
  15.         //确定单层递归逻辑
  16.         for(int i=startIndex;i<=9;i++){
  17.             n-=i;
  18.             path.push_back(i);
  19.             backtracking(k,n,i+1);
  20.             path.pop_back();
  21.             n+=i;
  22.         }
  23.     }
  24.     vector<vector<int>> combinationSum3(int k, int n) {
  25.         backtracking(k,n,1);
  26.         return res;
  27.     }
  28. };

剪枝优化：

1.目标数n一直在随i的加入减小，如果目标数n已经<0，那么剪枝。即path中的数已经大于目标数了。

2.对for循环i的遍历范围进行缩小

  1. class Solution {
  2. public:
  3.     vector<int>path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(int k,int n,int startIndex){
  7.         //优化：剪枝
  8.         if(n<0) return;
  9.         //确定终止条件
  10.         if(path.size()==k){
  11.             if(n==0){
  12.                 res.push_back(path);
  13.                 return;
  14.             }
  15.         }
  16.  
  17.         //确定单层递归逻辑
  18.         for(int i=startIndex;i<=10-(k-path.size());i++){//剪枝 优化
  19.             n-=i;
  20.             path.push_back(i);
  21.             backtracking(k,n,i+1);
  22.             path.pop_back();
  23.             n+=i;
  24.         }
  25.     }
  26.     vector<vector<int>> combinationSum3(int k, int n) {
  27.         backtracking(k,n,1);
  28.         return res;
  29.     }
  30. };

17. 电话号码的字母组合
 

  1. class Solution {
  2. public:
  3.     const string letterMap[10]={
  4.         "",
  5.         "",
  6.         "abc",
  7.         "def",
  8.         "ghi",
  9.         "jkl",
  10.         "mno",
  11.         "pqrs",
  12.         "tuv",
  13.         "wxyz",
  14.     };
  15.     vector<string> res;
  16.     string s;
  17.     //确定递归函数参数和返回值
  18.     void backtracing(const string& digits,int index){
  19.         //确定终止条件
  20.         if(index==digits.size()){
  21.             res.push_back(s);
  22.             return;
  23.         }
  24.  
  25.         //确定单层递归逻辑
  26.             int num=digits[index]-'0';
  27.         //string str=letterMap[num];
  28.         string strr=letterMap[num];
  29.         for(int i=0;i<strr.size();i++){
  30.             s.push_back(strr[i]);
  31.             backtracing(digits,index+1);
  32.             s.pop_back();
  33.         }
  34.         
  35.     }
  36.     vector<string> letterCombinations(string digits) {
  37.         if(digits.size()==0){
  38.             return res;
  39.         }
  40.         backtracing(digits,0);
  41.         return res;
  42.     }
  43. };

39. 组合总和

  1. class Solution {
  2. public:
  3.     vector<int> path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(vector<int>& candidates,int target,int startIndex){
  7.         //确定终止条件
  8.         if(target<0) return;
  9.         if(target==0) {
  10.             res.push_back(path);
  11.             return;
  12.         }
  13.  
  14.         //确定单层递归逻辑
  15.         for(int i=startIndex;i<candidates.size();i++){
  16.             target-=candidates[i];
  17.             path.push_back(candidates[i]);
  18.             backtracking(candidates,target,i);
  19.             target+=candidates[i];
  20.             path.pop_back();
  21.         }
  22.     }
  23.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  24.         backtracking(candidates,target,0);
  25.         return res;
  26.     }
  27. };

优化：（剪枝）

优化后的比之前的在叶子结点少递归一层。在排序candidates后，碰到target<0的情况直接结束本层的遍历，后面没遍历到的也不用遍历了。

  1. class Solution {
  2. public:
  3.     vector<int> path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(vector<int>& candidates,int target,int startIndex){
  7.         //确定终止条件
  8.         if(target==0) {
  9.             res.push_back(path);
  10.             return;
  11.         }
  12.  
  13.         //确定单层递归逻辑
  14.         for(int i=startIndex;i<candidates.size()&&target-candidates[i]>=0;i++){
  15.             target-=candidates[i];
  16.             path.push_back(candidates[i]);
  17.             backtracking(candidates,target,i);
  18.             target+=candidates[i];
  19.             path.pop_back();
  20.         }
  21.     }
  22.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  23.         sort(candidates.begin(),candidates.end());
  24.         backtracking(candidates,target,0);
  25.         return res;
  26.     }
  27. };

40. 组合总和 II

  1. class Solution {
  2. public:
  3.     vector<int>path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(vector<int>& candidates,int target,vector<bool>st,int startIndex){
  7.         //确定终止条件
  8.         if(target<0)return;
  9.         if(target==0){
  10.             res.push_back(path);
  11.             return;
  12.         }
  13.         
  14.         //确定单层递归逻辑
  15.         for(int i=startIndex;i<candidates.size();i++){
  16.             if(i>0&&candidates[i]==candidates[i-1]&&st[i-1]==false){
  17.                 continue;
  18.             }//对组合去重
  19.             path.push_back(candidates[i]);
  20.             st[i]=true;
  21.             target-=candidates[i];
  22.             backtracking(candidates,target,st,i+1);
  23.             path.pop_back();
  24.             st[i]=false;
  25.             target+=candidates[i];
  26.         }
  27.     }
  28.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  29.         vector<bool>st(candidates.size(),false);
  30.         sort(candidates.begin(),candidates.end());
  31.         backtracking(candidates,target,st,0);
  32.         return res;
  33.     }
  34. };

131. 分割回文串

  1. class Solution {
  2. public:
  3.     //确定是否是回文
  4.     bool isTrue(string s,int start,int end){
  5.         for(int i=start,j=end;i<j;){
  6.             if(s[i]!=s[j]){
  7.                 return false;
  8.             }
  9.             else {
  10.                 i++;
  11.                 j--;
  12.             }
  13.         }
  14.         return true;
  15.     }
  16.     //确定递归函数参数和返回值
  17.     void backtracking(vector<string>& path,vector<vector<string>>& res,int startIndex,string s){
  18.         //确定终止条件
  19.         if(startIndex==s.size()){
  20.             res.push_back(path);
  21.             return;
  22.         }
  23.         //确定单层递归逻辑
  24.         for(int i=startIndex;i<s.size();i++){
  25.             if(isTrue(s,startIndex,i)){
  26.                 string str=s.substr(startIndex,i-startIndex+1);
  27.                 path.push_back(str);
  28.             }
  29.             else{
  30.                 continue;
  31.             }
  32.             backtracking(path,res,i+1,s);
  33.             path.pop_back();
  34.         }
  35.     }
  36.     vector<vector<string>> partition(string s) {
  37.         vector<string>path;
  38.         vector<vector<string>>res;
  39.         backtracking(path,res,0,s);
  40.         return res;
  41.     }
  42. };

93. 复原 IP 地址

  1. class Solution {
  2. public:
  3.     //确判断是否符合ip地址
  4.     bool isTrue(string s,int start,int end){
  5.         if(start>end) return false;
  6.         if(s[start]=='0'&&start!=end) return false;
  7.         int num=0;
  8.         for(int i=start;i<=end;i++){
  9.             if(s[i]<'0'||s[i]>'9') return false;
  10.             num=num*10+(s[i]-'0');
  11.             if(num>255)return false;
  12.         }
  13.         return true;
  14.     }
  15.     //确定递归函数参数和返回值
  16.     void backtracking(string &s,int startIndex,int pointNum,vector<string>&res){
  17.         //确定终止条件
  18.         if(pointNum==3){
  19.             if(isTrue(s,startIndex,s.size()-1)){
  20.                 res.push_back(s);
  21.             }
  22.             return;
  23.         }
  24.         //确定单层递归逻辑
  25.         for(int i=startIndex;i<s.size();i++){
  26.             if(isTrue(s,startIndex,i)){
  27.                 s.insert(s.begin()+i+1,'.');
  28.                 pointNum+=1;
  29.                 backtracking(s,i+2,pointNum,res);
  30.                 pointNum-=1;
  31.                 s.erase(s.begin()+i+1);
  32.             }
  33.             else break;
  34.         }
  35.     }
  36.     vector<string> restoreIpAddresses(string s) {
  37.         vector<string>res;
  38.         if(s.size()<4||s.size()>12) return res;
  39.         backtracking(s,0,0,res);
  40.         return res;
  41.     }
  42. };

78. 子集

  1. class Solution {
  2. public:
  3.     vector<int>path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(int startIndex,vector<int>nums){
  7.         res.push_back(path);//不会漏掉自己，空集
  8.         //确定终止条件
  9.         if(startIndex>=nums.size()) return;
  10.  
  11.         //确定单层递归逻辑
  12.         for(int i=startIndex;i<nums.size();i++){
  13.             path.push_back(nums[i]);
  14.             backtracking(i+1,nums);
  15.             path.pop_back();
  16.  
  17.         }
  18.     }
  19.     vector<vector<int>> subsets(vector<int>& nums) {
  20.         backtracking(0,nums);
  21.         return res;
  22.     }
  23. };

90. 子集 II

  1. class Solution {
  2. public:
  3.     vector<int>path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(vector<int>nums,int startIndex,vector<bool>&st){
  7.         res.push_back(path);
  8.         //确定终止条件
  9.         if(startIndex>=nums.size())return;
  10.  
  11.         //确定单层递归逻辑
  12.         for(int i=startIndex;i<nums.size();i++){
  13.             if(i>0&&nums[i]==nums[i-1]&&st[i-1]==false){
  14.                 continue;
  15.             }
  16.             path.push_back(nums[i]);
  17.             st[i]=true;
  18.             backtracking(nums,i+1,st);
  19.             path.pop_back();
  20.             st[i]=false;
  21.         }
  22.     }
  23.     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  24.         vector<bool> st(nums.size(),false);
  25.         sort(nums.begin(),nums.end());
  26.         backtracking(nums,0,st);
  27.         return res;
  28.     }
  29. };

也可以不用st数组去重

  1. class Solution {
  2. public:
  3.     vector<int>path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(vector<int>nums,int startIndex){
  7.         res.push_back(path);
  8.         //确定终止条件
  9.         if(startIndex>=nums.size())return;
  10.  
  11.         //确定单层递归逻辑
  12.         for(int i=startIndex;i<nums.size();i++){
  13.             if(i>startIndex&&nums[i]==nums[i-1]){
  14.                 continue;
  15.             }
  16.             path.push_back(nums[i]);
  17.             backtracking(nums,i+1);
  18.             path.pop_back();
  19.         }
  20.     }
  21.     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  22.         sort(nums.begin(),nums.end());
  23.         backtracking(nums,0);
  24.         return res;
  25.     }
  26. };

491. 非递减子序列

  1. class Solution {
  2. public:
  3.     vector<int>path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(vector<int>& nums,int startIndex){
  7.         if(path.size()>1){
  8.             res.push_back(path);
  9.         }
  10.         //确定终止条件
  11.         if(startIndex>=nums.size()){
  12.             return;
  13.         }
  14.  
  15.         //确定单层递归逻辑
  16.         unordered_set<int> uset;//对每层去重
  17.         for(int i=startIndex;i<nums.size();i++){
  18.             if((!path.empty()&&nums[i]<path.back())||uset.find(nums[i])!=uset.end()){
  19.                 continue;
  20.             }
  21.             uset.insert(nums[i]);//记录该元素在本层用过了，之后的相同元素不再使用
  22.             path.push_back(nums[i]);
  23.             backtracking(nums,i+1);
  24.             path.pop_back();
  25.         }
  26.     }
  27.     vector<vector<int>> findSubsequences(vector<int>& nums) {
  28.         backtracking(nums,0);
  29.         return res;
  30.     }
  31. };

利用数组去重，因为题目的数值范围小，所以可以尽量使用。

  1. class Solution {
  2. public:
  3.     vector<int>path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(vector<int>& nums,int startIndex){
  7.         if(path.size()>1){
  8.             res.push_back(path);
  9.         }
  10.         //确定终止条件
  11.         if(startIndex>=nums.size()){
  12.             return;
  13.         }
  14.  
  15.         //确定单层递归逻辑
  16.         int st[201]={0};//对每层去重
  17.         for(int i=startIndex;i<nums.size();i++){
  18.             if((!path.empty()&&nums[i]<path.back())||st[nums[i]+100]==1){
  19.                 continue;
  20.             }
  21.             st[nums[i]+100]=1;;//记录该元素在本层用过了，之后的相同元素不再使用
  22.             path.push_back(nums[i]);
  23.             backtracking(nums,i+1);
  24.             path.pop_back();
  25.         }
  26.     }
  27.     vector<vector<int>> findSubsequences(vector<int>& nums) {
  28.         backtracking(nums,0);
  29.         return res;
  30.     }
  31. };

46. 全排列

  1. class Solution {
  2. public:
  3.     vector<int>path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(vector<int>& nums,vector<bool>& st){
  7.         //确定终止条件
  8.         if(path.size()==nums.size()){
  9.             res.push_back(path);
  10.             return;
  11.         }
  12.         //确定单层递归逻辑
  13.         for(int i=0;i<nums.size();i++){
  14.             if(st[i]==true) continue;
  15.             st[i]=true;
  16.             path.push_back(nums[i]);
  17.             backtracking(nums,st);
  18.             path.pop_back();
  19.             st[i]=false;
  20.         }
  21.     }
  22.     vector<vector<int>> permute(vector<int>& nums) {
  23.         vector<bool> st(nums.size(),false);
  24.         backtracking(nums,st);
  25.         return res;
  26.     }
  27. };

47. 全排列 II

  1. class Solution {
  2. public:
  3.     vector<int>path;
  4.     vector<vector<int>>res;
  5.     //确定递归函数参数和返回值
  6.     void backtracking(vector<int>& nums,vector<bool>& st){
  7.         //确定终止条件
  8.         if(path.size()==nums.size()){
  9.             res.push_back(path);
  10.             return;
  11.         }
  12.         //确定单层递归逻辑
  13.         for(int i=0;i<nums.size();i++){
  14.             if(i>0&&nums[i]==nums[i-1]&&st[i-1]==false){
  15.                 continue;//树层去重的
  16.             }
  17.             if(st[i]==true) continue;//树枝去重
  18.             st[i]=true;
  19.             path.push_back(nums[i]);
  20.             backtracking(nums,st);
  21.             path.pop_back();
  22.             st[i]=false;
  23.         }
  24.     }
  25.     vector<vector<int>> permuteUnique(vector<int>& nums) {
  26.         vector<bool>st(nums.size(),false);
  27.         sort(nums.begin(),nums.end());
  28.         backtracking(nums,st);
  29.         return res;
  30.     }
  31. };

332. 重新安排行程

  1. class Solution {
  2. public:
  3.     //unordered_map<出发机场,map<到达机场,航班次数>>targets;
  4.     unordered_map<string,map<string,int>>targets;
  5.     //确定递归函数参数和返回值
  6.     bool backtracking(int ticketNum,vector<string>& res){
  7.         //确定终止条件
  8.         if(res.size()==ticketNum+1){
  9.             return true;
  10.         }
  11.         //确定单层递归逻辑
  12.         for(pair<const string, int>&target:targets[res[res.size()-1]]){
  13.             if(target.second>0){//记录到达机场是否飞过了
  14.                 res.push_back(target.first);
  15.                 target.second--;
  16.                 if(backtracking(ticketNum,res)) return true;
  17.                 res.pop_back();
  18.                 target.second++;
  19.             }
  20.         }
  21.         return false;
  22.     }
  23.     vector<string> findItinerary(vector<vector<string>>& tickets) {
  24.         vector<string>res;
  25.         for(const vector<string>& vec:tickets){
  26.             targets[vec[0]][vec[1]]++;//记录映射关系
  27.  
  28.         }
  29.         res.push_back("JFK");
  30.         backtracking(tickets.size(),res);
  31.         return res;
  32.     }
  33. };

51. N 皇后

  1. class Solution {
  2. public:
  3.     vector<vector<string>>res;
  4.     //判断位置是否合法
  5.     bool isValid(int n,int col,int row,vector<string>& chessBorad){
  6.         //同一列
  7.         for(int i=row-1;i>=0;i--){
  8.             if(chessBorad[i][col]=='Q')return false;
  9.         }
  10.         //东北夹角
  11.         for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
  12.             if(chessBorad[i][j]=='Q') return false;
  13.         }
  14.         //西北夹角
  15.         for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
  16.             if(chessBorad[i][j]=='Q') return false;
  17.         }
  18.         return true;
  19.     }
  20.     //确定递归函数参数和返回值
  21.     void backtracking(int n,int row,vector<string>& chessBorad){
  22.         //确定终止条件
  23.         if(n==row){
  24.             res.push_back(chessBorad);
  25.             return ;
  26.         }
  27.  
  28.         //确定单层递归逻辑
  29.         for(int col=0;col<n;col++){
  30.             if(!isValid(n,col,row,chessBorad)){
  31.                 continue;
  32.             }
  33.             else{
  34.                 chessBorad[row][col]='Q';
  35.                 backtracking(n,row+1,chessBorad);
  36.                 chessBorad[row][col]='.';
  37.             }
  38.         }
  39.  
  40.     }
  41.     vector<vector<string>> solveNQueens(int n) {
  42.         vector<string> chessBorad(n,string(n,'.'));
  43.         backtracking(n,0,chessBorad);
  44.         return res;
  45.     }
  46. };

37. 解数独

  1. class Solution {
  2. public:
  3.     bool isValid(int row,int col,char val,vector<vector<char>>& board){
  4.         //行判断
  5.         for(int i=0;i<9;i++){
  6.             if(board[row][i]==val) return false;
  7.         }
  8.         //列判断
  9.         for(int i=0;i<9;i++){
  10.             if(board[i][col]==val) return false;
  11.         }   
  12.         //九宫格内判断
  13.         row=(row/3)*3;
  14.         col=(col/3)*3;
  15.         for(int i=row;i<row+3;i++){
  16.             for(int j=col;j<col+3;j++){
  17.                 if(board[i][j]==val) return false;
  18.             }
  19.         }
  20.         return true;
  21.     }
  22.     bool backtracking(vector<vector<char>>& board){
  23.         //不需要单独的终止条件，不需要收集结果
  24.         //确定单层递归逻辑
  25.         for(int row=0;row<board.size();row++){
  26.             for(int col=0;col<board[0].size();col++){
  27.                 if(board[row][col]=='.'){
  28.                     for(char val='1';val<='9';val++){
  29.                         if(isValid(row,col,val,board)){
  30.                             board[row][col]=val;
  31.                             if(backtracking(board)) return true;
  32.                             board[row][col]='.';
  33.                         }
  34.                     }
  35.                     return false;
  36.                 }
  37.             }
  38.         }
  39.         return true;
  40.     }
  41.     void solveSudoku(vector<vector<char>>& board) {
  42.         backtracking(board);
  43.     }
  44. };

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号