84 lines
2.0 KiB
Markdown
84 lines
2.0 KiB
Markdown
## 题目地址
|
||
https://leetcode-cn.com/problems/n-queens-ii
|
||
|
||
## 题目描述
|
||
```
|
||
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
|
||
|
||
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
|
||
|
||
示例:
|
||
|
||
输入: 4
|
||
输出: 2
|
||
解释: 4 皇后问题存在如下两个不同的解法。
|
||
|
||
[
|
||
[".Q..", // 解法 1
|
||
"...Q",
|
||
"Q...",
|
||
"..Q."],
|
||
|
||
["..Q.", // 解法 2
|
||
"Q...",
|
||
"...Q",
|
||
".Q.."]
|
||
]
|
||
```
|
||
|
||
## 思路
|
||
使用深度优先搜索配合位运算，二进制为 1 代表不可放置，0 相反
|
||
|
||
利用如下位运算公式：
|
||
|
||
- x & -x ：得到最低位的 1 代表除最后一位 1 保留，其他位全部为 0
|
||
- x & (x-1)：清零最低位的 1 代表将最后一位 1 变成 0
|
||
- x & ((1 << n) - 1)：将 x 最高位至第 n 位(含)清零
|
||
|
||
## 关键点
|
||
|
||
- 位运算
|
||
- DFS（深度优先搜索）
|
||
|
||
## 代码
|
||
* 语言支持：JS
|
||
|
||
```js
|
||
/**
|
||
* @param {number} n
|
||
* @return {number}
|
||
* @param row 当前层
|
||
* @param cols 列
|
||
* @param pie 左斜线
|
||
* @param na 右斜线
|
||
*/
|
||
const totalNQueens = function (n) {
|
||
let res = 0;
|
||
const dfs = (n, row, cols, pie, na) => {
|
||
if (row >= n) {
|
||
res++;
|
||
return;
|
||
}
|
||
// 将所有能放置 Q 的位置由 0 变成 1，以便进行后续的位遍历
|
||
// 也就是得到当前所有的空位
|
||
let bits = (~(cols | pie | na)) & ((1 << n) - 1);
|
||
while (bits) {
|
||
// 取最低位的1
|
||
let p = bits & -bits;
|
||
// 把P位置上放入皇后
|
||
bits = bits & (bits - 1);
|
||
// row + 1 搜索下一行可能的位置
|
||
// cols ｜ p 目前所有放置皇后的列
|
||
// (pie | p) << 1 和 (na | p) >> 1) 与已放置过皇后的位置 位于一条斜线上的位置
|
||
dfs(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1);
|
||
}
|
||
}
|
||
dfs(n, 0, 0, 0, 0);
|
||
return res;
|
||
};
|
||
```
|
||
***复杂度分析***
|
||
|
||
- 时间复杂度：O(N!)
|
||
- 空间复杂度：O(N)
|