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

代码随想录第22天：回溯算法4

news 来源：原创 2025/7/22 6:49:56

一、全排列（Leetcode 46）

与组合问题不同，排列问题要注意2个特点：

每层都是从0开始搜索而不是startIndex
需要used数组记录path里都放了哪些元素

class Solution:def permute(self, nums):result = []  # 存储所有的排列self.backtracking(nums, [], [False] * len(nums), result)  # 调用回溯函数开始排列生成return result  # 返回所有排列结果def backtracking(self, nums, path, used, result):# 基准条件：当路径长度等于nums长度时，说明已经生成了一个完整排列if len(path) == len(nums):result.append(path[:])  # 将当前排列添加到结果中return# 遍历每个元素，尝试放入路径中for i in range(len(nums)):# 如果nums[i]已经被使用过，跳过该元素if used[i]:continue# 标记当前元素为已使用used[i] = True# 将当前元素添加到路径中path.append(nums[i])# 递归生成下一个排列self.backtracking(nums, path, used, result)# 回溯：撤销当前选择path.pop()  # 从路径中移除当前元素used[i] = False  # 将当前元素标记为未使用，供后续递归使用

二、全排列II （Leetcode 47）

对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！

class Solution:def permuteUnique(self, nums):nums.sort()  # 排序，方便去重result = []  # 存储所有唯一排列self.backtracking(nums, [], [False] * len(nums), result)  # 调用回溯函数return result  # 返回所有排列结果def backtracking(self, nums, path, used, result):# 基准条件：路径长度等于nums长度时，说明生成了一个完整排列if len(path) == len(nums):result.append(path[:])  # 将当前路径的副本加入结果return# 遍历每个元素，尝试加入当前路径for i in range(len(nums)):# 如果当前元素与前一个相同，并且前一个元素未被使用，则跳过，避免重复排列if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]:continue# 标记当前元素为已使用used[i] = Truepath.append(nums[i])  # 将当前元素加入路径self.backtracking(nums, path, used, result)  # 递归生成下一个排列path.pop()  # 回溯，移除当前元素used[i] = False  # 将当前元素标记为未使用，供后续递归使用

三、重新安排行程（Leetcode 332）

class Solution:def findItinerary(self, tickets: List[List[str]]) -> List[str]:self.adj = {}  # 用于存储每个城市到其他城市的航班# 将航班按目的地字母排序tickets.sort(key=lambda x: x[1])# 构建每个城市的邻接表for u, v in tickets:if u in self.adj:self.adj[u].append(v)else:self.adj[u] = [v]self.result = []  # 存储结果的路径self.dfs("JFK")  # 从JFK出发return self.result[::-1]  # 结果是反向的，返回反转后的路径def dfs(self, s):# 当城市有可用航班时，继续深度优先搜索while s in self.adj and len(self.adj[s]) > 0:v = self.adj[s][0]  # 选择字母顺序最小的目的地self.adj[s].pop(0)  # 移除已使用的航班self.dfs(v)  # 从新的城市继续深度搜索self.result.append(s)  # 记录当前城市

四、N皇后（Leetcode 51）

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:result = []  # 存储最终结果的二维字符串数组，存放所有有效解# 初始化一个棋盘，棋盘是由 n 行字符串组成，每行包含 n 个 '.'，表示空位置chessboard = ['.' * n for _ in range(n)]  # 使用 '.' 表示空格self.backtracking(n, 0, chessboard, result)  # 回溯求解，起始行从0开始# 将结果中的每行列表转换成字符串并返回return [[''.join(row) for row in solution] for solution in result]  def backtracking(self, n: int, row: int, chessboard: List[str], result: List[List[str]]) -> None:# Base case: 如果已经放置了 n 个皇后，说明找到了一种解if row == n:result.append(chessboard[:])  # 将当前棋盘布局加入到结果集中return# 对当前行的每一列进行尝试for col in range(n):# 如果当前位置合法，放置皇后并递归处理下一行if self.isValid(row, col, chessboard):# 放置皇后，修改棋盘当前行的列为 'Q'chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]# 递归处理下一行self.backtracking(n, row + 1, chessboard, result)# 回溯：撤销当前皇后的放置chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]def isValid(self, row: int, col: int, chessboard: List[str]) -> bool:# 检查当前列是否已经有皇后for i in range(row):if chessboard[i][col] == 'Q':return False  # 列冲突，返回不合法# 检查 45 度角方向（左上到右下的对角线）是否有皇后i, j = row - 1, col - 1while i >= 0 and j >= 0:if chessboard[i][j] == 'Q':return False  # 45度角冲突，返回不合法i -= 1j -= 1# 检查 135 度角方向（右上到左下的对角线）是否有皇后i, j = row - 1, col + 1while i >= 0 and j < len(chessboard):if chessboard[i][j] == 'Q':return False  # 135度角冲突，返回不合法i -= 1j += 1return True  # 没有冲突，当前位置合法

