【Leetcode 每日一题】52. N 皇后 II

news/2024/12/5 2:45:18/

问题背景

n n n 皇后问题 研究的是如何将 n n n 个皇后放置在 n × n n \times n n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n n n,返回 n n n 皇后问题 不同的解决方案的数量。

数据约束

  • 1 ≤ n ≤ 9 1 \le n \le 9 1n9

解题过程

只需要统计可能的结果数量,参考修改 昨天的题解 就可以。
在不需要输出路径的前提下,位运算实现的优势就非常明显了。直接标记需要路径数组来记录之前访问过的节点信息,用布尔型数组虽然不需要记录路径,也避免不了定义几个标记数组。

具体实现

直接判断

class Solution {public int totalNQueens(int n) {int[] path = new int[n];return dfs(0, n, path);}private int dfs(int i, int n, int[] path) {if(i == n) {return 1;}int res = 0;for(int j = 0; j < n; j++) {if(check(i, j, path)) {path[i] = j;res += dfs(i + 1, n, path);path[i] = 0;}}return res;}private boolean check(int i, int j, int[] path) {for(int k = 0; k < i; k++) {if(j == path[k] || Math.abs(i - k) == Math.abs(j - path[k])) {return false;}}return true;}
}

位运算限制

class Solution {public int totalNQueens(int n) {return dfs(n, (1 << n) - 1, 0, 0, 0);}private int dfs(int n, int mask, int col, int mainDiag, int subDiag) {if(col == mask) {return 1;}int limit = col | mainDiag | subDiag;int candidate = mask & (~limit);int cur;int res = 0;while(candidate != 0) {cur = candidate & (-candidate);candidate ^= cur;res += dfs(n, mask, col | cur, (mainDiag | cur) << 1, (subDiag | cur) >>> 1);}return res;}
}

数组标记

class Solution {public int totalNQueens(int n) {boolean[] col = new boolean[n];boolean[] mainDiag = new boolean[2 * n - 1];boolean[] subDiag = new boolean[2 * n - 1];return dfs(0, n, col, mainDiag, subDiag);}private int dfs(int i, int n, boolean[] col, boolean[] mainDiag, boolean[] subDiag) {if(i == n) {return 1;}int res = 0;for(int j = 0; j < n; j++) {if(!col[j] && !mainDiag[i + j] && !subDiag[i - j + n - 1]) {col[j] = mainDiag[i + j] = subDiag[i - j + n - 1] = true;res += dfs(i + 1, n, col, mainDiag, subDiag);col[j] = mainDiag[i + j] = subDiag[i - j + n - 1] = false;}}return res;}
}

http://www.ppmy.cn/news/1552126.html

相关文章

【鸿蒙】鸿蒙开发过程中this指向问题

文章目录 什么是 this&#xff1f;常见 this 指向问题案例分析&#xff1a;HarmonyOS 组件中的 this 指向问题问题描述问题分析原因 解决方案&#xff1a;绑定 this 的正确方法方法一&#xff1a;使用箭头函数方法二&#xff1a;手动绑定 this 完整代码示例使用箭头函数使用 bi…

三格电子—单通道串口服务器

型号&#xff1a;SG-TCP232-110 一、产品介绍 1.1 功能简介 SG-TCP232-110 是一款用来进行串口数据和网口数据转换的设备。解决普通 串口设备在 Internet 上的联网问题。 设备的串口部分提供一个 232 接口和一个 485 接口&#xff0c;两个接口内部连接&#xff0c;…

深度学习案例:ResNet50模型+SE-Net

本文为为&#x1f517;365天深度学习训练营内部文章 原作者&#xff1a;K同学啊 一 回顾ResNet模型 ResNet&#xff0c;即残差网络&#xff0c;是由微软研究院的Kaiming He及其合作者于2015年提出的一种深度卷积神经网络架构。该网络架构的核心创新在于引入了“残差连接”&…

使用 Docker 部署 Spring Boot 项目流程

文章目录 使用 Docker 部署 Spring Boot 项目流程1. 构建 Spring Boot 项目使用 Maven 构建项目&#xff1a;使用 Gradle 构建项目&#xff1a; 2. 创建 Dockerfile示例 Dockerfile&#xff1a;解释&#xff1a; 3. 构建 Docker 镜像4. 运行 Docker 容器5. 查看容器日志6. 管理…

[每周一更]-(第125期):模拟面试|NoSQL面试思路解析

文章目录 39|Elasticsearch 高可用:怎么保证 Elasticsearch 的高可用?1. Elasticsearch 的节点有什么角色?一个节点可以扮演多个角色吗?2. 在实践中,怎么合理安排不同节点扮演的角色?3. 什么是候选主节点和投票节点?投票节点可以被选为主节点吗?为什么要引入投票节点?…

C#tabcontrol如何指定某个tabItem为默认页

// Selects tabPage2 using SelectedTab.this.tabControl1.SelectedTab tabPage2; 参考链接 TabControl.SelectedTab 属性 (System.Windows.Forms) | Microsoft Learnhttps://learn.microsoft.com/zh-cn/dotnet/api/system.windows.forms.tabcontrol.selectedtab?viewnetfr…

Python函数内部与函数外部执行相同语句的显存区别

执行代码 mport torch import torch.cuda # 设置设备 device torch.device(cuda if torch.cuda.is_available() else cpu) # 参数设置 B 64 # batch size L 32 # sequence length C 512 # embedding dimension H 8 # number of heads D C // H # head dimension # …

基于STM32的智能无人机自主飞行与目标识别系统设计

目录 引言系统需求分析 2.1 功能需求 2.2 硬件需求 2.3 软件需求系统设计 3.1 总体架构 3.2 各模块设计系统实现 4.1 硬件实现 4.2 软件实现系统调试与优化总结与展望 1. 引言 随着无人机技术的快速发展&#xff0c;无人机在军事侦察、环境监测、物流配送等领域的应用逐渐增多…