【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…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
基于鸿蒙(HarmonyOS5)的打车小程序
1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

Spring AOP代理对象生成原理
代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】,这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...