代码随想录第22天：回溯算法4

一、全排列（Leetcode 46） 与组合问题不同，排列问题要注意2个特点： 每层都是从0开始搜索而不是startIndex需要used数组记录path里都放了哪些元素 class Solution:def permute(self, nums):result [] # 存储所有的排列self.back…...

编程日记 2025/7/22 6:49:56

cdq 系列题解

从二维数点（二维偏序）到三维偏序。用 cdq 分治可以解决二维数点问题。 1.洛谷 P1908 逆序对题意求所有数对 ( i , j ) (i,j) (i,j) 的个数，满足 i < j i<j i<j 且 a i > a j a_i>a_j ai>aj。 1 ≤ n ≤ 5 1…...

编程日记 2025/7/22 6:43:03

稳压二极管详解：原理、作用、应用与选型要点

一、稳压二极管的基本定义稳压二极管（齐纳二极管，Zener Diode） 是一种利用反向击穿特性实现电压稳定的半导体器件。其核心特性是：在反向击穿时，两端电压几乎恒定（Vz），且不会因电流…...

编程日记 2025/7/22 6:41:54

如何在量子计算时代保障 Sui 的安全性

量子计算的出现对依赖加密机制的系统构成了重大威胁。区块链依赖加密技术来进行身份管理、安全交易和数据完整性保护，而量子计算具备打破传统加密模型的能力，因此区块链面临特别严峻的挑战。然而，Sui 天生具备“加密灵活性”，可…...

编程日记 2025/7/22 6:40:40

linux sysfs使用cat无显示的原因：返回值未赋值

在Linux驱动中通过sysfs定义的文件使用cat命令无显示，通常由以下原因导致： 1. show函数未正确实现原因：show函数（如show_status）未正确填充缓冲区或返回有效字节数。排查： // 错误示例：未写…...

编程日记 2025/7/19 22:30:01

Discuz论坛网站忘记管理员密码进不去管理中心怎么办？怎么改管理员密码？

Discuz论坛网站忘记管理员密码进不去管理中心怎么办？怎么改管理员密码？今天驰网飞飞和你分享首先我们需要用到Discuz！急诊箱tools.php这个文件，可在下载中心搜索关键词下载，下载好后将tools.php文件放到网站根目录&a…...

编程日记 2025/7/22 6:46:58

基于LangChain与Neo4j构建企业关系图谱的金融风控实施方案，结合工商数据、供应链记录及舆情数据，实现隐性关联识别与动态风险评估

以下是基于LangChain与Neo4j构建企业关系图谱的金融风控实施方案，结合工商数据、供应链记录及舆情数据，实现隐性关联识别与动态风险评估： 一、数据整合与图谱构建多源数据融合与清洗 • 数据源：整合企业工商数据（股权…...

编程日记 2025/6/29 10:26:57

数据结构第六章（五）-拓扑排序、关键路径

数据结构第六章（五） 图的应用（二）一、有向无环图二、拓扑排序1. AOV网2. 拓扑排序3. 逆拓扑排序三、关键路径1.AOE网2.关键路径2.1 介绍2.2 关键路径的求法总结图的应用（二） 一、有向无环图首先我们得…...

编程日记 2025/6/29 10:12:20

stc32单片机实现串口2M波特率满带宽传输

