算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习三（leetcode真题剖析）

01.字母大小写全排列

题目链接：https://leetcode.cn/problems/letter-case-permutation/

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

示例 1：

输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]
1
2

示例 2:

输入: s = "3z4"
输出: ["3z4","3Z4"]
1
2

提示:

• 1 <= s.length <= 12
• s 由小写英文字母、大写英文字母和数字组成

思路

在处理英文字母时，每个元素存在三种情况：

1. 不进行处理；
2. 如果当前字母是英文字母并且是大写，将其修改为小写；
3. 如果当前字母是英文字母并且是小写，将其修改为大写。

代码

class Solution {
    string path;
    vector<string> ret;
public:
    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;
        }

        int ch=s[pos];
        path.push_back(ch);
        dfs(s,pos+1);
        path.pop_back();

        if(ch<'0'||ch>'9'){
            int tmp=change(ch);
            path.push_back(tmp);
            dfs(s,pos+1);
            path.pop_back();
        }
    }

    char change(char ch){
        if(ch>='a'&&ch<='z') ch-=32;
        else ch+=32;
        return ch;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

02.优美的排列

题目链接：https://leetcode.cn/problems/beautiful-arrangement/

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：

• perm[i] 能够被 i 整除
• i 能够被 perm[i] 整除

给你一个整数 n ，返回可以构造的 优美排列 的 数量 。

示例 1：

输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
    - perm[1] = 1 能被 i = 1 整除
    - perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
    - perm[1] = 2 能被 i = 1 整除
    - i = 2 能被 perm[2] = 1 整除
1
2
3
4
5
6
7
8
9

示例 2：

输入：n = 1
输出：1
1
2

提示：

• 1 <= n <= 15

思路
在这个问题中，我们需要在每一个位置上考虑所有的可能情况，并确保不出现重复。通过深度优先搜索的方式，不断地枚举每个数在当前位置的可能性，并回溯到上一个状态，直到枚举完所有可能性，得到正确的结果。为了实现这一目标，可以采用以下步骤：

1. 定义一个变量用来记录所有可能的排列数量；
2. 使用一个一维数组 visited 标记元素的使用情况；
3. 从第一个位置开始进行递归，枚举每个数的可能性。

通过这样的深度优先搜索过程，可以得到所有符合条件的排列。

代码

class Solution {
    bool check[16];
    int ret=0,n;
public:
    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]&&(pos%i==0||i%pos==0)){
                check[i]=true;
                dfs(pos+1);
                check[i]=false;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

03.N 皇后

题目链接：https://leetcode.cn/problems/n-queens/

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

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

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 9

思路

首先，在每一行放置第一个皇后，然后遍历棋盘的第二行，在可行的位置放置第二个皇后，再遍历第三行，以此类推，直到放置了n个皇后为止。

为了记录每一行放置的皇后的列数，使用一个数组来记录。在每一行中，尝试放置一个皇后，并检查是否与前面已经放置的皇后冲突。如果没有冲突，继续递归地放置下一行的皇后，直到所有皇后都放置完毕，然后记录这个方案。

在检查皇后是否冲突时，可以使用一个数组来记录每一列是否已经放置了皇后，并检查当前要放置的皇后是否会和已经放置的皇后冲突。对于对角线，可以使用两个数组来记录从左上角到右下角的每一条对角线上是否已经放置了皇后，以及从右上角到左下角的每一条对角线上是否已经放置了皇后。

对于对角线是否冲突的判断可以通过以下流程解决：

1. 从左上到右下：相同对角线的行列之差相同；
2. 从右上到左下：相同对角线的行列之和相同。

因此，需要创建用于存储解决方案的二维字符串数组 ret，用于存储每个皇后的位置的一维整数数组 path，以及用于记录每一列和对角线上是否已经有皇后的布尔型数组 checkCol、checkDig1 和 checkDig2。

代码

class Solution {
    bool checkCol[10],checkDig1[20],checkDig2[20];
    vector<vector<string>> ret;
    vector<string> path;
    int n;
public:
    vector<vector<string>> solveNQueens(int _n) {
        n=_n;
        path.resize(n,string(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]&&!checkDig1[row-col+n]&&!checkDig2[row+col]){
                path[row][col]='Q';
                checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col]=true;
                dfs(row+1);
                path[row][col]='.';
                checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col]=false;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

04.有效的数独

题目链接：https://leetcode.cn/problems/valid-sudoku/

请你判断一个 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
1
2
3
4
5
6
7
8
9
10
11

示例 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 存在, 因此这个数独是无效的。
1
2
3
4
5
6
7
8
9
10
11
12

思路

创建三个数组标记行、列以及 3*3 小方格中是否出现 1~9 之间的数字即可。

代码

class Solution {
    int row[9][10];
    int col[9][10];
    int 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]!='.'){
                    int num=board[i][j]-'0';
                    if(!row[i][num]&&!col[j][num]&&!grid[i/3][j/3][num]){
                        row[i][num]=col[j][num]=grid[i/3][j/3][num]=1;
                    }else return false;
                }
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19