【LeetCode 刷题】回溯算法-排列问题

embedded/2025/2/4 10:12:54/

此博客为《代码随想录》二叉树章节的学习笔记,主要内容为回溯算法排列问题相关的题目解析。

文章目录

  • 46.全排列
  • 47.全排列 II

46.全排列

题目链接

python">class Solution:def permute(self, nums: List[int]) -> List[List[int]]:res, path = [], []used = [0] * len(nums)def dfs() -> None:if len(path) == len(nums):res.append(path.copy())returnnonlocal usedfor i in range(len(nums)):if used[i] == 0:used[i] = 1path.append(nums[i])dfs()path.pop()used[i] = 0dfs()return res
  • 排列问题由于需要考虑元素不同的顺序,因此从 start 升级为 used 数组,标识元素是否被使用过

47.全排列 II

题目链接

python">class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:res, path = [], []used = [0] * len(nums)nums.sort()def dfs() -> None:if len(path) == len(nums):res.append(path.copy())returnnonlocal usedfor i in range(len(nums)):if i > 0 and nums[i] == nums[i-1] and used[i-1] == 0:continueif used[i] == 0:used[i] = 1path.append(nums[i])dfs()path.pop()used[i] = 0dfs()return res
  • 添加排序和树层去重
  • 排列问题中的树层去重需要添加条件 used[i-1] == 0
    • used[i-1] == 0 说明同一树层 nums[i-1] 使用过,之后在回溯的过程中又设置为 0
    • used[i-1] == 1 说明同一树枝 nums[i-1] 使用过,已经是之前步骤的选择,对现在的选择没有影响

http://www.ppmy.cn/embedded/159437.html

相关文章

基于Docker以KRaft模式快速部署Kafka

参考文献 https://kafka.apache.org/37/documentation.html#uses https://spring.io/projects/spring-kafka#overview 获取Docker镜像 docker pull apache/kafka:3.7.1 创建一个目录来存储Kafka的配置文件 mkdir -p /home/user/kafka_config 启动Kafka容器 docker run …

OpenAI发布最新推理模型o3-mini

OpenAI于周五推出了新的AI"推理"模型o3-mini,这是该公司o系列推理模型家族的最新成员。 OpenAI此前在12月份就预告过这个模型,同时还展示了一个能力更强的系统o3。此次发布恰逢OpenAI面临诸多机遇与挑战的关键时刻。 目前,OpenAI…

爱普生L3153打印机无线连接配置流程

家里使用的是移动宽带中兴路由器,有WPS功能,进入192.168.1.1管理员页面,用户名user,密码在路由器背面(可以登录后修改密码)。在网络-WLAN网络配置-WPS中,点击push button,激活路由器…

java 字符串日期字段格式化前端显示

在 Java 应用程序中,如果你有一个字符串类型的日期字段,并希望将其格式化后显示在前端,可以通过多种方式实现。这通常涉及到在后端将字符串转换为 Date 或 LocalDateTime 等对象,然后使用适当的注解或配置来确保它们以正确的格式序…

搜索与图论复习2最短路

单源最短路---所有边权是正数(Dijkstra算法O(n^2)--稠密图(邻接矩阵)和堆优化的Dijkstra算法O(mlogn)--稀疏图(邻接表)) 或存在负边权(Bellman-ford贝尔曼福特算法O(nm)和SPFA一般O(m) 最坏O(nm) ) 多源最短路---Floyd算法O(n^3) 一、迪杰斯特拉算法(Dijkstra):1…

Dijkstra算法解析

Dijkstra算法,用于求解图中从一个起点到其他所有节点的最短路径。解决单源最短路径问题的有效方法。 条件 有向 带权路径 时间复杂度 O(n平方) 方法步骤 1 把图上的点分为两个集合 要求的起点 和除了起点之外的点 。能直达的写上权值 不…

登录认证(5):过滤器:Filter

统一拦截 上文我们提到(登录认证(4):令牌技术),现在大部分项目都使用JWT令牌来进行会话跟踪,来完成登录功能。有了JWT令牌可以标识用户的登录状态,但是完整的登录逻辑如图所示&…

Chromium132 编译指南 - Android 篇(五):获取源码

1. 引言 在前面的章节中,我们详细介绍了编译 Chromium 132 for Android 所需的系统和硬件要求,以及如何配置基础开发环境和 depot_tools。完成这些准备工作后,下一步就是获取 Chromium 的源代码。获取源代码是编译 Chromium 的关键步骤&…