LeetCode 52.N皇后 II 题解位运算 DFS 的 JavaScript 实现【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文基于 leetcode 题解仓库中的 problems/52.N-Queens-II.md 展开深入讲解 N 皇后问题只计数、不排版这一变体的经典解法深度优先搜索DFS 位运算状态压缩。你将掌握x -x、x (x-1)、x ((1 n) - 1)三个位运算公式在棋盘冲突检测中的落地用法并看到它与仓库 thinkings/backtrack.md 中回溯模板的对应关系最终能够独立写出可运行的高效计数代码。题目背景与描述N 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。给定一个整数 n返回 n 皇后不同的解决方案的数量。示例输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。 [ [.Q.., // 解法 1 ...Q, Q..., ..Q.], [..Q., // 解法 2 Q..., ...Q, .Q..] ]注意本题与 51 题N 皇后的区别51 题要求返回所有具体棋盘布局即上例中的[.Q.., ...Q, ...]完整列表而 52 题只要求返回解法数量因此无需真正构造棋盘二维数组可以用更轻量的位运算状态直接计数这也是本题的最优解思路。前置知识回溯Backtracking走不通就回头本质是对解空间树的穷举深度优先遍历DFS回溯是 DFS 中的一种技巧。仓库 thinkings/backtrack.md 中归纳了回溯的通用流程构造空间树进行遍历遇到边界条件即不再向下搜索转而搜索另一条链达到目标条件输出结果并给出了通用模板伪代码const visited {} function dfs(i) { if (满足特定条件{ // 返回结果 or 退出搜索空间 } visited[i] true // 将当前状态标为已搜索 dosomething(i) // 对i做一些操作 for (根据i能到达的下个状态j) { if (!visited[j]) { // 如果状态j没有被搜索过 dfs(j) } } undo(i) // 恢复i }本解的 DFS 本质就是该模板的位运算特化版而逐行放皇后、冲突则剪枝正是回溯避免根本不可能是答案的递归这一剪枝原则的体现。解题思路DFS 配合位运算状态压缩核心思路一句话使用深度优先搜索配合位运算用整型变量的二进制位表示棋盘状态二进制位为 1 代表不可放置为 0 代表可放置。与传统的布尔数组记录列/两条对角线相比位运算方案的优势在于三个冲突集合列 cols、左斜线 pie、右斜线 na各用一个整数表示递归传参零拷贝当前行所有可放位置可以用一条位运算表达式直接算出无需遍历 n 个列下标天然支持状态回溯——进入递归时用|与移位产生新状态返回时由于参数按值传递旧状态自动恢复对应回溯模板中的 undo 操作。三个关键位运算公式原文档给出了本题依赖的三个位运算公式逐一展开说明x -x得到最低位的 1代表除最后一位 1 保留其他位全部为 0原理-x在补码表示下等于~x 1它与x进行按位与后恰好只留下x最低位的那个 1。例如bits 0b1100时bits -bits 0b0100。本题用它逐个取出可放置位。x (x-1)清零最低位的 1代表将最后一位 1 变成 0例如0b1100 0b1011 0b1000。本题用它取出一个可放位置后把该位置从候选集合中移除从而进入下一次循环迭代。x ((1 n) - 1)将 x 最高位至第 n 位含清零(1 n) - 1会生成一个低 n 位全为 1 的掩码例如n 4时为0b1111。由于~取反后高位全是 1必须用该掩码截断才能只保留棋盘范围内的有效位。完整代码与逐行解读语言支持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; };各状态位的含义cols已放置皇后的列集合。第 i 位为 1 表示第 i 列已被占用pie左斜线 / 主对角线方向同一条左上到右下斜线上的格子其row - col为常量。在逐行下移时已占斜线整体左移一位即(pie | p) 1对应下一行中与已放皇后同属一条左斜线的位置na右斜线 / 副对角线方向同一条右上到左下斜线上的格子其row col为常量。逐行下移时整体右移一位即(na | p) 1。执行流程拆解边界条件row n说明 n 行均已成功放置皇后res并回溯对应回溯模板中的达到目标条件输出结果计算候选位cols | pie | na把三类冲突位置合并或运算~取反得到可放位置1 表示可放再用(1 n) - 1掩码截断无效高位遍历候选位while (bits)循环处理每一个可放位bits -bits取出最低位 1 作为本次放置位置 pbits (bits - 1)将该位置从候选集中清除避免重复放置递归深入传入cols | p新增列的占用、(pie | p) 1左斜线随行下移、(na | p) 1右斜线随行下移。由于每层递归的参数都是按值传递的新整数回溯时无需像二维数组方案那样手动撤销这一点与 thinkings/backtrack.md 中每次递归都拷贝一份数据则不需要撤销状态的论述完全一致只是把拷贝的对象从数组换成了整数的位。复杂度分析时间复杂度O(N!)DFS 逐行放置第 k 行的可选位置被位运算直接枚举最坏情况下解空间接近 n! 量级且每一层的冲突判断都是 O(1) 的位运算远快于逐列扫描的 O(N) 判断版本。空间复杂度O(N)递归深度最大为 N每行一层没有额外的棋盘数组或 visited 数组主要开销是递归调用栈。同类技巧在仓库中的延伸位运算 状态压缩并非本题独有仓库中其他题目也复用了相同技巧problems/1494.parallel-courses-ii.md用整数位表示课程先修关系与已修课程集合配合 DP/DFS 做状态转移problems/1723.find-minimum-time-to-finish-all-jobs.md用位掩码枚举工作分配的子集并配合回溯剪枝。此外thinkings/bit.md 专题系统总结了异或、取最低位等位运算性质及其在只出现一次的数字等题目中的应用可作为掌握本题位运算基础的延伸阅读而 thinkings/backtrack.md 则提供了回溯的算法流程、通用模板与剪枝原则本题正是回溯 剪枝 状态压缩三者结合的典范。小结52.N 皇后 II 的位运算解法用三个公式完成了求可放位置、取一个位置、移除该位置的闭环配合cols / pie / na三个整数实现 O(1) 的冲突检测是回溯问题中状态压缩的代表作。理解它的关键在于把棋盘二维结构映射到整数的二进制位把行推进映射为斜线状态的左右移位——掌握了这套映射类似的状态压缩 DFS 题目都可以举一反三。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考