算法系列--递归,回溯,剪枝的综合应用(3)（上）

💕"对相爱的人来说，对方的心意，才是最好的房子。"💕

作者：Lvzi

文章主要内容：算法系列–递归,回溯,剪枝的综合应用(3)

大家好,今天为大家带来的是算法系列--递归,回溯,剪枝的综合应用(3),带来几个比较经典的问题N皇后和解数独,这两道都是hard级别的题目,但是不要被吓到!请看我的分析

1.N皇后

题目链接:

https://leetcode.cn/problems/n-queens/description/

分析**

1.画决策树

理解题目的意思之后可以开始画决策树,决策树其实也好画,我们只需枚举每一行可能的位置即可,下面是当N = 3时的决策树:

每一层干的事情:

• 枚举当前行所有的位置,如果可以放皇后,就放,并递归下一行
• 如果不可以放—剪枝

2.剪枝(本题的难点)

这里先不设计代码,先进行剪枝的操作,分析上图,当我们在某个位置放皇后的时候一定要保证该位置行,列,主对角线,副对角线上没有其他皇后

其实当前行不需要考虑有没有皇后,因为我们是一行一行枚举的,所以只需要考虑列,主对角线,副对角线上没有其他皇后即可

那该怎么判断呢?可能会想到使用3层for循环去遍历与当前位置相关的位置:

1. 第一层循环遍历当前位置所在列有无皇后
2. 第二层循环遍历当前位置的主对角线上有无皇后
3. 第三层循环遍历当前位置副对角线上有无皇后

如果在遍历的过程中发现了皇后,则该皇后会攻击当前要填位置的皇后,所以不能放皇后–剪枝

但是此时的时间复杂度高达3n * 2 ^ n,时间复杂度很高(但是在本题也能通过),其实我们可以采用之前学习过的五子棋中判断当前位置的相关位置有无棋子的策略–使用三个布尔类型的数组

• boolean[] col:用于标记当前列上有无皇后
• boolean[] digit1:用于标记当前位置的主对角线上有无皇后
• boolean[] digit2:用于标记当前位置的副对角线上有无皇后

3.设计代码

全局变量

• ret:最终的返回值
• path:记录每次dfs的结果,类型设置为char[][],方便填充
• 三个布尔类型的数组
• N:用于表示皇后的个数

dfs

• 函数头:只需要告诉我当前遍历到哪一行就行–一个参数row
• 函数体:每一个子问题都是从0开始遍历当前行的所有位置,符合条件的位置添加Q,并递归下一行,不符合条件的位置什么也不干
• 递归出口:当row==N,即遍历到完所有行后

4.剪枝:

不符合条件的位置直接跳过即可

5.回溯:

回溯只需要将原先填充的位置恢复原状,并将对应位置的三个布尔类型的数组更改为false

代码:

class Solution {
    List<List<String>> ret;// 返回值
    char[][] path;// 记录每次搜索的结果
    boolean[] col;// 列
    boolean[] digit1;// 主对角线
    boolean[] digit2;// 副对角线
    int N;
    public List<List<String>> solveNQueens(int n) {
        N = n;
        ret = new ArrayList<>();
        path = new char[N][N];
        for(int i = 0; i < n; i++)// 预处理  全部填充为. 后续只需要考虑符合条件的情况即可
            Arrays.fill(path[i],'.');
        col = new boolean[N];
        digit1 = new boolean[2 * N];
        digit2 = new boolean[2 * N];
        dfs(0);
        return ret;
    }
    private void dfs(int row) {
        // 递归出口
        if(row == N) {
            // 添加结果
            List<String> tmp = new ArrayList<>();
            for(int i = 0; i < N; i++)
            {
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
            return;
        }
        for(int i = 0; i < N; i++) {
            if(!col[i] && !digit1[i - row + N] && !digit2[i + row]) {
                path[row][i] = 'Q';
                col[i] = digit1[i - row + N] = digit2[i + row] = true;
                dfs(row + 1);// 递归下一行
                path[row][i] = '.';// 回溯
                col[i] = digit1[i - row + N] = digit2[i + row] = false;
            }
        }
    }
}

总结:

1. path是一个二维的字符数组,path[0]代表一个char[],字符数组就是一个字符串,然后创建一个List类型的集合去依次添加path每一行的元素即可
2. 将path数组使用Arrays.fill()将path全部填充为.,这样在后面遍历的时候只需要考虑为Q的情况即可
3. 注意在填充的时候一定要创建新的引用,不要直接添加,因为引用指向的是堆上的地址,你后续的更改会影响集合中存储的内容的
4. i代表列数,row是行数,明确每一个变量的实际意义

算法系列--递归,回溯,剪枝的综合应用(3)（下）https://developer.aliyun.com/article/1480887?spm=a2c6h.13148508.setting.14.352e4f0emDjgDq