当前位置: 首页 > 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…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

C++_哈希表

本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、基础概念 1. 哈希核心思想&#xff1a; 哈希函数的作用&#xff1a;通过此函数建立一个Key与存储位置之间的映射关系。理想目标&#xff1a;实现…...