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

第三十天| 51. N皇后

Leetcode 51. N皇后

题目链接:51 N皇后

题干:按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

思考:回溯法。先定义结果集result,再考虑回溯函数:

函数参数含义
参数含义
n题目给定皇后个数
chessboard当前棋盘摆放情况
row当前处理行数

 终止条件:如果当前处理行数row等于n时说明皇后已全部摆放完毕,将当前棋盘摆放情况chessboard存放到结果集result中。

单层搜索逻辑:从下标0开始循环处理每个二维坐标位置,若当前行row当前列col存放皇后合法则摆放皇后,递归处理,最后回溯。

验证row行col列摆放皇后合法性:参数当前行列值,当前棋盘以及皇后个数。三处标准判断合法性:不能同行(每次处理都是不同行故此标准不用验证)、不能同列、不能同斜线 (45度和135度角)。

  • 判断同列:当前row行前面的所以行对应的col列是否摆放过皇后
  • 判断45°线:当前row行col列45°斜方向是否摆放过皇后
  • 判断135°线:当前row行col列135°斜方向是否摆放过皇后

代码:

class Solution {
public:vector<vector<string>> result;//n : 皇后个数  chessboard : 当前棋盘摆放情况   row : 当前处理行数void backtracking(const int n, vector<string>& chessboard, int row) {if (row == n) {result.push_back(chessboard);return;}for (int col = 0; col < n; col++) {if (isValid(n, chessboard, row, col)) {chessboard[row][col] = 'Q';     //摆放皇后backtracking(n, chessboard, row + 1);chessboard[row][col] = '.';     //回溯}}}//判断row行col列摆放皇后是否合法bool isValid(const int n, vector<string>& chessboard, int row, int col) {//检查此行是否摆放过皇后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;}vector<vector<string>> solveNQueens(int n) {result.clear();vector<string> chessboard(n, string(n, '.'));backtracking(n, chessboard, 0);return result;}
};

回溯法专题总结:

  •  熟悉回溯法代码整体框架。把回溯问题抽象为树形结构,其搜索的过程:for循环横向遍历,递归纵向遍历,回溯不断调整结果集。
  • 确定是否使用startIndex。对于组合问题,如果是一个集合来求组合的话,就需要startIndex;如果是多个集合取组合,各个集合之间相互不影响,那么就不用startIndex。
  • 熟悉同层去重两种方式。排序后相邻元素比较以及set容器记录使用情况。了解到节点去重,但未归纳。
  • 明确在树形结构中子集问题是要收集所有节点的结果,而组合问题是收集叶子节点的结果。

相关文章:

第三十天| 51. N皇后

Leetcode 51. N皇后 题目链接&#xff1a;51 N皇后 题干&#xff1a;按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上&#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整…...

pythn-scipy 查漏补缺

1. 2. 3. 4. 5. 6. 7. 8. 9. 偏度 skewness&#xff0c;峰度 kurtosis...

【JavaScript 漫游】【013】Date 对象知识点摘录

文章简介 本文为【JavaScript 漫游】专栏的第 013 篇文章&#xff0c;记录了 JS 语言中 Date 对象的重要知识点。 普通函数的用法构造函数的用法日期的运算静态方法&#xff0c;包括&#xff1a;Date.now()、Date.parse() 和 Date.UTC()实例方法&#xff0c;包括&#xff1a;…...

vue.config.js和webpack.config.js区别

webpack.config.js和vue.config.js的区别 webpack.config.js是webpack的配置文件&#xff0c;所有使用webpack作为打包工具的项目都可以使用&#xff0c;vue的项目可以使用&#xff0c;react的项目也可以使用。 vue.config.js是vue项目的配置文件&#xff0c;专用于vue项目。…...

H12-821_73

73.某台路由器Router LSA如图所示&#xff0c;下列说法中错误的是&#xff1f; A.本路由器的Router ID为10.0.12.1 B.本路由器为DR C.本路由器已建立邻接关系 D.本路由器支持外部路由引入 答案&#xff1a;B 注释&#xff1a; LSA中的链路信息Link ID&#xff0c;Data&#xf…...

postman执行批量测试

1.背景 有许多的人常常需要使用第三方系统进行重复的数据查询&#xff0c;本文介绍使用PostMan的方式对数据进行批量的查询&#xff0c;减少重复的劳动。 2.工具下载 3.初入门 一、如图示进行点击&#xff0c;创建collection 二、输入对应的名称 三、创建Request并进行查…...

蓝桥杯基础知识8 list

蓝桥杯基础知识8 list 01 list 的定义和结构 lits使用频率较低&#xff0c;是一种双向链表容器&#xff0c;是标准模板库&#xff08;STL&#xff09;提供的一种序列容器&#xff0c;lsit容器以节点&#xff08;node&#xff09;的形式存储元素&#xff0c;使用指针将这些节点链…...

