【LeetCode】51. N 皇后(困难)——代码随想录算法训练营Day30

题目链接:51. N 皇后

题目描述

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

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

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

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

示例 1:

输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

输入:n = 1
输出:[["Q"]]

提示:

  • 1 <= n <= 9

文章讲解:代码随想录

视频讲解:这就是传说中的N皇后? 回溯算法安排!| LeetCode:51.N皇后_哔哩哔哩_bilibili

题解1:回溯法

思路:使用回溯法解棋盘类问题。

回溯分析:

  • 递归函数的参数和返回值:首先创建变量 res 记录结果,path 记录路径。递归函数的返回值为 void,参数为 row,表示当前遍历到第几行。
  • 递归函数的终止条件:row 和 n 相当,即遍历完整个棋盘。
  • 单层递归的逻辑:从0到 n 横向横向填充皇后,然后递归的纵向填充皇后。
  • 剪枝:当纵向、斜向已经有皇后时(因为一层层遍历行,所以行不会重复),跳过本次遍历。
/*** @param {number} n* @return {string[][]}*/
var solveNQueens = function(n) {const res = []; // 结果数组const path = new Array(n).fill().map(() => new Array(n).fill(".")); // 路径const colState = new Set(); // 列状态const leftSlantState = new Set(); // 135度斜向状态const rightSlantState = new Set(); // 45度斜向状态const backtracking = function (row) {// 当前 row 和 n 相等,说明完成整个棋盘遍历,保存结果,然后返回if (row === n) {res.push(path.map(item => item.join("")));return;}for (let i = 0; i < n; i++) {// 如果列重复或斜向重复,跳过本次遍历if (colState.has(i) || leftSlantState.has(i - row) || rightSlantState.has(i + row)) {continue;}path[row][i] = "Q"; // 记录路径colState.add(i); // 更新列状态leftSlantState.add(i - row); // 更新135度斜向状态rightSlantState.add(i + row); // 更新45度斜向状态backtracking(row + 1); // 向下查找// 回溯path[row][i] = ".";colState.delete(i);leftSlantState.delete(i - row);rightSlantState.delete(i + row);}}backtracking(0);return res;
};

分析:时间复杂度为 O(n!),空间复杂度为 O(n)。

收获

学习使用回溯法求解棋盘类问题,这类问题的路径是一个二维数组,横向遍历列,纵向遍历行。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2774669.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

day34 本地存储(重要)

目录 本地存储简介本地存储分类—— localStorage本地存储分类—— sessionStorage&#xff08;了解&#xff09;存储复杂数据类型问题1&#xff1a;本地只能存储字符串,无法存储复杂数据类型。问题2&#xff1a;因为本地存储里面取出来的是字符串&#xff0c;不是对象&#xf…

react将选中文本自动滑动到容器可视区域内

// 自动滚动到可视区域内useEffect(() > {const target ref;const wrapper wrapperRef?.current;if (target && wrapperRef) {const rect target.getBoundingClientRect();const wrapperRect wrapper.getBoundingClientRect();const isVisible rect.bottom &l…

消息队列MQ 介绍

&#x1f47d;System.out.println(“&#x1f44b;&#x1f3fc;嗨&#xff0c;大家好&#xff0c;我是代码不会敲的小符&#xff0c;双非大四&#xff0c;Java实习中…”); &#x1f4da;System.out.println(“&#x1f388;如果文章中有错误的地方&#xff0c;恳请大家指正&a…

掌握虚拟化与网络配置之道:深入浅出VMware及远程管理技巧

