leetcode算法练习【51】N皇后

ゞ浴缸里的玫瑰 2023-02-15 01:17 142阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：回溯
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
    上图为 8 皇后问题的一种解法。
    给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

![在这里插入图片描述][20200604013133276.png]

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

#### 方案：回溯 ####

*  我的思路就是遍历~~
 *  1、利用一维数组记录每行皇后的位置，用于计算是否重复，这样会节省不少时间
 *  2、然后res这个二维数组主要用于画String用
 *  3、如果到了n+1层，说明前n层都匹配了，也就是匹配成功，这就是递归出口
 *  4、优化思路：N皇后问题应该是对称的，因此，可以只访问一半，然后加入的时候就直接镜像一下就行

class Solution { 
            private char[][] res;
            private int[] coord;
            private int n ;
            LinkedList<List<String>> ans = new LinkedList<>();
            public List<List<String>> solveNQueens(int n) { 
                //init
                this.n = n;
                this.res = new char[n][n];
                //用于存储Q的坐标
                this.coord = new int[n];
                for(int i = 0;i<n;i++){ 
                    for (int j = 0;j<n;j++){ 
                        this.res[i][j] = '.';
                    }
                }
                //回朔
                //如果成功则记录，如果失败则进入下一个
                recall(0);
                return ans;
            }
            public void recall(int row){ 
                //到这了说明上面都成功了，设为递归出口吧
                if (row>=this.n) { 
                    LinkedList<String> lis =new LinkedList<>();
                    for (int i = 0;i<n;i++){ 
                        res[i][coord[i]] = 'Q';
                        lis.addLast(String.valueOf(res[i]));
                        res[i][coord[i]] = '.';
                    }
                    ans.add(lis);
                    return;
                }
                //row = 行号
                loop1:for(int i = 0;i<this.n;i++){ 
                    //判断当前是否成立
                    for (int j = 0;j<row;j++){ 
                        //三种情况不成立，分别是竖、左斜、右斜
                        if (coord[j]==i) continue loop1;
                        if (coord[j]<i&&coord[j]-j+row==i)continue loop1;
                        if (coord[j]>i&&coord[j]+j-row==i)continue loop1;
                    }
                    this.coord[row] = i;
                    //如果匹配成功，进入下一行
                    recall(row+1);
                    this.coord[row] = 0;
                }
                return;
            }
        }

![在这里插入图片描述][20200604013105303.png]

##### 复杂度计算 #####

*  时间复杂度：O(n3)
 *  空间复杂度：O(n2)

[Git]: https://github.com/ch98road/leetcode
[20200604013133276.png]: https://img-blog.csdnimg.cn/20200604013133276.png
[20200604013105303.png]: https://img-blog.csdnimg.cn/20200604013105303.png