0052. N 皇后 II
题目地址(52. N皇后 II)
https://leetcode-cn.com/problems/n-queens-ii/
题目描述
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
前置知识
回溯
深度优先遍历
公司
阿里
百度
字节
思路
使用深度优先搜索配合位运算,二进制为 1 代表不可放置,0 相反
利用如下位运算公式:
x & -x :得到最低位的 1 代表除最后一位 1 保留,其他位全部为 0
x & (x-1):清零最低位的 1 代表将最后一位 1 变成 0
x & ((1 << n) - 1):将 x 最高位至第 n 位(含)清零
关键点
位运算
DFS(深度优先搜索)
代码
语言支持:JS
复杂度分析
时间复杂度:O(N!)
空间复杂度:O(N)
最后更新于