当前位置： 首页 > article >正文

递归搜索回溯综合练习（十五题）

article 2025/1/30 12:54:19

目录

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;
        }
        //left
        left++;
        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;
            }
        }
    }
};


http://www.kler.cn/a/522663.html

相关文章：

  • 多级缓存（亿级并发解决方案）
  • UE求职Demo开发日志#15 思路与任务梳理、找需要的资源
  • JAVA 接口、抽象类的关系和用处 详细解析
  • 智慧园区系统分类及其在提升企业管理效率中的创新应用探讨
  • Java基于SSM框架的互助学习平台小程序【附源码、文档】
  • 搭建Spring Boot开发环境
  • 力扣-链表-19 删除链表倒数第N个节点
  • 三星手机人脸识别解锁需要点击一下电源键，能够不用点击直接解锁吗
  • Vue 封装http 请求
  • 使用 Intersection Observer 实现高效懒加载和滚动监听
  • 7. 马科维茨资产组合模型+金融研报AI长文本智能体(Qwen-Long)增强方案（理论+Python实战）
  • PPT自动化 python-pptx -7: 占位符（placeholder）
  • java爬虫工具Jsoup学习
  • mysql性能调优之SQL分析与优化
  • 图像处理之图像灰度化
  • MySQL中InnoDB逻辑存储结构
  • 第13章 深入volatile关键字（Java高并发编程详解：多线程与系统设计）
  • 蓝桥杯例题三
  • AWS Snowball
  • MySQL 事件调度器
  • 【Java数据结构】了解排序相关算法
  • maven、npm、pip、yum官方镜像修改文档
  • 学习ASP.NET Core的身份认证（基于JwtBearer的身份认证10）
  • 基于RIP的MGRE VPN综合实验
  • DNS解析防护应措施有哪些？
  • 【算法】Master Theorem 计算递归算法的时间复杂度