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

leetcode 困难 —— N 皇后(简单递归)

(不知道为啥总是给这种简单的递归设为困难题,虽然优化部分很不错,但是题目太好过了)

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

题解:
首先看眼数据范围,1 <= n <= 9,这么小的数据,估计就是枚举了

那我们怎么枚举呢,遍历在前 i 行已经确定的情况下,第 i + 1 行所有可取的情况
(第 0 行则每一列所有都可取)

那我们怎么判断可不可取呢
① 该列和以前行的列重合
② 该列和以前行的列在一条斜线上(当前行 - 以前行 = | 当前列 - 以前列 |)

然后我们把以前的行的选择列,用一个字符串表示即可
例 “13524”,第一行选第一列,第二行选第三列…

代码如下:

class Solution {
public:vector<string> solve(string pre, int n) {vector<string> res;bool flag[10];for(int i = 0; i < n; i++) {flag[i] = true;}int m = pre.size();for(int i = 0; i < m; i++) {flag[pre[i] - '0'] = false;if(pre[i] - '0' - m + i >= 0) flag[pre[i] - '0' - m + i] = false;if(pre[i] - '0' + m - i < n) flag[pre[i] - '0' + m - i] = false;}vector<string> temp;for(int i = 0; i < n; i++) {if(flag[i] && m != n - 1) {temp = solve(pre + char(i + '0'), n);res.insert(res.end(), temp.begin(), temp.end());}else if(flag[i] && m == n - 1) {res.push_back(pre + char(i + '0'));}}return res;}vector<vector<string>> solveNQueens(int n) {vector<vector<string> > res;vector<string> t = solve("", n);for(int i = 0; i < t.size(); i++) {vector<string> temp;for(int j = 0; j < n; j++) {string str = "";for(int k = 0; k < n; k++) {if(k != t[i][j] - '0') {str = str + '.';}else {str = str + 'Q';}}temp.push_back(str);}res.push_back(temp);}return res;}
};

接下来,我们考虑优化

在这里插入图片描述

有没有觉得,这个很像二进制的位移

我们用三个二进制数字分别表示,在左斜线上的,在右斜线上的,在一条直线上的
每一个二进制数字都是表示当前行的状态

接下来每过一行,我们二进制位移一次即可(表示直线上的不用二进制位移)
这样空间和时间复杂度都降低了

相关文章:

leetcode 困难 —— N 皇后(简单递归)

&#xff08;不知道为啥总是给这种简单的递归设为困难题&#xff0c;虽然优化部分很不错&#xff0c;但是题目太好过了&#xff09; 题目&#xff1a; 按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个…...

AWS实战:Dynamodb到Redshift数据同步

AWS Dynamodb简介 Amazon DynamoDB 是一种完全托管式、无服务器的 NoSQL 键值数据库&#xff0c;旨在运行任何规模的高性能应用程序。DynamoDB能在任何规模下实现不到10毫秒级的一致响应&#xff0c;并且它的存储空间无限&#xff0c;可在任何规模提供可靠的性能。DynamoDB 提…...

机器学习评估指标的十个常见面试问题

评估指标是用于评估机器学习模型性能的定量指标。它们提供了一种系统和客观的方法来比较不同的模型并衡量它们在解决特定问题方面的成功程度。通过比较不同模型的结果并评估其性能可以对使用哪些模型、如何改进现有模型以及如何优化给定任务的性能做出正确的决定&#xff0c;所…...

常见的安全问题汇总 学习记录

声明 本文是学习2017中国网站安全形势分析报告. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 2017年重大网站安全漏洞 CVE-2017-3248 &#xff1a;WebLogic 远程代码执行 2017年1月27日&#xff0c;WebLogic官方发布了一个编号为CVE-2017-3248 的…...

元宵晚会节目预告没有岳云鹏,是不敢透露还是另有隐情

在刚刚结束的元宵节晚会上&#xff0c;德云社的岳云鹏&#xff0c;再一次参加并引起轰动&#xff0c;并获得了观众朋友们的一致好评。 不过有细心的网友发现&#xff0c;早前央视元宵晚会节目预告&#xff0c;并没有看到小岳岳&#xff0c;难道是不敢提前透露&#xff0c;怕公布…...

计算机视觉 吴恩达 week 10 卷积

文章目录一、边缘检测二、填充 padding1、valid convolution2、same convolution三、卷积步长 strided convolution四、三维卷积五、池化层 pooling六、 为什么要使用卷积神经网络一、边缘检测 可以通过卷积操作来进行 原图像 n✖n 卷积核 f✖f 则输出的图像为 n-f1 二、填充…...

JavaScript 函数定义

JavaScript 函数定义 函数是 JavaScript 中的基本组件之一。一个函数是 JavaScript 过程 — 一组执行任务或计算值的语句。要使用一个函数&#xff0c;你必须将其定义在你希望调用它的作用域内。 一个 JavaScript 函数用function关键字定义&#xff0c;后面跟着函数名和圆括号…...

设计模式:建造者模式教你创建复杂对象