我需要实现已极高的速度用串口往上位机发送数据, 并且还不能占用mcu资源, 使用的单片机位stc32g8K64 我的方法是串口接收采用中断接收, 发送采用dma自动发送, 预先初始化16个64字节的缓冲区, 每次通过串口发送时, 先找到当前的空闲缓冲区, 然后往缓冲区里填充数据, 在dma传输完…...

编程日记 2025/7/18 10:38:24

uni-app 状态管理深度解析：Vuex 与全局方案实战指南

uni-app 状态管理深度解析：Vuex 与全局方案实战指南一、Vuex 使用示例 1. 基础 Vuex 配置 1.1 项目结构 src/ ├── store/ │ ├── index.js # 主入口文件 │ └── modules/ │ └── counter.js # 计数器模块 └── main.js …...

编程日记 2025/6/29 9:40:32

STM32之DHT11温湿度传感器---附代码

DHT11简介 DHT11的供电电压为 3－5.5V。传感器上电后，要等待 1s 以越过不稳定状态在此期间无需发送任何指令。电源引脚（VDD，GND）之间可增加一个100nF 的电容，用以去耦滤波。 DATA 用于微处理器与DHT11之间…...

编程日记 2025/6/29 11:54:33

Fluent 内置双向流固耦合FSI 液舱晃荡仿真计算

本案例利用Fluent 内置双向流固耦合FSI对液舱晃荡仿真展开了计算，提供了一种更为便捷快速的分析方法，对不同杨氏模量的液舱内部构件进行分析，后续可以通过该案例对不同的双向流固耦合模型展开计算分析。 1 SCDM 设置 1.1 导入几何本案例根…...

编程日记 2025/6/29 10:37:09

嵌入式开发板调试方式完全指南：串口/SSH/Telnet及其他方式对比

文章目录 💻嵌入式开发板调试方式完全指南：串口/SSH/Telnet及其他方式对比一、为什么需要连接嵌入式开发板❓二、串口调试：最古老的调试方式仍在发光🏛️2.1 什么是串口调试？ 三、SSH/Telnet：网络时代的调试…...

编程日记 2025/6/29 12:29:40

JavaScript数据结构与算法实战: 探秘Leetcode经典题目

# JavaScript数据结构与算法实战: 探秘Leetcode经典题目第一章：掌握LeetCode经典题目什么是LeetCode？ 力扣）是一个专门为程序员提供算法题目练习的平台，涵盖了广泛的题目类型，包括数据结构、算法、数据库等多个领域。…...

编程日记 2025/6/29 11:12:55

内网穿透实践：cpolar快速入门教程

最近有个朋友联系我，问我有没有方法将自己做的项目让别人也能访问到，我寻思这不就是外网映射的事情。于是我很愉快的和他说，你去买个云服务器就行，尽管我一再和他说，个人新用户能有免费试用期，但是本着又蠢…...

编程日记 2025/7/10 6:36:14

HAL库(STM32CubeMX)——高级ADC学习、HRTIM（STM32G474RBT6）

系列文章目录文章目录系列文章目录前言存在的问题HRTIMcubemx配置前言对cubemx的ADC的设置进行补充 ADCs_Common_Settings Mode：ADC 模式 Independent mod 独立 ADC 模式，当使用一个 ADC 时是独立模式，使用两个 ADC 时是双模式，在双模式下还有很多细分模式可选 ADC_Se…...

编程日记 2025/6/29 9:41:03

Kafka 详细解读

1. Producer（生产部卷王） 职责：往 Kafka 里疯狂输出数据，KPI 是「日抛式消息海啸」职场人设： 白天开会画饼，深夜写周报的奋斗逼，口头禅是「这个需求今晚必须上线！」代码里的「福报…...

编程日记 2025/7/19 20:55:34

Python爬虫实战：获取高考网专业数据并分析，为志愿填报做参考

一、引言高考志愿填报是考生人生的关键节点，合理的志愿填报能为其未来发展奠定良好基础。计算机类专业作为当下热门领域，相关信息对考生填报志愿至关重要。教育在线网站虽提供丰富的计算机类专业数据，但存在反爬机制，增加了数据获取难度。本研究借助 Scrapy 爬虫技术及多…...

编程日记 2025/6/29 10:54:46

