51. N皇后

回溯

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {

    List> list  = new LinkedList<>();

    public List> solveNQueens(int n) {

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

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

        backtracking(n, 0, chars);
        return list;
    }

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

        /**
         * 终止条件：遍历到最后一行
         * String.copyValueOf()方法将字符数组转换为字符串
         */
        if (row == n){

            LinkedList li = new LinkedList<>();

            for (char[] c : chars){
                li.add(String.copyValueOf(c));
            }

            list.add(li);

            return;
        }

        /**
         * 对每一行的位置进行遍历，判断该位置是否可以存在皇后
         */
        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/