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

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

Python爬虫(一):爬虫伪装

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

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...

CMS内容管理系统的设计与实现:多站点模式的实现

在一套内容管理系统中&#xff0c;其实有很多站点&#xff0c;比如企业门户网站&#xff0c;产品手册&#xff0c;知识帮助手册等&#xff0c;因此会需要多个站点&#xff0c;甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...