1. 首页

LeetCode 052. N皇后 II

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

image.png


给定一个整数 n,返回 n 皇后不同的解决方案的数量。 示例: 输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。 [  [".Q..",  // 解法 1   "...Q",   "Q...",   "..Q."],  ["..Q.",  // 解法 2   "Q...",   "...Q",   ".Q.."] ]

难度:Middle

前置知识

  • 回溯
  • 深度优先遍历

公司

  • 阿里
  • 百度
  • 字节

思路

使用深度优先搜索配合位运算,二进制为 1 代表不可放置,0 相反

利用如下位运算公式:

  • x & -x :得到最低位的 1 代表除最后一位 1 保留,其他位全部为 0
  • x & (x-1):清零最低位的 1 代表将最后一位 1 变成 0
  • x & ((1 << n) – 1):将 x 最高位至第 n 位(含)清零

关键点

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

代码

  • 语言支持:JS
/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.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;
};

复杂度分析

更多题解可以访问我的 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 052. N皇后 II

链接:https://www.javascriptc.com/4412.html

« LeetCode 053. 最大子序和
写文档太麻烦,试试这款 IDEA 插件吧!»
Flutter 中文教程资源

相关推荐

QR code