一、问题场景 当我们需要创建资源池配置对象的时候&#xff0c;资源池配置类里面有以下成员变量: 如果我们使用new关键字调用构造函数&#xff0c;构造函数参数列表就会太长。 如果我们使用set方法设置字段值&#xff0c;那minIdle<maxIdle<maxTotal的约束逻辑就没地方…...

在C++中将引用转换为指针表示

在C中将引用转换为指针表示 有没有办法在c 中"转换"对指针的引用&#xff1f;在下面的例子,func2已经定义了原型和我不能改变它,但func是我的API,我想为pass两个参数,或一(组和第二组,以NULL)或既不(均设置为NULL): void func2(some1 *p1, some2 *p2); func(some1…...

PS快速入门系列

01-界面构成 1菜单栏 2工具箱 3工县属性栏 4悬浮面板 5画布 ctr1N新建对话框&#xff08;针对画布进行设置&#xff09; 打开对话框&#xff1a;ctrl0&#xff08;字母&#xff09; 画布三种显示方式切换&#xff1a;F 隐藏工具箱&#xff0c;工具属性栏&#xff0c;悬浮面板…...

ASP.NET CORE 3.1 MVC“指定的网络名不再可用\企图在不存在的网络连接上进行操作”的问题解决过程

ASP.NET CORE 3.1 MVC“指定的网络名不再可用\企图在不存在的网络连接上进行操作”的问题解决过程 我家里的MAC没这个问题。这个是在windows上发生的。 起因很简单我用ASP.NET CORE 3.1 MVC做个项目做登录将数据从VIEW post到Controller上结果意外的报了错误。 各种百度都说…...

JVM从看懂到看开Ⅲ -- 类加载与字节码技术【下】

文章目录编译期处理默认构造器自动拆装箱泛型集合取值可变参数foreach 循环switch 字符串switch 枚举枚举类try-with-resources方法重写时的桥接方法匿名内部类类加载阶段加载链接初始化相关练习和应用类加载器类与类加载器启动类加载器拓展类加载器双亲委派模式自定义类加载器…...

服务器常用的41个状态码及其对应的含义

服务器常用的状态码及其对应的含义如下&#xff1a; 100——客户必须继续发出请求 101——客户要求服务器根据请求转换HTTP协议版本 200——交易成功 201——提示知道新文件的URL 202——接受和处理、但处理未完成 203——返回信息不确定或不完整 204——请求收到&#…...

万里数据库加入龙蜥社区,打造基于“龙蜥+GreatSQL”的开源技术底座

近日&#xff0c;北京万里开源软件有限公司&#xff08;以下简称“万里数据库”&#xff09;及 GreatSQL 开源社区签署了 CLA&#xff08;Contributor License Agreement&#xff0c;贡献者许可协议&#xff09;&#xff0c;正式加入龙蜥社区&#xff08;OpenAnolis&#xff09…...

为什么不推荐使用CSDN?

CSDN粪坑 94%的讲得乱七八糟前言不搭后语互相矛盾的垃圾&#xff08;还包含直接复制粘贴其他源的内容&#xff09;3%的纯搬运&#xff08;偷窃&#xff09;2%个人日记 &#xff08;以上99%中还夹杂着很多明明都是盗版资源还要上传卖钱的 &#xff09; 1%黄金程序员时间有限&am…...

apisix 初体验

文章目录前言一、参考资料二、安装1.安装依赖2.安装apisix 2.53.apisix dashboard三、小试牛刀3.1 上游&#xff08;upstream&#xff09;3.2 路由&#xff08;route&#xff09;四、遇到的问题前言 APISIX 是一个微服务API网关&#xff0c;具有高性能、可扩展性等优点。它基于…...

time时间模块

time时间模块 目录time时间模块1.概述2.查看不同类型的时钟3.墙上时钟time3.1.time()当前时间戳3.2.ctime()格式化时间4.单调时钟计算测量时间5.cpu处理器时钟时间6.性能计数器7.时间组成8.处理时区9.解析和格式化时间1.概述 time模块允许访问多种类型的时钟&#xff0c;分别用…...

如何判断反馈电路的类型-反馈类型-三极管

如何判断反馈电路的类型 反馈电路类型很多&#xff0c;可根据不同的标准分类&#xff1a; ①根据反馈的极性分&#xff1a;有正反馈和负反馈。 ②根据反馈信号和输出信号的关系分&#xff1a;有电压反馈和电流反馈。 ③根据反馈信号和输入信号的关系分&#xff1a;有串联反…...

C++ 实现生命游戏 Live Game

#include"stdlib.h" #include"time.h" #include"unistd.h" using namespace std; #define XSIZE 80 #define YSIZE 30 #include"iostream" using namespace std ; // 初始化生命 void initLive(int a[YSIZE][XSIZE]) { // …...

什么是QoS?QoS是如何工作的?QoS的实验配置如何进行?

QoS&#xff08;Quality of Service&#xff09;是服务质量的简称。对于网络业务来说&#xff0c;服务质量包括哪些方面呢&#xff1f; 从传统意义上来讲&#xff0c;无非就是传输的带宽、传送的时延、数据的丢包率等&#xff0c;而提高服务质量无非也就是保证传输的带宽&…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...