当前位置: 首页 > news >正文

【Leetcode】 51. N 皇后

按照国际象棋的规则,皇后可以攻击与之处在同一行同一列同一斜线上的棋子。

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

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q''.' 分别代表了皇后空位

示例 1
answer
输入n = 4
输出[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2

输入n = 1
输出[["Q"]]

提示

1 <= n <= 9

已经不是第一次遇到 N 皇后问题了,依稀记得三年前的暑假,刚接触 c++的自己,看着 N 皇后别人 AC 掉的代码,天书一般,留下的知识满眼的钦佩!

  • 愿与君共勉!

事实上,现在看来,N 皇后问题相比其他的回溯算法题,hard点在于它使用的是二维数组,回溯的思路是不变的!

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}
  • 参数选择 -> 回溯终止条件 -> 单层处理logic

值得一提的是 每列棋子放置的合理性判别,即 isValid的函数实现。


AC

/** @lc app=leetcode.cn id=51 lang=cpp** [51] N 皇后*/// @lc code=start
class Solution {
private:vector<vector<string>> result;bool isValid(int row, int col, vector<string>& chessboard, int n) {// 检查列for(int i = 0; i < row; i++) {if(chessboard[i][col] == 'Q')return false;}// 检查45°角for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if(chessboard[i][j] == 'Q')return false;}// 检查135°角for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if(chessboard[i][j] == 'Q')return false;}return true;}void backtracking(int n, int row, vector<string>& chessboard) {if(n == row) {result.push_back(chessboard);return ;}for(int col = 0; col < n; col++) {if(isValid(row, col, chessboard, n)) {chessboard[row][col] = 'Q';backtracking(n, row + 1, chessboard);chessboard[row][col] = '.';}}}
public:vector<vector<string>> solveNQueens(int n) {result.clear();std::vector<std::string> chessboard(n, std::string(n, '.'));backtracking(n, 0, chessboard);return result;}
};
// @lc code=end

AC


【补充】cpp 哈希表
C++中哈希表可以分为以下几类:

