N-Queens II——Leetcode

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

计算N皇后的合法解的数量。

解题思路：这次使用了更优化的方式判断棋盘上的冲突，abs(curr.row-row)==abs(curr.col-col)

board数组纪录每行的列的位置，如board[1]=3，代表第一行第三列上有皇后。

public class Solution {

    int[] board;

    int res = 0;

    public int totalNQueens(int n) {

        board = new int[n];

        helper(0,n);

        return res;

    }

    private void helper(int k,int n){

        if(k>=n){

            res++;

            return;

        }

        for(int i=0;i<n;i++){

            if(valid(k,i)){

                board[k]=i;

                helper(k+1,n);

            }

        }

        return ;

    } 

    private boolean valid(int x, int y){

        int row = 0;

        while(row<x){

            if(board[row]==y||Math.abs(x-row)==Math.abs(y-board[row])){

                return false;

            }

            row++;

        }

        return true;

    }

}

巴特西

N-Queens II——Leetcode

最新文章

热门文章