第六章 - 高频考题(困难)
0052. N 皇后 II

题目地址(52. N皇后 II)

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
image.png
1
给定一个整数 n,返回 n 皇后不同的解决方案的数量。
2
3
示例:
4
5
输入: 4
6
输出: 2
7
解释: 4 皇后问题存在如下两个不同的解法。
8
9
[
10
[".Q..", // 解法 1
11
"...Q",
12
"Q...",
13
"..Q."],
14
15
["..Q.", // 解法 2
16
"Q...",
17
"...Q",
18
".Q.."]
19
]
Copied!

前置知识

  • 回溯
  • 深度优先遍历

公司

  • 阿里
  • 百度
  • 字节

思路

使用深度优先搜索配合位运算,二进制为 1 代表不可放置,0 相反
利用如下位运算公式:
  • x & -x :得到最低位的 1 代表除最后一位 1 保留,其他位全部为 0
  • x & (x-1):清零最低位的 1 代表将最后一位 1 变成 0
  • x & ((1 << n) - 1):将 x 最高位至第 n 位(含)清零

关键点

  • 位运算
  • DFS(深度优先搜索)

代码

  • 语言支持:JS
1
/**
2
* @param {number} n
3
* @return {number}
4
* @param row 当前层
5
* @param cols 列
6
* @param pie 左斜线
7
* @param na 右斜线
8
*/
9
const totalNQueens = function (n) {
10
let res = 0;
11
const dfs = (n, row, cols, pie, na) => {
12
if (row >= n) {
13
res++;
14
return;
15
}
16
// 将所有能放置 Q 的位置由 0 变成 1,以便进行后续的位遍历
17
// 也就是得到当前所有的空位
18
let bits = (~(cols | pie | na)) & ((1 << n) - 1);
19
while (bits) {
20
// 取最低位的1
21
let p = bits & -bits;
22
// 把P位置上放入皇后
23
bits = bits & (bits - 1);
24
// row + 1 搜索下一行可能的位置
25
// cols | p 目前所有放置皇后的列
26
// (pie | p) << 1 和 (na | p) >> 1) 与已放置过皇后的位置 位于一条斜线上的位置
27
dfs(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1);
28
}
29
}
30
dfs(n, 0, 0, 0, 0);
31
return res;
32
};
Copied!
复杂度分析
  • 时间复杂度:O(N!)
  • 空间复杂度:O(N)
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。