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

Leetcode打卡:N皇后

执行结果:通过

题目: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

代码以及解题思路

代码:

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:ans = []def dfs(i, a):if i == n: ans.append(['.' * j + 'Q' + '.' * (n - j - 1) for j in a])returnfor j in range(n):if all(j1 != j and j1 - i1 != j - i and j1 + i1 != j + i for i1, j1 in enumerate(a)):dfs(i + 1, a + [j])for i in range(n): dfs(1, [i])return ans

解题思路:

  1. 初始化结果列表
    • ans = []:用来存储所有满足条件的N皇后摆放方式。
  2. 定义深度优先搜索函数 dfs(i, a)
    • i:当前正在尝试放置皇后的行数(从1开始)。
    • a:一个列表,存储了到目前为止每一行皇后放置的列索引(从0开始)。
  3. 递归终止条件
    • if i == n::当i等于n时,说明已经成功地在每一行都放置了一个皇后,此时将当前摆放方式添加到结果列表中。
    • ans.append(['.' * j + 'Q' + '.' * (n - j - 1) for j in a]):将当前摆放方式转换为字符串列表,每个字符串代表棋盘的一行,'Q'表示皇后,'.'表示空位。
  4. 递归过程
    • 遍历当前行的每一列j(从0到n-1)。
    • 检查当前列j是否安全,即是否不与之前放置的皇后冲突。
      • all(j1 != j and j1 - i1 != j - i and j1 + i1 != j + i for i1, j1 in enumerate(a)):检查当前列j和之前每一行放置的皇后j1是否在同一列、同一主对角线或同一副对角线上。
    • 如果安全,则递归调用dfs(i + 1, a + [j]),将当前列j添加到已放置皇后的列索引列表中,并尝试在下一行放置皇后。
  5. 启动搜索
    • 遍历第一行的每一列i(从0到n-1),作为搜索的起点,调用dfs(1, [i])开始搜索。
  6. 返回结果
    • 返回所有满足条件的N皇后摆放方式ans

总结:

  • 这段代码通过深度优先搜索(DFS)和回溯算法,尝试在N×N的棋盘上放置N个皇后,并记录所有满足条件的摆放方式。
  • 通过递归和条件判断,确保每一行放置的皇后不与之前放置的皇后在同一列、同一主对角线或同一副对角线上。

相关文章:

Leetcode打卡:N皇后

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

Linux内核4.14版本——ccf时钟子系统(3)——ccf一些核心结构体

目录 1. struct clk_hw 2. struct clk_ops 3. struct clk_core 4. struct clk_notifier 5. struct clk 6. struct clk_gate 7. struct clk_divider 8. struct clk_mux 9. struct clk_fixed_factor 10. struct clk_fractional_divider 11. struct clk_multiplier 12…...

[Deep Learning] 深度学习中常用函数的整理与介绍(pytorch为例)

文章目录 深度学习中常用函数的整理与介绍常见损失函数1. L2_loss | nn.MSELoss()公式表示&#xff1a;特点&#xff1a;应用&#xff1a;缺点&#xff1a;主要参数&#xff1a;示例用法&#xff1a;注意事项&#xff1a; 2. L1 Loss | nn.L1Loss数学定义&#xff1a;特点&…...

【ETCD】etcd简单入门之单节点部署etcd

etcd 是一个分布式可靠的键值存储系统&#xff0c;用于分布式系统中最关键的数据&#xff0c;主要特点包括&#xff1a; 简单&#xff1a;具有明确的、面向用户的 API&#xff08;gRPC&#xff09; 安全&#xff1a;自动 TLS 支持&#xff0c;并可选的客户端证书认证 快速&am…...

Cadence基础语法

03-Cadence基础语法 0 Cadence基础语法入门&#xff1a;流程编排语言的新星 Cadence是由Uber开发的一种领域特定语言&#xff08;Domain-Specific Language&#xff0c;DSL&#xff09;&#xff0c;专门用于编写可扩展的长时间运行的业务流程。它是Temporal工作流引擎的核心组…...

GAMES101虚拟机使用教程与探讨

写在前面 环境配置请参考作业0的pdf&#xff0c;本文章主要对于配置好环境后怎么使用以及遇到的问题进行探讨&#xff08;要是有更方便的使用方式欢迎在评论区讨论&#xff09;&#xff0c;自己刚开始用的时候也折腾了好久&#xff0c;希望能为后来学习的小伙伴节约一点工具使…...

王道考研编程题总结

我还在完善中&#xff0c;边复习边完善&#xff08;这个只是根据我自身总结的&#xff09; 一、 线性表 1. 结构体 #define MaxSize 40 typedef struct{ElemType data[MaxSize]&#xff1b;int length; }SqList 2. 编程题 1. 删除最小值 题意 &#xff1a;从顺序表中删除…...

算法2--滑动窗口

