N皇后题目链接https://leetcode.cn/problems/n-queens/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答无分析自己没什么思路连棋盘大小都不知道如何计算。哈哈哈哈自己不认真看题题目说了n*n的棋盘哈哈哈哈哈哈被自己困笑了看了官方题解后的解答//方法一基于集合的回溯 //时间复杂度O(n!) //空间复杂度O(n) public ListListString solveNQueens(int n) { int[] queen new int[n];//记录每行皇后所在的列下标 Arrays.fill(queen, -1); SetInteger col new HashSet();//记录已经被影响的列 SetInteger diagonals1 new HashSet();//记录已经被影响的从左上到右下的对角线横坐标与纵坐标之差 SetInteger diagonals2 new HashSet();//记录已经被影响的从右上到左下的对角线横坐标与纵坐标之和 ListListString ans new ArrayList(); dfs(n, 0, queen, col, diagonals1, diagonals2, ans); return ans; } public void dfs(int n, int cur, int[] queen, SetInteger col, SetInteger diagonals1, SetInteger diagonals2, ListListString ans){ if(cur n){ //收集答案 ListString res generateRes(n, queen); ans.add(res); return; } //遍历当前行的皇后可以放置的位置 for(int i0; in; i){ //当前位置可以放置皇后 if(!col.contains(i) !diagonals1.contains(cur-i) !diagonals2.contains(curi)){ queen[cur] i; col.add(i); diagonals1.add(cur-i); diagonals2.add(curi); dfs(n, cur1, queen, col, diagonals1, diagonals2, ans); //回溯 queen[cur] -1; col.remove(i); diagonals1.remove(cur-i); diagonals2.remove(curi); } } } public ListString generateRes(int n, int[] queen){ ListString res new ArrayList(); for(int i0; in; i){ char[] row new char[n]; Arrays.fill(row, .); row[queen[i]] Q; res.add(new String(row)); } return res; } //方法二基于位运算的回溯只看思路版 //时间复杂度O(n!) //空间复杂度O(n) public ListListString solveNQueens(int n) { ListListString ans new ArrayList(); int[] queen new int[n]; Arrays.fill(queen, -1); dfs(n, 0, queen, ans, 0, 0, 0); return ans; } public void dfs(int n, int cur, int[] queen, ListListString ans, int column, int diagonals1, int diagonals2){ if(cur n){ ListString res generateRes(n, queen); ans.add(res); return; } for(int col0; coln; col){ if(((1 col) column) 0 ((1 (cur-col)) diagonals1) 0 ((1 (curcol)) diagonals2) 0){ queen[cur] col; int newColumn (1 col) | column; int newDiagonals1 (1 (cur-col)) | diagonals1; int newDiagonals2 (1 (curcol)) | diagonals2; dfs(n, cur1, queen, ans, newColumn, newDiagonals1, newDiagonals2); queen[cur] -1; } } } public ListString generateRes(int n, int[] queen){ ListString res new ArrayList(); for(int i0; in; i){ char[] row new char[n]; Arrays.fill(row, .); row[queen[i]] Q; res.add(new String(row)); } return res; } //方法二基于位运算的回溯看了官方解答版 //时间复杂度O(n!) //空间复杂度O(n) public ListListString solveNQueens(int n) { ListListString ans new ArrayList(); int[] queen new int[n]; Arrays.fill(queen, -1); dfs(n, 0, queen, ans, 0, 0, 0); return ans; } public void dfs(int n, int cur, int[] queen, ListListString ans, int columns, int diagonals1, int diagonals2){ if(cur n){ ListString res generateRes(n, queen); ans.add(res); return; } int availablePositions ((1 n) - 1) (~(columns | diagonals1 | diagonals2)); while(availablePositions ! 0){ int position availablePositions (-availablePositions);//获取最低位 1 所对应的数值 availablePositions availablePositions (availablePositions - 1);//将最低位的1置0 int column Integer.bitCount(position - 1);//计算该列对应的列索引从 0 开始 queen[cur] column; dfs(n, cur1, queen, ans, columns | position, (diagonals1 | position) 1, (diagonals2 | position) 1); queen[cur] -1; } } public ListString generateRes(int n, int[] queen){ ListString res new ArrayList(); for(int i0; in; i){ char[] row new char[n]; Arrays.fill(row, .); row[queen[i]] Q; res.add(new String(row)); } return res; }分析​ 1、方法一的解题思路根据规则每行只能放置一个皇后所以对于每一行我们遍历所有的列寻找皇后可以放置的位置然后递归放置下一个皇后第一个皇后可能放置的位置有n个那么第二个皇后可能放置的位置最多有n-1个以此类推放置所有皇后的时间复杂度就为n!所以我们需要考虑降低判断当前位置是否可以放置皇后的时间复杂度本方法采用三个Set集合来分别判断当前位置所处的列、从左上到右下的斜线、从右上到左下的斜线是否存在皇后判断的时间复杂度就为O(1)对于列我们很好判断但是对于两个斜线位置如何判断是否为同一条斜线呢经过观察我们可以发现从左上到右下的斜线横坐标和纵坐标都是同时加一的所以从左上到右下的每一条斜线上每个位置的横坐标与纵坐标之差都是相等的而从右上到左下的斜线横坐标每次加一纵坐标每次减一所以从右上到左下的每一条斜线上每个位置的横坐标与纵坐标之和都是相等的由此我们就可以轻松判断是否为同一条斜线了。另外在递归遍历时我们用数组queen记录每行皇后放置位置的列queen[i]表示第i行皇后放置的列最后完成n个皇后的放置后就可以通过数组queen来创建答案。​ 2、方法二与方法一的核心思想是差不多的主要区别在于​ 第一方法一使用三个Set集合分别记录每一列以及两个方向的每条斜线上是否有皇后集合的空间复杂度是 O(N)而方法二只采用三个整数 columns、diagonals1和 diagonals2分别记录每一列以及两个方向的每条斜线上是否有皇后每个整数有 N 个二进制位棋盘的每一列对应每个整数的二进制表示中的一个数位其中棋盘的最左列对应每个整数的最低二进制位最右列对应每个整数的最高二进制位。进入下一行时columns 的值保持不变diagonals1左移一位diagonals2右移一位由于棋盘的最左列对应每个整数的最低二进制位即每个整数的最右二进制位因此对整数的移位操作方向和对棋盘的移位操作方向相反对棋盘的移位操作方向是 diagonals1右移一位diagonals2左移一位。​ 第二方法一遍历了每一行的所有列而方法二只遍历当前皇后可以存放的列。方法二遍历可以放置皇后的位置时可以利用以下两个按位与运算的性质​ x (−x) 可以获得 x 的二进制表示中的最低位的 1 的位置​ x (x−1) 可以将 x 的二进制表示中的最低位的 1 置成 0。​ 具体做法是每次获得可以放置皇后的位置中的最低位并将该位的值置成 0尝试在该位置放置皇后。这样即可遍历每个可以放置皇后的位置。总结本题有两种解题方法分别为基于集合的回溯、基于位运算的回溯。基于集合的回溯方法比较简单直接直接用三个Set集合分别记录每一列以及两个方向的每条斜线上是否有皇后即可。基于位运算的回溯方法比较考察对于位运算的理解和运用实现起来较为复杂具体思路建议直接看官方解答方法二的思路分析。