52. N皇后II

回溯

import java.util.Arrays;

class Solution {

    int sum = 0;

    public int totalNQueens(int n) {

        /**
         * 使用二维数组存储棋盘，最后再转换为列表
         * 默认填充'.'
         */
        char[][] chars = new char[n][n];

        for (char[] c : chars){
            Arrays.fill(c, '.');
        }

        backtracking(n, 0, chars);

        return sum;
    }

    public void backtracking(int n, int row, char[][] chars){

        /**
         * 终止条件：遍历到最后一行
         */
        if (row == n){
            sum++;
        }

        /**
         * 对每一行的位置进行遍历，判断该位置是否可以存在皇后
         */
        for (int col = 0; col < n; col++) {

            if (isValid(n, row, col, chars)){

                chars[row][col] = 'Q';
                backtracking(n, row + 1, chars);
                chars[row][col] = '.';
            }
        }
    }

    public boolean isValid(int n, int row, int col, char[][] chars){

        /**
         * 判断同一列是否有皇后
         */
        for (int i = 0; i < row; i++) {

            if (chars[i][col] == 'Q'){
                return false;
            }
        }

        /**
         * 判断右上方向是否有皇后
         */
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {

            if (chars[i][j] == 'Q'){
                return false;
            }
        }

        /**
         * 判断左上方向是否有皇后
         */
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {

            if (chars[i][j] == 'Q'){
                return false;
            }
        }

        return true;
    }
}

/**
 * 时间复杂度 O(n!)
 * 空间复杂度 O(n)
 */

https://leetcode-cn.com/problems/n-queens-ii/