滑动窗口 滑动窗口经典例题长度最小的子数组无重复字符的最长子串[最大连续1的个数 III](https://leetcode.cn/problems/max-consecutive-ones-iii/description/)[将 x 减到 0 的最小操作数](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description…...

pycharm或conda中配置镜像源

文章目录 1. 为什么要配置镜像源2. pycharm配置2.1使用pip配置国内镜像源2.2 Pycharm中更改镜像源 3.conda配置镜像源3.1 使用conda命令3.2 文件所在位置&#xff08;进行增删&#xff09;3.3 conda常用的几个命令 参考文献 1. 为什么要配置镜像源 由于Python在下载包时&#…...

C#基础之方法

文章目录 1 方法1.1 定义方法1.2 参数传递1.2.1 按值传递参数1.2.2 按引用传递参数1.2.3 按输出传递参数1.2.4 可变参数 params1.2.5 具名参数1.2.6 可选参数 1.3 匿名方法1.3.1 Lambda 表达式1.3.1.1 定义1.3.1.2 常用类型1.3.1.3 Lambda 表达式与 LINQ1.3.1.4 Lambda 表达式的…...

JVM 性能调优 -- JVM常用调优工具【jps、jstack、jmap、jstats 命令】

前言&#xff1a; 前面我们分析怎么去预估系统资源&#xff0c;怎么去设置 JVM 参数以及怎么去看 GC 日志&#xff0c;本篇我们分享一些常用的 JVM 调优工具&#xff0c;我们在进行 JVM 调优的时候&#xff0c;通常需要借助一些工具来对系统的进行相关分析&#xff0c;从而确定…...

PostgreSQL 三种关库模式

PostgreSQL 三种关库模式 基础信息 OS版本&#xff1a;Red Hat Enterprise Linux Server release 7.9 (Maipo) DB版本&#xff1a;16.2 pg软件目录&#xff1a;/home/pg16/soft pg数据目录&#xff1a;/home/pg16/data 端口&#xff1a;5777PostgreSQL 提供了三种关库模式&…...

《运放秘籍》第二部:仪表放大器专项知识点总结

一、差分放大器与仪表放大器的讨论 1.1. 仪放的前世今生——差分放大器原理&#xff1f; 1.2. 差分放大的原理 1.3. 差分放大器检测电流 1.4. 差分放大器端一&#xff1a;输入阻抗 1.5. 差分放大器端二&#xff1a;共模抑制比 1.6. 为什么关注输入阻抗&#xff1f;共模抑…...

C++STL之vector(超详细)

CSTL之vector 1.vector基本介绍2.vector重要接口2.1.构造函数2.2.迭代器2.3.空间2.3.1.resize2.3.2.capacity 2.4.增删查找 3.迭代器失效4.迭代器分类 &#x1f31f;&#x1f31f;hello&#xff0c;各位读者大大们你们好呀&#x1f31f;&#x1f31f; &#x1f680;&#x1f68…...

ubuntu环境下安装electron环境,并快速打包

1.配置镜像源 关闭防火墙&#xff0c;命令&#xff1a;sudo ufw disable 1.1配置国内镜像源&#xff1a; vim /etc/apt/source.list deb https://mirrors.aliyun.com/ubuntu/ jammy main restricted universe multiversedeb-src https://mirrors.aliyun.com/ubuntu/ jammy main…...

【Pytorch】优化器(Optimizer)模块‘torch.optim’

torch.optim 是 PyTorch 中提供的优化器&#xff08;Optimizer&#xff09;模块&#xff0c;用于优化神经网络模型的参数&#xff0c;更新网络权重&#xff0c;使得模型在训练过程中最小化损失函数。它提供了多种常见的优化算法&#xff0c;如 梯度下降法&#xff08;SGD&#…...

API平台建设之路:从0到1的实践指南

在这个互联网蓬勃发展的时代&#xff0c;API已经成为连接各个系统、服务和应用的重要纽带。搭建一个优质的API平台不仅能为开发者提供便利&#xff0c;更能创造可观的商业价值。让我们一起探讨如何打造一个成功的API平台。 技术架构是API平台的根基。选择合适的技术栈对平台的…...

【Flink-scala】DataStream编程模型之窗口计算-触发器-驱逐器

DataStream API编程模型 1.【Flink-Scala】DataStream编程模型之数据源、数据转换、数据输出 2.【Flink-scala】DataStream编程模型之 窗口的划分-时间概念-窗口计算程序 文章目录 DataStream API编程模型前言1.触发器1.1 代码示例 2.驱逐器2.1 代码示例 总结 前言 本小节我想…...

信号灯集以及 P V 操作

一、信号灯集 1.1 信号灯集的概念 信号灯集是进程间同步的一种方式。 信号灯集创建后&#xff0c;在信号灯集内部会有很多个信号灯。 每个信号灯都可以理解为是一个信号量。 信号灯的编号是从0开始的。 比如A进程监视0号灯&#xff0c;B进程监视1号灯。 0号灯有资源&…...

在 Flutter app 中,通过视频 URL 下载视频到手机相册

在 Flutter app 中&#xff0c;通过视频 URL 下载视频到手机相册可以通过以下步骤实现&#xff1a; 1. 添加依赖 使用 dio 下载文件&#xff0c;结合 path_provider 获取临时存储路径&#xff0c;以及 gallery_saver 将文件保存到相册。 在 pubspec.yaml 中添加以下依赖&…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...