【Leetcode】 51. N 皇后
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1:

输入: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

【补充】cpp 哈希表
C++中哈希表可以分为以下几类:
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;
}
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;
}
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;
}
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 皇后
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。 每一种…...
Java数据库连接:JDBC介绍与简单示例
Java数据库连接:JDBC介绍与简单示例 在Java程序中,操作数据库是必不可少的。JDBC(Java Database Connectivity)是Java中用于连接和操作数据库的一种技术。通过JDBC,Java程序可以与各种关系型数据库进行交互࿰…...
智慧茶园:茶厂茶园监管可视化视频管理系统解决方案
一、方案背景 我国是茶叶生产大国,茶叶销量全世界第一。随着经济社会的发展和人民生活水平的提高,对健康、天然的茶叶产品的消费需求量也在逐步提高。茶叶的种植、生产和制作过程工序复杂,伴随着人力成本的上升,传统茶厂的运营及…...
springboot整合pi支付开发
pi支付流程图: 使用Pi SDK功能发起支付由 Pi SDK 自动调用的回调函数(让您的应用服务器知道它需要发出批准 API 请求)从您的应用程序服务器到 Pi 服务器的 API 请求以批准付款(让 Pi 服务器知道您知道此付款)Pi浏览器向…...
类 ChatGPT 模型存在的局限性
尽管类ChatGPT模型经过数月的迭代和完善,已经初步融入了部分领域以及人们的日常生活,但目前市面上的产品和相关技术仍然存在一些问题,以下列出一些局限性进行详细说明与成因分析: 1)互联网上高质量、大规模、经过清洗…...
Nginx的安全控制
安全控制 关于web服务器的安全是比较大的一个话题,里面所涉及的内容很多,Nginx反向代理是安全隔离来提升web服务器的安全,通过代理分开了客户端到应用程序服务器端的连接,实现了安全措施。在反向代理之前设置防火墙,…...
字符串与字符编码 - GO语言从入门到实战
字符串与字符编码 - GO语言从入门到实战 字符串 与其他主要编程语⾔的差异 基本数据类型:string 是基础数据类型,而不是引用类型或指针类型。string 在内存中占用的空间大小是固定的,且只读、不可改变。字节切片:string 是只读…...
12P4375X042-233C KJ2005X1-BA1 CE3007 EMERSON servo controller
12P4375X042-233C KJ2005X1-BA1 CE3007 EMERSON servo controller 我们提供三种不同类别的EDGEBoost I/O模块供选择,以实现最大程度的I/O定制: 数字和模拟输入/输出网络和连接边缘人工智能和存储 利用EDGEBoost I/O实现变革性技术 EBIO-2M2BK EBIO-2M2BK载板支持…...
WPF向Avalonia迁移(四、其他事项)
开发必备 1. Avalonia项目源代码!!!!!!!!!!没有源代码,你连控件的背景色怎么改都找不着!! 2.下载你所使用的版本&#x…...
Python 代码调试
from pdb import set_trace as stx 是一个Python代码中常用的调试技巧之一,它用于在代码中插入断点以进行调试。这行代码的作用是将Python标准库中的 pdb(Python Debugger)模块中的 set_trace 函数导入,并将其重命名为 stx&#x…...
DM宣传单制作,利用在线模板,快速替换文字
如果你需要制作一批宣传单,但是时间很紧,而且没有专业的设计人员协助,那么你可以选择使用在线模板来快速制作宣传单。本文将介绍如何使用乔拓云平台,快速制作宣传单的方法。 步骤一:选择适合的在线制作工具 首先&…...
【力扣】42. 接雨水
这道题我卡了差不多1个小时,不是不会做,是不知道怎么能用栈来实现,后面看了一个博主的视频,豁然开朗,我主要的纠结点在于当指针指到7的时候,我计算出4到7的水块是2,但实际上是0,因为…...
IPETRONIK数据采集设备携手Softing Q-Vision软件致力于ADAS测试方案
一 背景 汽车ADAS技术是当下国内外的重点研究方向,且ADAS的发展水平和市场竞争力紧密相关,因此一套完善的ADAS测试方案对各整车厂而言非常重要。然而,国内ADAS测试却面临着很多阻碍,主要原因在于:相关测试设备昂贵&am…...
Go语言中的指针介绍
Go语言中的指针 文章目录 Go语言中的指针一、Go语言中的指针介绍1.1 指针介绍1.2 基本语法1.3 声明和初始化1.4 Go 指针的3个重要概念1.4.1 指针地址(Pointer Address)1.4.2 指针类型(Pointer Type)1.4.3 指针取值(Poi…...
简单理解区块链
这篇是挖矿篇详细介绍区块链之挖矿-CSDN博客的后置文章,咱们通过之前的解释进一步复习学习区块链叭! 百度百科定义 区块链,就是一个又一个区块组成的链条。每一个区块中保存了一定的信息,它们按照各自产生的时间顺序连接成链条。这…...
[尚硅谷React笔记]——第3章 React应用(基于React脚手架)
目录: react脚手架创建项目并启动react脚手架项目结构一个简单的Hello组件样式的模块化功能界面的组件化编码流程(通用)组件的组合使用-TodoList 1.react脚手架 xxx脚手架: 用来帮助程序员快速创建一个基于xxx库的模板项目 包含了所有需…...
《Linux 内核设计与实现》13. 虚拟文件系统
通用文件接口 VFS 使得可以直接使用 open()、read()、write() 这样的系统调用而无需考虑具体文件系统和实际物理介质。 好处:新的文件系统和新类型的存储介质需要挂载时,程序无需重写,甚至无需重新编译。 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; } 没有换行,不然会格式错误 第二题 #include<stdio.h>int main() {int a;s…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