spd_dump使用说明源码地址：https://github.com/ilyakurdyukov/spreadtrum_flash 编译环境准备： sudo apt update sudo apt install git sudo apt install build-essential sudo apt install libusb-1.0-0-devIf you create /etc/udev/rules.d/80-spd…...

编程日记 2025/6/29 12:14:09

配置 VS Code 使用 ESLint 格式化

1、在设置里面搜索Default Formatter，下拉框里选择eslint 2、并勾选Enables ESlint as a formatter 3、再在settings.json文件中添加配置代码，如下所示： 1） 、打开 VS Code 设置快捷键：Ctrl ,（Mac: ⌘ ,…...

编程日记 2025/6/29 11:03:42

极刻云搜-专业的软件网址搜索引擎

软件名：极刻云搜版本：v1.0 软件功能：搜索实用软件和网址之前有个全网爆火的软件叫搜软但是它满屏广告而且很久都没更新了我看也有好多人在求这门类似的软件我就按照它扒了一个一模一样的软件丑是丑了点但是这个功能确实简单粗暴因为用…...

编程日记 2025/7/10 10:19:36

android Stagefright框架

作为Android音视频开发人员，学习Stagefright框架需要结合理论、源码分析和实践验证。以下是系统化的学习路径： 1. 基础准备熟悉Android多媒体体系掌握MediaPlayer、MediaCodec、MediaExtractor等核心API的用法。理解Android的OpenMAX IL&#xff08…...

编程日记 2025/6/29 11:27:18

vscode 打开新页签

目录 vscode 打开新页签完整settings.json内容： vscode 打开新页签 .vscode目录中新建settings.json 在 settings.json 文件中，添加或修改以下行： json "workbench.editor.enablePreview": false 这将禁用预览模式&#xff0…...

编程日记 2025/6/29 10:45:51

【C++编程入门】：从零开始掌握基础语法

C语言是通过对C语言不足的地方进行优化创建的，C在C语言之上，C当然也兼容C语言， 在大部分地方使用C比C更方便，可能使用C需要一两百行代码，而C只需要五六十行。目录 C关键字命名空间缺省参数缺省参数分类函数…...

编程日记 2025/6/29 10:30:33

Vue中如何优雅地阻止特定标签的移除并恢复其原始位置

Vue中如何优雅地阻止特定标签的移除并恢复其原始位置在使用 Element Plus 或 Element UI 的 <el-select> 组件时，有时我们希望根据某些条件阻止用户移除特定的标签，并且在阻止移除后将该标签重新添加到其原始位置。这在处理与子项目关联的成员时特别有用。本文将详细…...

编程日记 2025/6/29 10:43:00

基于Arduino的ESP8266连接OneNET云平台（MQTT协议物模型）（二）连接云平台

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录前言一、前期准备1.1 硬件配置1.2 软件环境配置二、接线三、核心代码3.1 总代码三、最终效果总结前言本系列将以0基础新手视角，完整演示ArduinoESP…...

编程日记 2025/7/9 21:46:48

空间注意力和通道注意力的区别

空间注意力和通道注意力是深度学习中两种常见的注意力机制。 1. 关注维度不同通道注意力（Channel Attention） 对特征图的每个通道分配不同的权重，强调“哪些通道更重要”。例如，在RGB图像中，可能红色…...

编程日记 2025/7/19 0:53:59

git 版本提交规范

Git 提交规范（Git Commit Message Convention）是为了让项目的提交历史更加清晰、可读、便于追踪和自动化工具解析。常见的规范之一是 Conventional Commits，下面是一个推荐的格式规范： 🌟 提交信息格式（Con…...

编程日记 2025/6/29 11:11:56

Linux的基础的操作指令

一.目录文件：在Linux中的以d开头的文件，就叫做目录文件(Directory): 二.普通的文件：在Linux中的以-r开头的文件，就叫做普通的文件,他们通常以.txt .cpp .c为后缀: 三.pwd:查看当前目录的绝对路径:查看当前所在位置的目录的绝对路径…...

编程日记 2025/6/29 10:03:25

级联vs端到端、全双工、轮次检测、方言语种、商业模式…语音 AI 开发者都在关心什么？丨Voice Agent 学习笔记

