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

day-27 代码随想录算法训练营（19）回溯part03

作者：IT小白 | 2024-03-02 22:51:32

赞

踩

day-27 代码随想录算法训练营（19）回溯part03

39.组合总和

分析：同一个数可以选多次，但是不能有重复的答案；
思路：横向遍历，纵向递归（不同的是递归的时候不需要跳到下一个位置，因为同一个数可以选多次）
  1. class Solution {
  2. public:
  3.     vector<vector<int>>res;
  4.     vector<int>mids;
  5.     void backtrace(vector<int>&candidates,int start,int sum,int target){
  6.         if(sum>=target){//终止条件
  7.             if(sum==target)//目标条件
  8.                 res.push_back(mids);
  9.             return;
  10.         }
  11.  
  12.         for(int i=start;i<candidates.size();i++){
  13.             mids.push_back(candidates[i]);
  14.             sum+=candidates[i];
  15.             backtrace(candidates,i,sum,target);//因为同一个数可以选多次，所以递归为i
  16.             mids.pop_back();
  17.             sum-=candidates[i];
  18.         }
  19.     }
  20.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  21.         backtrace(candidates,0,0,target);
  22.         return res;
  23.     }
  24. };

 40.组合总和||

思路：重点在于去重
去重：树层去重，需要在递归遍历的时候判断是否重复
  1. class Solution {
  2. public:
  3.     vector<vector<int>>res;
  4.     vector<int>mids;
  5.     void backtrace(vector<int>&candidates,int startIndex,int sum,int target,vector<bool>&used){
  6.         if(sum==target){
  7.             res.push_back(mids);
  8.             return;
  9.         }
  10.         //剪枝
  11.         for(int i=startIndex;i<candidates.size() && sum+candidates[i]<=target;i++){
  12.             if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==false)//树层去重
  13.                 continue;
  14.             mids.push_back(candidates[i]);
  15.             sum+=candidates[i];
  16.             used[i]=true;
  17.             backtrace(candidates,i+1,sum,target,used);
  18.             used[i]=false;
  19.             mids.pop_back();
  20.             sum-=candidates[i];
  21.             
  22.         }
  23.     }
  24.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  25.         sort(candidates.begin(),candidates.end());
  26.         vector<bool>used(candidates.size(),false);
  27.         backtrace(candidates,0,0,target,used);
  28.         return res;
  29.     }
  30. };

 131.分割回文串

思路：分割字符串，然后多了一个判断是否回文的操作
  1. class Solution {
  2. public:
  3.     vector<vector<string>>res;
  4.     vector<string>mids;
  5.     bool judge(const string& s,int left,int right){
  6.         while(left<right){
  7.             if(s[left]!=s[right]) return false;
  8.             left++;
  9.             right--;
  10.         }
  11.         return true;
  12.     }
  13.     void backtrace(string&s,int startIndex){
  14.         if(startIndex>=s.size()){
  15.             res.push_back(mids);
  16.             return;
  17.         }
  18.  
  19.         for(int i=startIndex;i<s.size();i++){
  20.             if(!judge(s,startIndex,i)) continue;//判断是否回文串
  21.             string str=s.substr(startIndex,i-startIndex+1);
  22.             mids.push_back(str);
  23.             backtrace(s,i+1);
  24.             mids.pop_back();
  25.         }
  26.  
  27.  
  28.     }
  29.     vector<vector<string>> partition(string s) {
  30.         backtrace(s,0);
  31.         return res;
  32.     }
  33. };

78.子集

画图分析：

 思路：横向遍历，每次遍历的时候都进行一次添加，然后进行纵向递归，递归完之后进行回溯。
  • 注意：空集也是子集。（所有节点都需要添加）
  1. class Solution {
  2. public:
  3.     vector<vector<int>>res;
  4.     vector<int>mid;
  5.     void backtrace(vector<int>&nums,int start){
  6.         res.push_back(mid);
  7.         if(start==nums.size()){
  8.             //res.push_back(mid);
  9.             return;
  10.         }
  11.         for(int i=start;i<nums.size();i++){
  12.             mid.push_back(nums[i]);
  13.             backtrace(nums,i+1);
  14.             mid.pop_back();
  15.         }
  16.  
  17.     }
  18.     vector<vector<int>> subsets(vector<int>& nums) {
  19.         backtrace(nums,0);
  20.         return res;
  21.     }
  22. };

90.子集||

