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后端面试过程中的刷题笔记