Leetcode日记–52.N Queens Ⅱ

发布于 2020-10-18  113 次阅读


碎碎念:昨天和学姐交流了一下nus项目的要求,果然竞争也蛮激烈的呢。。我这简历上项目经历太少了。。看起来信安竞赛 小程序竞赛什么的都要加油了呢。

题目如下:


The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "…Q",
  "Q…",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q…",
  "…Q",
  ".Q.."]
]

思路:

本题即求8皇后(N皇后)的解的个数。这是一道经典的算法题(据说要用到回溯思想)。但是我并没有什么思路。。

N皇后问题的本质就是找到某个格子,这个格子所在的列,行,斜线均不能有其他queen存在。

回溯的具体做法是:依次在每一行放置一个皇后,每次新放置的皇后都不能和已经放置的皇后之间有攻击,即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上。当 N 个皇后都放置完毕,则找到一个可能的解,将可能的解的数量加 1。

同一个列是否冲突很好表示。但是斜线如何表示呢?

首先,我们来观察第一种情况--从左上到右下的斜线。

可以看到,我们的行下标和列下标都是每次加一。那么可以知道,在某个特定的斜线组合中,行数-列数的值是不变的。

第二种情况--右上到左下的斜线。

可以观察到,当行数+1时,列数-1,那么我们就知道,在特定的斜线组合中,行数+列数的值是不变的。

方法一:

我们设立三个集合,column,diagonals1,diagonals2来分别表示本行当前遍历的列是否与某列或某斜线冲突。

若冲突则遍历下一列,否则添加进入集合中,并开始放置下一行的皇后。

细节:

根据回溯法,我们在得到了当前列放置的所有组合数后,应该remove掉当前列放入的column,diagonals1和diagonals2.因为当前行放入其他列并存在解是有可能的,因此要继续“尝试”其他列。

代码如下:

class Solution {
    public int totalNQueens(int n) {
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        return backtrack(n, 0, columns, diagonals1, diagonals2);
    }

    public int backtrack(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if(row == n)
            return 1;
        else{
            int count = 0;
            for(int i =0;i<n;++i){
                if(columns.contains(i))
                    continue;
                if(diagonals1.contains(row+i))
                    continue;
                if(diagonals2.contains(row-i))
                    continue;
                columns.add(i);
                diagonals1.add(row+i);
                diagonals2.add(row-i);
                count+=backtrack(n,row+1,columns,diagonals1,diagonals2);
                // 放入第i列的情况算完了,算当前情况下除了i列其他分支的可能性
                columns.remove(i);
                diagonals1.remove(row+i);
                diagonals2.remove(row-i);
            }
            return count;
        }
        // return count;
    }
}

方法二:

上面的方法因为需要set来记录冲突情况,因此空间复杂度为O(n),但是我们希望使用O(1)复杂度来解决要怎么做呢?

可以使用官方题解中的位操作法(但是我没看懂,这里就不自己班门弄斧了)。


你好哇!欢迎来到雷公马碎碎念的地方:)