分析：和上题一样，区别在于有重复数字
思路：组合问题有重复都考虑先排序再操作！
  1. class Solution {
  2. public:
  3.     vector<vector<int>>res;
  4.     vector<int>mid;
  5.     void backtrace(vector<int>&nums,int start){
  6.         if(find(res.begin(),res.end(),mid)==res.end())//去重
  7.             res.push_back(mid);
  8.         if(start==nums.size())
  9.             return;
  10.         
  11.         for(int i=start;i<nums.size();i++){
  12.             
  13.             mid.push_back(nums[i]);
  14.             backtrace(nums,i+1);
  15.             mid.pop_back();
  16.         }
  17.     }
  18.     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  19.         sort(nums.begin(),nums.end());//需要排序
  20.         backtrace(nums,0);
  21.         return res;
  22.     }
  23. };

491.递增子序列

思路：重点在于set去重以及递增条件
  1. class Solution {
  2. public:
  3.     vector<vector<int>>midRes,res;
  4.     vector<int>mid;
  5.     void backtrace(vector<int>&nums,int start){
  6.         if(mid.size()>=2 ){//条件限制
  7.             midRes.push_back(mid);
  8.         }
  9.         if(start==nums.size())//终止条件
  10.             return;
  11.         unordered_set<int> vistedSet;
  12.         for(int i=start;i<nums.size();i++){
  13.             if(vistedSet.find(nums[i])!=vistedSet.end())//去重
  14.                 continue;
  15.             if(!mid.empty() && mid.back()>nums[i])//递增条件
  16.                 continue;
  17.             //judge[nums[i]]=true;
  18.             vistedSet.insert(nums[i]);//遍历标记
  19.             mid.push_back(nums[i]);
  20.             backtrace(nums,i+1);
  21.             mid.pop_back();//回溯
  22.         }
  23.     }
  24.     vector<vector<int>> findSubsequences(vector<int>& nums) {
  25.         backtrace(nums,0);
  26.         return midRes;
  27.     }
  28. };

46.全排列

思路：跟子集的代码几乎一样，主要区别在于
  • 每次遍历都从0开始，并且做树枝去重
  1. class Solution {
  2. public:
  3.     vector<vector<int>>res;
  4.     vector<int>mid;
  5.     void backtrace(vector<int>&nums,int start){
  6.         if(start==nums.size()){
  7.             res.push_back(mid);
  8.         }
  9.         for(int i=0;i<nums.size();i++){
  10.             if(find(mid.begin(),mid.end(),nums[i])!=mid.end())//树枝去重
  11.                 continue;
  12.             mid.push_back(nums[i]);
  13.             backtrace(nums,start+1);
  14.             mid.pop_back();
  15.         }
  16.     }
  17.     //树枝去重
  18.     vector<vector<int>> permute(vector<int>& nums) {
  19.         backtrace(nums,0);
  20.         return res;
  21.     }
  22. };

47.全排列||

思路一：使用哈希表进行树枝下标去重（因为有重复元素）
问题：在数组去重时时间复杂度过高
  1. class Solution {
  2. public:
  3.     vector<vector<int>>res;
  4.     vector<int>mid;
  5.     unordered_map<int,bool>map;
  6.     void backtrace(vector<int>&nums,int start){
  7.         if(start==nums.size()){
  8.             if(find(res.begin(),res.end(),mid)==res.end())//数组去重
  9.                 res.push_back(mid);
  10.             return;
  11.         }
  12.  
  13.         for(int i=0;i<nums.size();i++){
  14.             if(map[i])//树枝去重
  15.                 continue;
  16.             mid.push_back(nums[i]);
  17.             map[i]=true;
  18.             backtrace(nums,start+1);
  19.             mid.pop_back();
  20.             map[i]=false;
  21.         }
  22.     }
  23.     vector<vector<int>> permuteUnique(vector<int>& nums) {
  24.         //sort(nums.begin(),nums.end());
  25.         backtrace(nums,0);
  26.         return res;
  27.     }
  28. };

323.重新安排行程 

