长大后想做什么？做回小孩！

0%

LeetCode——N皇后II

发表于 更新于 分类于 Valine：
本文字数： 203

NO.52 N皇后II 困难

NO.52是NO.51的姊妹题，区别在于NO.51要求返回包含”棋子摆放”的List<List<String>>集合，而本题NO.52只需要返回一共有多少种摆法。

1
2
NO.51:public List<List<String>> solveNQueens(int n)
NO.52:public int totalNQueens(int n)

思路一：回溯法 看到题的第一反应是直接把上一题回溯法的终止处理”res.add”改成”计数器+1”。

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
35
36
37
38
39
40
41
42
43
44
int count=0;
public int totalNQueens(int n) {
    //棋盘,默认为0表示空，1表示皇后
    int[][] board=new int[n][n];
    //row当前填写得的行号
    dfs(n,0,board);
    return count;
}

//深度优先遍历
private void dfs(int n, int row, int[][] board) {
    //0~n-1都填写完毕
    if (row==n){
        count++;
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isUsable(board,row,col)){
            board[row][col]=1;
            //填写下一行
            dfs(n,row+1,board);
            board[row][col]=0;
        }
    }
}

//board[row][col]是否可用
private boolean isUsable(int[][] board, int row, int col) {
    //检查列上有无皇后
    for (int i = 0; i < row; i++) {
        if (board[i][col]==1)return false;
    }
    //检查左上至右下对角线有无皇后
    for (int i = col-1; i >= 0; i--) {
        if (i+row-col<0)break;
        if (board[i+row-col][i]==1)return false;
    }
    //检查右上至左下对角线有无皇后
    for (int i = col+1; i < board.length; i++) {
        if (row+col-i<0)break;
        if (board[row+col-i][i]==1)return false;
    }
    return true;
}

时间复杂度：O(n!)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github