编者按： A16Z在《AI Voice Agents: 2025 Update》中提到： 语音是 AI 应用公司最强大的突破之一。它是人类沟通中最频繁（也是信息密度最高的）形式，AI 也让其首次变得“可编程”。在13期Z沙龙，我们聚焦AI…...

编程日记 2025/7/6 19:25:50

使用Cloudflare加速网站的具体操作步骤

要通过Cloudflare加速网站，您需要按照以下步骤进行设置和配置。这些步骤包括域名设置、接入Cloudflare、配置缓存和其他设置，以及测试网站性能。 1. 注册Cloudflare账户访问Cloudflare官网：前往 Cloudflare官网。创建账户：点击…...

编程日记 2025/7/12 10:25:45

编译原理实验（四）———— LR(1)分析法

一、实验目的掌握LR(1)分析法的基本原理与实现流程。通过构造LR(1)分析表，验证符号串是否符合给定文法规则。理解LR(1)分析中向前搜索符（Lookahead Symbol）的作用，解决移进-归约冲突。二、实验题目 1.对下列文法，用…...

编程日记 2025/6/29 11:27:17

【Redis】Jedis与Jedis连接池

目录 1. Jedis 单实例连接 2. Jedis 连接池（JedisPool） 3. JedisPool 与 Jedis 的区别 4. JedisPool 线程安全 6. 使用 JedisPool 的注意事项 1. Jedis 单实例连接在最简单的用法中，Jedis 提供了直接与 Redis 服务器连接的方式。这适合…...

编程日记 2025/7/3 23:26:52

MongoDB数据库的安装到入门使用详细讲解

本篇文章主要讲解MongoDB的安装使用教程及基础的数据库管理和操作能力的讲解，通过本篇文章您可以快速的掌握对MongDB数据库的基本认识及，基础开发能力。一、MongoDB介绍 MongoDB是一款免费开源的非关系型数据库，该数据库适应于复杂关系的存储和管理，非常适合数据结构复杂…...

编程日记 2025/6/29 10:48:46

Argo CD

文章目录一、什么是 Argo CD二、为什么选择 Argo CD三、Argo CD 架构1、API服务器2、存储库服务器3、应用程序控制器四、Argo CD 的使用1、要求2、安装 Argo CD2.1、创建 argocd 命名空间2.2、部署 Argo CD2.3、验证部署是否成功 3、下载 Argo CD CLI4、发布 Argo CD 服务器5…...

编程日记 2025/6/29 9:40:46

ElementUI中checkbox v-model绑定值为布尔、字符串或数字类型

这篇博客介绍了在Vue.js中使用El-Checkbox组件时，如何设置和处理v-model的布尔值和类型转换。通过示例代码展示了如何设置true-label和false-label属性来改变选中状态的值，适用于需要特定类型（如字符串或整数）的场景。v-model不能…...

编程日记 2025/6/29 10:27:06

Wasm Client SDK线上优化

前言随着 WebAssembly（Wasm）在前端开发中的普及，越来越多的开源项目开始在浏览器端提供高性能的逻辑处理方案。OpenIM Wasm SDK 便是其中的代表：通过将 Go 语言编写的 OpenIMSDK 核心编译为 .wasm 文件，在前端即可完成…...

编程日记 2025/6/29 11:02:37

Spring（第一章）

一，Spring介绍什么是Spring 1. 轻量级：Spring 是非侵入性的 - 基于 Spring 开发的应用中的对象可以不依赖于 Spring 的 API 2. 依赖注入(DI --- dependency injection、IOC) 3. 面向切面编程(AOP --- aspect oriented programming) 4. 容器: Spring 是…...

编程日记 2025/7/9 18:13:45

蓝桥杯 18.分考场

分考场原题目链接题目描述有 n 个人参加某项特殊考试。为了公平，要求任何两个认识的人不能分在同一个考场。你的任务是求出最少需要分几个考场才能满足这个条件。输入描述第一行：一个整数 n，表示参加考试的人数（1 ≤…...

编程日记 2025/6/29 9:41:21

大文件分片上传进阶版（新增md5校验、上传进度展示、并行控制，智能分片、加密上传、断点续传、自动重试），实现四位一体的网络感知型大文件传输系统‌