目录 虚拟机介绍 虚拟机的关键字 服务器架构的发展 为什么用虚拟机VMware 虚拟机和阿里云的区别 功能角度 价格因素 应用场景 优势方面 找到windows的服务管理 配置VMware 关于VMware安装的几个服务 vmware如何修改各种网络配置 关于NAT的详细信息(了解) NAT(网…

我的docker随笔43:问答平台answer部署

本文介绍开源问答社区平台Answer的容器化部署。 起因 笔者一直想搭建一个类似stack overflower这样的平台&#xff0c;自使用了Typora&#xff0c;就正式全面用MarkdownTyporagit来积累自己的个人知识库&#xff0c;但没有做到web化&#xff0c;现在也还在探索更好的方法。 无…

常见的ANSI转义码

ANSI 转义码是一组控制码&#xff0c;用于在文本中添加格式化和颜色。这些码以 ESC&#xff08;Escape&#xff09;字符为开头&#xff0c;通常是 \x1b&#xff0c;后面紧跟着一系列参数和指令。在 ANSI 标准中&#xff0c;这些码通常用于控制终端的文本输出。 下面是一些常见…

springboo冬奥会科普平台源码和论文

随着信息技术和网络技术的飞速发展&#xff0c;人类已进入全新信息化时代&#xff0c;传统管理技术已无法高效&#xff0c;便捷地管理信息。为了迎合时代需求&#xff0c;优化管理效率&#xff0c;各种各样的管理平台应运而生&#xff0c;各行各业相继进入信息管理时代&#xf…

cocos creator 3.x 预制体无法显示

双击预制体&#xff0c;进入详情页&#xff0c;没有显示资源 Bomb 是个预制体&#xff0c;但是当我双击进来什么都没有了&#xff0c;无法对预制体进行可视化编辑 目前我只试出来一个解决方法&#xff1a; 把预制体拖进Canvas文件中&#xff0c;这样就能展示到屏幕上&#xff…

为什么要设置止损

2024年1月至2月7日&#xff0c;A股最令人瞩目的事件就是代表小微盘的中证500和中证1000雪球连续敲入&#xff0c;以及万得微盘指数的崩塌&#xff08;1个月下跌50%&#xff09;。 这次的这个过程中&#xff0c;止损很重要。一般情况下&#xff0c;如果设置了20%回撤止损的话&am…

挑战杯 python opencv 深度学习 指纹识别算法实现

1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; python opencv 深度学习 指纹识别算法实现 &#x1f947;学长这里给一个题目综合评分(每项满分5分) 难度系数&#xff1a;3分工作量&#xff1a;4分创新点&#xff1a;4分 该项目较为新颖…

多线程JUC:解决线程安全问题——synchronized同步代码块、Lock锁

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位大四、研0学生&#xff0c;正在努力准备大四暑假的实习 &#x1f30c;上期文章&#xff1a;多线程&JUC&#xff1a;线程的生命周期与安全问题 &#x1f4da;订阅专栏&#xff1a;多线程&JUC 希望文章对你们有所帮…

【DC渗透系列】DC-4靶场

主机发现 arp-scan -l┌──(root㉿kali)-[~] └─# arp-scan -l Interface: eth0, type: EN10MB, MAC: 00:0c:29:6b:ed:27, IPv4: 192.168.100.251 Starting arp-scan 1.10.0 with 256 hosts (https://github.com/royhills/arp-scan) 192.168.100.1 00:50:56:c0:00:08 …

记录 | python list extend()

extend() 函数用于在列表末尾一次性追加另一个序列中的多个值&#xff08;用新列表扩展原来的列表&#xff09;。 以下实例展示了 extend()函数的使用方法&#xff1a; #!/usr/bin/pythonaList [123, xyz, zara, abc, 123]; bList [2009, manni]; aList.extend(bList)print …

大厂聚合支付系统架构演进(下)

点击下方“JavaEdge”&#xff0c;选择“设为星标” 第一时间关注技术干货&#xff01; 关注我&#xff0c;紧跟本系列专栏文章&#xff0c;咱们下篇再续&#xff01; 作者简介&#xff1a;魔都国企技术专家兼架构&#xff0c;多家大厂后端一线研发经验&#xff0c;各大技术社区…

VMware17上安装centos7.9

一、下载安装包&#xff1a; 1、VMware安装 VMware 下载地址&#xff1a; https://www.vmware.com/cn/products/workstation-pro.html VMware下载后安装即可 安装教程可以参考VMware安装教程 2、CentOs7.9下载地址&#xff1a; http://mirrors.aliyun.com/centos/7.9.2009/iso…

揭秘实战胜利秘籍!2023冬季波卡黑客松获奖团队经验分享全回顾

2023 冬季波卡黑客松大赛 已在香港圆满结束&#xff01;自 2023 年 11 月 1 日报名通道开启以来&#xff0c;2023 冬季波卡黑客松大赛一直备受全球 Web3 爱好者的瞩目。本届波卡黑客松大赛报名人数达到 342 人&#xff0c;总参赛项目高达 111 个&#xff0c;相比上一届增长 39%…

股票均线的使用方法和实战技术,看涨看空的均线形态与案例教学

一、教程描述 本套教程讲解了14种均线的特殊形态&#xff0c;通过直观图形以及大量案例的教学&#xff0c;将深奥、繁琐的均线变得生动与具体&#xff0c;广大投资者在认真学习以后&#xff0c;可以学会均线的使用方法&#xff0c;掌握最强的均线应用实战技术。本套教程不仅适…

freeRTOS总结(十四)任务通知

1、任务通知 任务通知&#xff1a; 用来通知任务的&#xff0c;任务控制块中的结构体成员变量ulNotifiedValue就是这个通知值 使用队列、信号量、事件标志组时都需另外创建一个结构体&#xff0c;通过中间的结构体进行间接通信&#xff01; 使用任务通知时&#xff0c;任务结…

【错误收录】ohpm ERROR: Install failed FetchPackageInfo: @ohos/hypium failed

创建APP的时候出现这样一个错误&#xff0c;是代理没有配置的原因 ohpm.bat install --registry https://repo.harmonyos.com/ohpm/ ohpm WARN: ETIMEDOUT Failed to search for package "ohos/hypium" from "https://repo.harmonyos.com/ohpm/", request…

教你怎么前端实现埋点上报

公众号&#xff1a;程序员白特&#xff0c;可加前端技术交流群 前言 只有了解用户&#xff0c;我们才能服务好用户&#xff0c;而最接近用户的我们&#xff0c;自然要承担起更多的责任。 那么在一个企业中&#xff0c;我们要如何去了解用户呢&#xff1f; 最直接有效的方式就是…