【DDD】学习笔记-理解领域模型

Eric Evans 的领域驱动设计是对软件设计领域的一次重新审视&#xff0c;是在面向对象语言大行其道时对数据建模的“拨乱反正”。Eric 强调了模型的重要性&#xff0c;例如他在书中总结了模型在领域驱动设计中的作用包括&#xff1a; 模型和设计的核心互相影响模型是团队所有成…...

v-if 和v-show 的区别

第074个 查看专栏目录: VUE ------ element UI 专栏目标 在vue和element UI联合技术栈的操控下&#xff0c;本专栏提供行之有效的源代码示例和信息点介绍&#xff0c;做到灵活运用。 提供vue2的一些基本操作&#xff1a;安装、引用&#xff0c;模板使用&#xff0c;computed&a…...

LabVIEW网络测控系统

LabVIEW网络测控系统 介绍了基于LabVIEW的网络测控系统的开发与应用&#xff0c;通过网络技术实现了远程的数据采集、监控和控制。系统采用LabVIEW软件与网络通信技术相结合&#xff0c;提高了系统的灵活性和扩展性&#xff0c;适用于各种工业和科研领域的远程测控需求。 随着…...

攻防世界 CTF Web方向 引导模式-难度1 —— 11-20题 wp精讲

PHP2 题目描述: 暂无 根据dirsearch的结果&#xff0c;只有index.php存在&#xff0c;里面也什么都没有 index.phps存在源码泄露&#xff0c;访问index.phps 由获取的代码可知&#xff0c;需要url解码(urldecode )后验证id为admin则通过 网页工具不能直接对字母进行url编码 …...

华为Eth-Trunk级联堆叠接入IPTV网络部署案例

Eth-Trunk级联堆叠接入IPTV网络部署案例 组网图形 图2 Eth-Trunk级联堆叠IPTV基本组网图 方案简介配置注意事项组网需求数据规划配置思路操作步骤配置文件 方案简介 随着IPTV业务的迅速发展&#xff0c;IPTV平台承载的用户也越来越多&#xff0c;用户对IPTV直播业务的可靠性…...

idea: 无法创建Java Class文件(SpringBoot)已解决

第一&#xff1a;点击file-->project Sructure... 第二步&#xff1a;点击Moudules 选择自己需要创建java的文件夹&#xff08;我这里选择的是main&#xff09;右键点击Sources&#xff0c;然后点击OK即可 然后就可以创建java类了...

ChinaXiv:中科院科技论文预发布平台

文章目录 Main彩蛋 Main 主页&#xff1a;https://chinaxiv.org/home.htm 彩蛋...

【人工智能】Fine-tuning 微调:解析深度学习中的利器(7)

在深度学习领域&#xff0c;Fine-tuning 微调是一项重要而强大的技术&#xff0c;它为我们提供了在特定任务上充分利用预训练模型的途径。本文将深入讨论 Fine-tuning 的定义、原理、实际操作以及其在不同场景中的应用&#xff0c;最后简要探讨Fine-tuning 的整体架构。 1. Fi…...

黄金交易策略(Nerve Nnife):大K线对技术指标的影响

我们使用heiken ashi smoothed来做敏感指标&#xff08;大趋势借助其转向趋势预判&#xff0c;但不是马上转变&#xff09;&#xff0c;has默认使用6根k线的移动平均值来做计算的。若在6根k线规范内有一个突变的行情&#xff08;k线很长&#xff09;&#xff0c;那么整个行情的…...

django中实现数据迁移

在Django中&#xff0c;数据迁移&#xff08;data migrations&#xff09;通常指的是将模型&#xff08;models&#xff09;中的数据从一个状态迁移到另一个状态。这可以涉及很多操作&#xff0c;比如添加新字段、删除字段、更新字段的数据类型&#xff0c;或者更改表之间的关系…...

全新抖音快手小红书去水印系统网站源码 | 支持几十种平台

全新抖音快手小红书去水印系统网站源码 | 支持几十种平台...

ChatGPT炸裂了

优质内容&#xff1a;ChatGPT太炸裂了 hello&#xff0c;我是小索奇 很多人在使用ChatGPT时遇到了两个主要问题&#xff0c;导致他们觉得这个工具并没有带来太多实际价值。首先&#xff0c;许多人发现ChatGPT的回答缺乏深度&#xff0c;缺乏实用性。其次&#xff0c;一些人在使…...

小白代码审计入门

最近小白一直在学习代码审计,对于我这个没有代码审计的菜鸟来说确实是一件无比艰难的事情。但是着恰恰应了一句老话:万事开头难。但是小白我会坚持下去。何况现在已经喜欢上了代码审计,下面呢小白就说一下appcms后台模板Getshell以及读取任意文件,影响的版本是2.0.101版本。…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...