AIPRO AIPRO

算法研习之路：递归、搜索与回溯的进阶探索（其二）

2小时前发布 gsjqwyl
2 0 0

文章标题：

算法探索之旅：递归、搜索与回溯的深入探究（其二）

文章内容：算法学习：

前言：

在（一）里我们选取了几个经典例题，对递归、搜索以及回溯算法做了初步的讲解，今日我们要更深入地剖析这些算法知识点，着重加入了剪枝相关内容，来瞧瞧今日的例题哟

目录

1. 经典例题

1.1 全排列 ||

1.2 组合总和

1.3 N皇后

1.4 有效的数独

1.5 单词搜索

1.6 不同路径 |||

2. 总结

1. 经典例题

1.1 全排列 ||

47. 全排列 II

给定一个可能含有重复数字的序列 nums ，要按任意顺序返回所有不重复的全排列。

示例 1：

**输入：** nums = [1,1,2]
**输出：**
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

**输入：** nums = [1,2,3]
**输出：**[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

**算法原理：**

这道题和（一）中的全排列|解法差别不大，唯一不同的是这里存在重复数字，需要进行剪枝操作。观察示例能发现，策略树中有一些要剪掉的错误分支，比如橙红色的是同一数重复使用的分支，绿色的是同一层相同元素多次使用的分支。基于此，代码可以从关注不合法分支或者合法分支两个角度去切入。

代码实现：

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    bool check[10];
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        dfs(nums);
        return ret;
    }
    void dfs(vector<int>& nums)
    {
        if(path.size()==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;
            // 关注合法分支的做法是取反上面的条件并将内容包含在函数体内
            path.push_back(nums[i]);
            check[i]=true;
            dfs(nums);
            path.pop_back();
            check[i]=false;
        }
    }
};

1.2 组合总和

LCR 081. 组合总和

给定一个没有重复元素的正整数数组 candidates 和一个正整数 target，找出 candidates 中所有能使数字总和等于目标数 target 的唯一组合。

candidates 中的数字可以无限制重复选取。若至少一个所选数字的数量不同，则视为不同的组合。

对于给定输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：

**输入:** candidates = [2,3,6,7], target = 7<
**输出:**[[7],[2,2,3]]

示例 2：

**输入:** candidates = [2,3,5], target = 8
**输出:**[[2,2,2,2],[2,3,3],[3,5]]

示例 3：

**输入:** candidates = [2], target = 1
**输出:**[]

示例 4：

**输入:** candidates = [1], target = 1
**输出:**[[1]]

示例 5：

**输入:** candidates = [1], target = 2
**输出:**[[1,1]]

提示：

  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidate 中的每个元素都是独一无二的。
  • 1 <= target <= 500

算法原理：

代码实现：

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    int sum;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates,target,0);
        return ret;
    }
    void dfs(vector<int>& candidates,int target,int pos)
    {
        if(sum>=target)
        {
            if(sum==target) ret.push_back(path);
            return;
        }
        for(int i=pos;i<candidates.size();i++)
        {
            sum+=candidates[i];
            path.push_back(candidates[i]);

            dfs(candidates,target,i);
            path.pop_back();
            sum-=candidates[i];
        }
    }
};

1.3 N皇后

51. N 皇后

按照国际象棋规则，皇后能攻击同一行、同一列或同一斜线上的棋子。

n 皇后问题 是要把 n 个皇后放置在 n×n 的棋盘上，且让皇后彼此不能互相攻击。

给你一个整数 n，返回所有不同的 n 皇后问题 的解决方案。

每种解法包含一种不同的棋子放置方案，其中 'Q' 表示皇后，'.' 表示空位。

示例 1：