思路：首先记录航班的映射关系，然后从起点开始根据映射关系一一添加（横向遍历，纵向递归）
注意：
  • 起点航班要先添加
  • 如果添加的路线等于航班数+1时，说明已经走完全部航班（如五个航班，必然是六个站点）
  • 递归深入的时候需要判断当前映射关系是否被添加过
  1. class Solution {
  2. public:
  3.     unordered_map<string,map<string,int>>targets;
  4.     vector<string>midres;
  5.     bool backtrace(vector<vector<string>>& tickets){
  6.         if(midres.size()==tickets.size()+1)//航班已经走完的终止条件
  7.             return true;
  8.         
  9.         for(pair<const string,int>&target:targets[midres[midres.size()-1]]){//遍历映射关系
  10.             if(target.second>0){//当映射关系还存在时
  11.                 midres.push_back(target.first);
  12.                 target.second--;
  13.                 if(backtrace(tickets)) return true;//已经找到一条路线
  14.                 midres.pop_back();
  15.                 target.second++;
  16.             }
  17.         }
  18.         return false;
  19.     }
  20.     vector<string> findItinerary(vector<vector<string>>& tickets) {
  21.         midres.push_back("JFK");//先添加起点航班
  22.         for(auto it:tickets)
  23.             targets[it[0]][it[1]]++;//记录映射关系
  24.         backtrace(tickets);
  25.         return midres;
  26.     }
  27. };

51.N皇后

思路：二维数组，行递归，列遍历
在列放置皇后的时候，要进行有效判断
  • 1.判断列方向上有没有放置过（行方向是递归遍历进行的，所以只可能放置一个）
  • 2.判断左上方有没有放置过
  • 3.判断右上方有没有放置过（左下方和右下方还没有遍历到，无需遍历）
  1. class Solution {
  2. public:
  3.     vector<vector<string>>res;
  4.     bool isvald(int row,int lie,vector<string>&mids,int n){
  5.         //检查列
  6.         for(int i=0;i<row;i++){
  7.             if(mids[i][lie]=='Q')
  8.                 return false;
  9.         }
  10.         //检查左上方
  11.         for(int i=row-1,j=lie-1;i>=0 && j>=0;i--,j--){
  12.             if(mids[i][j]=='Q')
  13.                 return false;
  14.         }
  15.         //检查右上方
  16.         for(int i=row-1,j=lie+1;i>=0 && j<n;i--,j++){
  17.             if(mids[i][j]=='Q')
  18.                 return false;
  19.         }
  20.         return true;
  21.  
  22.  
  23.     }
  24.     void backtrace(vector<string>&mids,int n,int row){
  25.  
  26.         if(row==n){
  27.             res.push_back(mids);
  28.             return;
  29.         }
  30.         
  31.         for(int i=0;i<n;i++){//列的遍历
  32.             if(isvald(row,i,mids,n)){//判断该位置是否有效
  33.                 mids[row][i]='Q';
  34.                 backtrace(mids,n,row+1);//传入的是下一行不是下一列
  35.                 mids[row][i]='.';
  36.             }
  37.         }
  38.     }
  39.     vector<vector<string>> solveNQueens(int n) {
  40.         vector<string>mids(n,string(n,'.'));//二维数组初始化
  41.         backtrace(mids,n,0);
  42.         return res;
  43.     }
  44. };

37.解数独

思路：二维遍历，递归判断
  1. class Solution {
  2. public:
  3.  
  4.     bool backtrace(vector<vector<char>>&board){
  5.         for(int i=0;i<board.size();i++){//遍历行
  6.             for(int j=0;j<board[0].size();j++){//遍历列
  7.                 if(board[i][j]=='.'){
  8.                     for(char k='1';k<='9';k++){
  9.                         if(isValid(i,j,k,board)){
  10.                             board[i][j]=k;
  11.                             if(backtrace(board)) 
  12.                                 return true;
  13.                             board[i][j]='.';
  14.                         }
  15.                     }
  16.                     return false;//9个数都遍历完都不对，说明这个位置无法插入
  17.                 }
  18.             }
  19.         }
  20.         return true;//遍历完没有返回false，说明完全ok
  21.     }
  22.     bool isValid(int row,int col,char val,vector<vector<char>>&board){
  23.         for(int i=0;i<9;i++){//判断行里是否重复
  24.             if(board[row][i]==val) return false;
  25.         }
  26.  
  27.         //判断列里是否重复
  28.         for(int i=0;i<9;i++){
  29.             if(board[i][col]==val) return false;
  30.         }
  31.  
  32.         //判断九宫格里是否重复
  33.         int startRow=(row/3)*3;//得到的是九宫格内的起始坐标
  34.         int startCol=(col/3)*3;
  35.         for(int i=startRow;i<startRow+3;i++){
  36.             for(int j=startCol;j<startCol+3;j++){
  37.                 if(board[i][j]==val) 
  38.                     return false;
  39.             }
  40.         }
  41.         return true;
  42.     }
  43.     void solveSudoku(vector<vector<char>>& board) {
  44.         backtrace(board);
  45.     }
  46. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/182842?site
推荐阅读
相关标签

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

  

闽ICP备14008679号