当前位置: 首页 > 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;而提高服务质量无非也就是保证传输的带宽&…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...

GraphRAG优化新思路-开源的ROGRAG框架

目前的如微软开源的GraphRAG的工作流程都较为复杂&#xff0c;难以孤立地评估各个组件的贡献&#xff0c;传统的检索方法在处理复杂推理任务时可能不够有效&#xff0c;特别是在需要理解实体间关系或多跳知识的情况下。先说结论&#xff0c;看完后感觉这个框架性能上不会比Grap…...

起重机起升机构的安全装置有哪些?

起重机起升机构的安全装置是保障吊装作业安全的关键部件&#xff0c;主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理&#xff1a; 一、超载保护装置&#xff08;核心安全装置&#xff09; 1. 起重量限制器 功能&#xff1a;实时监测起升载荷&a…...