Leetcode-51. N 皇后

51. N 皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1:
输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:[["Q"]]

解题思路
N皇后问题的摆放原则:同行同列,左上,右上不能有重复
解题思路还是回溯算法的框架
但是我们需要核实是否有效,参照labuladong算法小抄,用二维char数组表示一个可行解,便于后续修改答案和合法性检验,最后可行解有效则转换为List存入结果中
图片说明

class Solution {

    List<List<String>> res=new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
        //List<String> board=new ArrayList<>();--改为使用char数组
        char[][] board = new char[n][n];
        for (char[] i : board){
            Arrays.fill(i,'.');
        }
        backtrack(board,0);
        return res;
    }
    //row表示row之前的行已放置好皇后
    public void backtrack(char[][] board,int row){
        if(row==board.length){
            res.add(charToList(board));
            return;
        }
        int n=board[row].length;
        for(int col=0;col<n;col++){
            if(!isVaild(board,row,col))//如果该位置不合法,则不能放置
                continue;
            //选择
            board[row][col]='Q';
            //回溯
            backtrack(board,row+1);
            //撤销
            board[row][col]='.';
        }
    }
    //将board转换为List<String>
    public List<String> charToList(char[][] board){
        List<String> result=new LinkedList<>();
        for (char[] i : board){
            String tmp=String.valueOf(i);
            result.add(tmp);
        }
        return result;
    }
    /* 是否可以在 board[row][col] 放置皇后? */
    public boolean isVaild(char[][] board,int row,int col){
        int n = board.length;
        // 检查列是否有皇后互相冲突
        for (int i = 0; i < n; i++) {
            if (board[i][col] == 'Q')
                return false;
        }
        // 检查右上方是否有皇后互相冲突
        for (int i = row - 1, j = col + 1; 
                i >= 0 && j < n; i--, j++) {
            if (board[i][j]== 'Q')
                return false;
        }
        // 检查左上方是否有皇后互相冲突
        for (int i = row - 1, j = col - 1;
                i >= 0 && j >= 0; i--, j--) {
            if (board[i][j]== 'Q')
                return false;
        }
        return true;
    }
}
Leetcode-牛客-刷题笔记 文章被收录于专栏

本专栏主要用于分享栏主在准备java后端面试过程中的刷题笔记

全部评论

相关推荐

one_t:硕还是本?什么岗
点赞 评论 收藏
分享
头像
09-29 16:18
门头沟学院 Java
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务