**输入：** n = 4
**输出：**[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
**解释：** 如上图所示，4 皇后问题存在两种不同解法。

示例 2：

**输入：** n = 1
**输出：**[["Q"]]

提示：

  • 1 <= n <= 9

算法原理：

解释:

这道题关键在于剪枝操作。根据题意，一个列中只能有一个皇后，所以可以创建bool数组col来标记列的情况。把棋盘抽象到坐标系，对角线也只能有一个皇后，对角线有两种情况，其x+y是定值，所以能创建bool数组来标记。

因为y-x可能为负数，不能作为bool数组下标，所以要加上n的偏移量。

代码实现：

class Solution {
    bool checkCol[10],checkDigal1[20],checkDigal2[20];
    vector<vector<string>> ret;
    vector<string> path;
    int n;
public:
    vector<vector<string>> solveNQueens(int _n) {
        n=_n;
        path.resize(n);
        for(int i=0;i<n;i++)
            path[i].append(n,'.');
        dfs(0);
        return ret;
    }
    void dfs(int row)
    {
        if(row==n)
        {
            ret.push_back(path);
            return;
        }
        for(int col=0;col<n;col++)    // 尝试在该行放置皇后
        {
            // 剪枝
            if(!checkCol[col]&&!checkDigal1[row-col+n]&&!checkDigal2[row+col])
            {
                path[row][col]='Q';
                checkCol[col]=checkDigal1[row-col+n]=checkDigal2[row+col]=true;
                dfs(row+1);
                // 恢复现场
                path[row][col]='.';
                checkCol[col]=checkDigal1[row-col+n]=checkDigal2[row+col]=false;
            }
        }
    }
};

1.4 有效的数独

36. 有效的数独

请判断一个 9 x 9 的数独是否有效。只需根据以下规则验证已填入数字是否有效。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每个 3x3 宫内只能出现一次。（参考示例图）

注意：

  • 有效的数独不一定可解。
  • 只需验证已填入数字是否有效。
  • 空白格用 '.' 表示。

示例 1：

**输入：** board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
**输出：** true

示例 2：

**输入：** board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
**输出：** false
**解释：** 除第一行第一个数字从**5**改为**8**外，其他同示例1，但左上角3x3宫内有两个8，数独无效。

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是数字（1-9）或 '.'

算法原理：

解释:

这题不是回溯类题目，但能助于理解N皇后题。需保证数据在特定位置不重复，可用哈希方式（数组模拟）标记。用三个bool数组分别标记行、列、九宫格中数字的出现情况。比如row数组标记第i行数字的出现，grid数组标记3×3九宫格中数字的出现。

代码实现：

class Solution {
    bool col[9][10];
    bool row[9][10];
    bool grid[3][3][10];
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]>='0'&&board[i][j]<='9')
                {
                    int num=board[i][j]-'0';
                    if(row[i][num] ||col[j][num]||grid[i/3][j/3][num]) return false;
                    row[i][num]=col[j][num]=grid[i/3][j/3][num]=true;
                }
            }
        }
        return true;
    }
};

1.5 单词搜索

79. 单词搜索

给定一个 m x n 二维字符网格 board 和字符串单词 word。若 word 存在于网格中，返回 true；否则，返回 false。

单词需按字母顺序，由相邻单元格的字母构成，相邻单元格指水平或垂直相邻的。同一单元格字母不可重复使用。

示例 1：

**输入：** board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
**输出：** true

示例 2：

**输入：** board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
**输出：** true

示例 3：

**输入：** board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
**输出：** false

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

算法原理：

代码实现：

class Solution {
    bool vis[7][7];
    int m,n;
public:
    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])
                {
                    vis[i][j]=true;
                    if(dfs(board,i,j,word,1)) return true;
                    vis[i][j]=false;
                }
            }
        return false;
    }
    int dx[
© 版权声明
文章版权归作者所有，未经允许请勿转载。
上一篇

没有更多了...

下一篇

没有更多了...

相关文章

🚀 2025年最新IDEA永久破解教程 | 附最新激活码&破解补丁下载 🚀
gsjqwyl
23
🚀 2025年最新IDEA激活码分享：永久破解IDEA终极教程（附破解补丁）
gsjqwyl
12
🚀 2025最新PyCharm永久激活教程（附2099年有效激活码）| 破解全攻略 💻
gsjqwyl
23
Java实现安全哈希算法（附完整代码示例）
gsjqwyl
56
2025年最新DataGrip激活码及永久破解教程（支持2099年）
gsjqwyl
9
序列图中执行规范的运用与解析
gsjqwyl
57

暂无评论

暂无评论...
添加小工具
点此为“正文侧边栏”添加小工具
Copyright © 2025 AIPRO 陇ICP备2022001249号-4