上篇文章我们总结了大文件分片上传的主要核心，但是我对md5校验和上传进度展示这块也比较感兴趣，所以在deepseek的帮助下，扩展了一下我们的代码，如果有任何问题和想法，非常欢迎大家在评论区与我交流，我需要学…...

编程日记 2025/6/29 11:48:25

【项目管理】成本类计算笔记

项目管理-相关文档，希望互相学习，共同进步风123456789～-CSDN博客 （一）知识总览项目管理知识域知识点： （项目管理概论、立项管理、十大知识域、配置与变更管理、绩效域） 对应&…...

编程日记 2025/7/5 3:00:37

Redis 事务

事务介绍 Redis 事务和 MySQL 事务在概念上类似的把一些列的操作绑定成一组，让这一组能够批量执行 MySQL 事务原子性：把多个操作打包成一个整体一致性：事务执行前后数据合理持久性：事务做出的操作都会修改硬盘隔离性&#…...

编程日记 2025/7/9 7:07:09

JavaScript day5

立即执行函数 <script>(function(){ console.log//函数不需调用，立马执行 })() </script> //另外写法 <script> (function(){}()) </script> 常见的内置对象 Math console.dir()——打印对象的使用Math中的属性——console.log(Math.…...

编程日记 2025/6/29 10:07:13

辛格迪客户案例 | 浙江高跖医药委托生产质量管理协同(OWL MAH)项目

一、案例概述浙江高跖医药科技股份有限公司是一家集“研、产、销”为一体的专业化药品持证企业。高跖医药自成立之初就建立并运行着一套相对完善的质量管理体系，涵盖了药品的研发、生产监管及销售。高跖医药于2022年选择实施了辛格迪的“委托生产质量管理协同解决…...

编程日记 2025/6/29 10:08:10

科学养生指南：解锁健康生活新方式

在快节奏的现代生活中，健康养生已成为人们关注的焦点。科学合理的养生方式，能帮助我们增强体质、预防疾病，享受更优质的生活。饮食是健康养生的基石。遵循 “均衡饮食” 原则，每日饮食需包含谷类、蔬菜水果、优质蛋白质和健康…...

编程日记 2025/7/19 3:56:13

FreeRTos学习记录--2.内存管理

后续的章节涉及这些内核对象：task、queue、semaphores和event group等。为了让FreeRTOS更容易使用，这些内核对象一般都是动态分配：用到时分配，不使用时释放。使用内存的动态管理功能，简化了程序设计：不再需…...

编程日记 2025/6/29 11:03:41

C++ 操作符重载Operator

C可以重载大多数操作符，如算术运算符号，-号。位操作符<<,>> 下标符号[]等都可以重载。重载的意思，是让这些符号，按你定义的行为来执行代码，但是这种自定义，是有限制的，必须有一…...

编程日记 2025/6/29 10:46:51

SBTI科学碳目标认证有什么要求？SBTI认证的好处？

SBTi（科学碳目标倡议）认证要求与好处 SBTi（Science Based Targets initiative，科学碳目标倡议）是由全球环境信息研究中心（CDP）、联合国全球契约（UNGC）、世界资源研究所&…...

编程日记 2025/6/29 9:41:01

RS232转Profibus DP网关：技术革新！

RS232转Profibus DP网关：技术革新！ 在工业自动化领域，通讯协议的多样性为系统设计提供了灵活性，但同时也带来了不同设备间通信的挑战。其中，RS232和Profibus DP是两种广泛应用的通讯协议。RS232，作为一种串…...

编程日记 2025/7/15 1:37:33

XAML基本语法与例子

XAML (eXtensible Application Markup Language) 是一种基于 XML 的声明性语言，主要用于 WPF、UWP、Xamarin.Forms 和 MAUI 等框架中构建用户界面。基本语法结构 1. 根元素和命名空间声明 <Page x:Class"MyNamespace.MyPage"xmlns"http://sch…...

编程日记 2025/7/13 23:24:11

一、全排列（Leetcode 46）

二、全排列II （Leetcode 47）

三、重新安排行程（Leetcode 332）

四、N皇后（Leetcode 51）

相关文章：