  1. unordered_map :基于哈希表实现的 Key-Value 映射容器,支持快速的插入、查找和删除操作。

下面是 unordered_map 常见的使用方式:

#include <unordered_map>
#include <string>
using namespace std;int main() {// 创建一个空的unordered_mapunordered_map<string, int> umap;// 插入元素umap["apple"] = 10;umap.insert(make_pair("orange", 20));// 访问元素int apple_price = umap["apple"];int orange_price = umap.at("orange");// 遍历元素for (auto it = umap.begin(); it != umap.end(); it++) {cout << it->first << " : " << it->second << endl;}// 删除元素umap.erase("apple");umap.clear();return 0;
}
  1. unordered_set :基于哈希表实现的无序集合容器,支持快速的插入、查找和删除操作。和 unordered_map 相似,只是不需要存储键值对。

下面是 unordered_set 常见的使用方式:

#include <unordered_set>
#include <string>
using namespace std;int main() {// 创建一个空的unordered_setunordered_set<string> uset;// 插入元素uset.insert("apple");uset.insert("orange");// 查找元素if (uset.find("apple") != uset.end()) {cout << "Found apple!" << endl;}// 遍历元素for (auto it = uset.begin(); it != uset.end(); it++) {cout << *it << endl;}// 删除元素uset.erase("apple");uset.clear();return 0;
}
  1. unordered_multimap :基于哈希表实现的 Key-Value 映射容器,支持插入重复的 Key,每个 Key 对应多个 Value。和 unordered_map 相似,只是可以插入重复 Key 和多个 Value。

下面是 unordered_multimap 常见的使用方式:

#include <unordered_map>
#include <string>
using namespace std;int main() {// 创建一个空的unordered_multimapunordered_multimap<string, int> umap;// 插入元素umap.insert(make_pair("apple", 10));umap.insert(make_pair("orange", 20));umap.insert(make_pair("apple", 30));// 访问元素auto range = umap.equal_range("apple");for (auto it = range.first; it != range.second; it++) {cout << it->first << " : " << it->second << endl;}// 遍历元素for (auto it = umap.begin(); it != umap.end(); it++) {cout << it->first << " : " << it->second << endl;}// 删除元素umap.erase("apple");umap.clear();return 0;
}
  1. unordered_multiset :基于哈希表实现的无序集合容器,支持插入重复的元素。和 unordered_set 相似,只是可以插入重复元素。

下面是 unordered_multiset 常见的使用方式:

#include <unordered_set>
#include <string>
using namespace std;int main() {// 创建一个空的unordered_multisetunordered_multiset<string> uset;// 插入元素uset.insert("apple");uset.insert("orange");uset.insert("apple");// 查找元素if (uset.count("apple") > 0) {cout << "Found apple!" << endl;}// 遍历元素for (auto it = uset.begin(); it != uset.end(); it++) {cout << *it << endl;}// 删除元素uset.erase("apple");uset.clear();return 0;
}

以上是哈希表的四种常见用法,需要根据具体业务场景选择相应的容器。

相关文章:

【Leetcode】 51. N 皇后

按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上&#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整数 n &#xff0c;返回所有不同的 n 皇后问题 的解决方案。 每一种…...

Java数据库连接:JDBC介绍与简单示例

Java数据库连接&#xff1a;JDBC介绍与简单示例 在Java程序中&#xff0c;操作数据库是必不可少的。JDBC&#xff08;Java Database Connectivity&#xff09;是Java中用于连接和操作数据库的一种技术。通过JDBC&#xff0c;Java程序可以与各种关系型数据库进行交互&#xff0…...

智慧茶园:茶厂茶园监管可视化视频管理系统解决方案

一、方案背景 我国是茶叶生产大国&#xff0c;茶叶销量全世界第一。随着经济社会的发展和人民生活水平的提高&#xff0c;对健康、天然的茶叶产品的消费需求量也在逐步提高。茶叶的种植、生产和制作过程工序复杂&#xff0c;伴随着人力成本的上升&#xff0c;传统茶厂的运营及…...

springboot整合pi支付开发

pi支付流程图&#xff1a; 使用Pi SDK功能发起支付由 Pi SDK 自动调用的回调函数&#xff08;让您的应用服务器知道它需要发出批准 API 请求&#xff09;从您的应用程序服务器到 Pi 服务器的 API 请求以批准付款&#xff08;让 Pi 服务器知道您知道此付款&#xff09;Pi浏览器向…...

类 ChatGPT 模型存在的局限性

尽管类ChatGPT模型经过数月的迭代和完善&#xff0c;已经初步融入了部分领域以及人们的日常生活&#xff0c;但目前市面上的产品和相关技术仍然存在一些问题&#xff0c;以下列出一些局限性进行详细说明与成因分析&#xff1a; 1&#xff09;互联网上高质量、大规模、经过清洗…...

Nginx的安全控制

安全控制 关于web服务器的安全是比较大的一个话题&#xff0c;里面所涉及的内容很多&#xff0c;Nginx反向代理是安全隔离来提升web服务器的安全&#xff0c;通过代理分开了客户端到应用程序服务器端的连接&#xff0c;实现了安全措施。在反向代理之前设置防火墙&#xff0c;…...

字符串与字符编码 - GO语言从入门到实战

字符串与字符编码 - GO语言从入门到实战 字符串 与其他主要编程语⾔的差异 基本数据类型&#xff1a;string 是基础数据类型&#xff0c;而不是引用类型或指针类型。string 在内存中占用的空间大小是固定的&#xff0c;且只读、不可改变。字节切片&#xff1a;string 是只读…...

12P4375X042-233C KJ2005X1-BA1 CE3007 EMERSON servo controller

12P4375X042-233C KJ2005X1-BA1 CE3007 EMERSON servo controller 我们提供三种不同类别的EDGEBoost I/O模块供选择&#xff0c;以实现最大程度的I/O定制: 数字和模拟输入/输出网络和连接边缘人工智能和存储 利用EDGEBoost I/O实现变革性技术 EBIO-2M2BK EBIO-2M2BK载板支持…...

WPF向Avalonia迁移(四、其他事项)

开发必备 1. Avalonia项目源代码&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;没有源代码&#xff0c;你连控件的背景色怎么改都找不着&#xff01;&#xff01; 2.下载你所使用的版本&#x…...

Python 代码调试

from pdb import set_trace as stx 是一个Python代码中常用的调试技巧之一&#xff0c;它用于在代码中插入断点以进行调试。这行代码的作用是将Python标准库中的 pdb&#xff08;Python Debugger&#xff09;模块中的 set_trace 函数导入&#xff0c;并将其重命名为 stx&#x…...

DM宣传单制作,利用在线模板,快速替换文字

如果你需要制作一批宣传单&#xff0c;但是时间很紧&#xff0c;而且没有专业的设计人员协助&#xff0c;那么你可以选择使用在线模板来快速制作宣传单。本文将介绍如何使用乔拓云平台&#xff0c;快速制作宣传单的方法。 步骤一&#xff1a;选择适合的在线制作工具 首先&…...

【力扣】42. 接雨水

这道题我卡了差不多1个小时&#xff0c;不是不会做&#xff0c;是不知道怎么能用栈来实现&#xff0c;后面看了一个博主的视频&#xff0c;豁然开朗&#xff0c;我主要的纠结点在于当指针指到7的时候&#xff0c;我计算出4到7的水块是2&#xff0c;但实际上是0&#xff0c;因为…...

IPETRONIK数据采集设备携手Softing Q-Vision软件致力于ADAS测试方案

一 背景 汽车ADAS技术是当下国内外的重点研究方向&#xff0c;且ADAS的发展水平和市场竞争力紧密相关&#xff0c;因此一套完善的ADAS测试方案对各整车厂而言非常重要。然而&#xff0c;国内ADAS测试却面临着很多阻碍&#xff0c;主要原因在于&#xff1a;相关测试设备昂贵&am…...

Go语言中的指针介绍

Go语言中的指针 文章目录 Go语言中的指针一、Go语言中的指针介绍1.1 指针介绍1.2 基本语法1.3 声明和初始化1.4 Go 指针的3个重要概念1.4.1 指针地址&#xff08;Pointer Address&#xff09;1.4.2 指针类型&#xff08;Pointer Type&#xff09;1.4.3 指针取值&#xff08;Poi…...

简单理解区块链

这篇是挖矿篇详细介绍区块链之挖矿-CSDN博客的后置文章&#xff0c;咱们通过之前的解释进一步复习学习区块链叭&#xff01; 百度百科定义 区块链&#xff0c;就是一个又一个区块组成的链条。每一个区块中保存了一定的信息&#xff0c;它们按照各自产生的时间顺序连接成链条。这…...

[尚硅谷React笔记]——第3章 React应用(基于React脚手架)

目录&#xff1a; react脚手架创建项目并启动react脚手架项目结构一个简单的Hello组件样式的模块化功能界面的组件化编码流程&#xff08;通用&#xff09;组件的组合使用-TodoList 1.react脚手架 xxx脚手架: 用来帮助程序员快速创建一个基于xxx库的模板项目 包含了所有需…...

《Linux 内核设计与实现》13. 虚拟文件系统

通用文件接口 VFS 使得可以直接使用 open()、read()、write() 这样的系统调用而无需考虑具体文件系统和实际物理介质。 好处&#xff1a;新的文件系统和新类型的存储介质需要挂载时&#xff0c;程序无需重写&#xff0c;甚至无需重新编译。 VFS 将各种不同的文件系统抽象后采…...

2021-06-09 51单片机:两个独立按键控制一个led,k1按下松开led闪烁三次,k2按下LED闪烁五次

缘由51单片机:两个独立按键控制一个led,k1按下松开led闪烁三次,k2按下LED闪烁五次_嵌入式-CSDN问答 #include "REG52.h" sbit K1 P1^0; sbit K2 P1^1; sbit LEDP0^0; void main() {unsigned char Xd0,ss0;unsigned int wei0;while(1){if(K10&&Xd0){ss3*2;…...

C/C++ 经典面试算法题

1.打印杨辉三角 1 #include <stdio.h>2 #include <string.h>3 4 int main()5 {6 int x;7 int a[100][100];8 printf("输入行数\n");9 scanf("%d",&x); 10 for(int i 0;i<x;i) 11 { 12 for(int j 0;…...

2023年下学期《C语言》作业0x02-分支 XTU OJ 1068 1069 1070 1071 1072

第一题 #include<stdio.h>int main() {int a;scanf("%d",&a);if(a>90&&a<100) printf("A");else printf("B");return 0; } 没有换行&#xff0c;不然会格式错误 第二题 #include<stdio.h>int main() {int a;s…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

【Android】Android 开发 ADB 常用指令

查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...