LeetCodehot 力扣热题100 全排列
这段代码的目的是计算给定整数数组的所有全排列(permutations),并返回一个包含所有排列的二维数组。
思路解析
在这段代码中,采用了 深度优先搜索(DFS) 和 回溯 的方法来生成所有的排列。
关键步骤:
1. 回溯:我们通过交换数组中的元素,将数组的每个元素依次放置到每个位置,生成所有的排列组合。
2. 递归:每次递归处理当前索引位置的元素,继续处理下一个位置,直到递归到数组的末尾,表示完成一个排列。
3. 交换回溯:在每次递归后,通过交换操作还原数组的顺序,避免对后续递归产生影响。
代码解析
class Solution {public:vector<vector<int>> ans; // 用于存储所有的排列vector<vector<int>> permute(vector<int>& nums) {dfs(nums, 0); // 从数组的第一个位置开始深度优先搜索return ans; // 返回所有的排列}void dfs(vector<int>& nums, int n) {// 如果当前的索引等于数组的长度,说明已经形成了一个排列if (n == nums.size()) {ans.push_back(nums); // 将当前排列加入结果集中return;}// 遍历当前索引位置后的所有元素for (int i = n; i < nums.size(); i++) {swap(nums[i], nums[n]); // 将第 i 个元素与第 n 个元素交换dfs(nums, n + 1); // 递归处理下一个位置swap(nums[i], nums[n]); // 交换回去,恢复原数组状态(回溯)}}};
详细注释
1. vector<vector<int>> ans;:
• 用于存储所有的排列组合。
2. vector<vector<int>> permute(vector<int>& nums):
• permute 是主函数,接受一个整数数组 nums 作为输入,返回一个包含所有排列的二维数组。
• dfs(nums, 0) 从 nums 的第 0 个位置开始深度优先搜索。
3. void dfs(vector<int>& nums, int n):
• dfs 是深度优先搜索的核心函数,负责递归生成排列。
• nums 是待排列的数组,n 是当前递归处理的索引位置。
4. if (n == nums.size()):
• 如果当前的索引 n 等于数组的大小,说明已经将所有元素排列完毕,形成了一个有效的排列。
• ans.push_back(nums) 将当前的排列(即 nums 数组的状态)加入结果集 ans。
5. for (int i = n; i < nums.size(); i++):
• 遍历当前索引 n 之后的每一个元素,通过交换生成不同的排列。
6. swap(nums[i], nums[n]);:
• 交换 nums[i] 和 nums[n],将 nums[i] 放到当前的位置 n。这样可以生成一个新的排列组合。
7. dfs(nums, n + 1):
• 递归调用 dfs,将处理下一个位置的元素。即当前元素已放置好,继续处理下一个索引。
8. swap(nums[i], nums[n]);:
• 交换回去,恢复原数组状态,这样可以进行下一轮的排列生成(即回溯)。这是为了确保后续的排列生成不会受到之前交换的影响。
好的,接下来我会详细地继续补充并完成整个 深度优先搜索(DFS) 和 回溯 的运行步骤,直到所有排列都生成完毕。
输入数组:
nums = [1, 2, 3]
运行步骤:
我们通过 DFS 和回溯的方法生成 nums 数组的所有排列。
初始状态:
• 输入:nums = [1, 2, 3]
• ans = [](最终存储所有排列的结果)
第 1 层递归:n = 0 (处理第一个位置)
• 当前节点的起始值是 nums = [1, 2, 3],n = 0,遍历 i = 0 到 i = 2。
1. 第 1 次交换:swap(nums[0], nums[0]),数组未变,仍为 [1, 2, 3]。
• 递归调用 dfs(nums, 1),进入处理第二个位置。
第 2 层递归:n = 1 (处理第二个位置)
• 当前节点的起始值是 nums = [1, 2, 3],n = 1,遍历 i = 1 到 i = 2。
1. 第 1 次交换:swap(nums[1], nums[1]),数组未变,仍为 [1, 2, 3]。
• 递归调用 dfs(nums, 2),进入处理第三个位置。
第 3 层递归:n = 2 (处理第三个位置)
• 当前节点的起始值是 nums = [1, 2, 3],n = 2,遍历 i = 2 到 i = 2(只剩下一个位置)。
1. 第 1 次交换:swap(nums[2], nums[2]),数组未变,仍为 [1, 2, 3]。
• 递归调用 dfs(nums, 3),这时 n == nums.size(),说明当前排列已经完成。
2. 将 [1, 2, 3] 加入到 ans 中。
• ans = [[1, 2, 3]]
回溯:恢复状态
• 交换回去,恢复原数组 [1, 2, 3]。
• 返回到 n = 1,继续处理 i = 2。
2. 第 2 次交换:swap(nums[1], nums[2]),数组变为 [1, 3, 2]。
• 递归调用 dfs(nums, 2),进入处理第三个位置。
第 3 层递归:n = 2 (处理第三个位置)
• 当前节点的起始值是 nums = [1, 3, 2],n = 2,遍历 i = 2 到 i = 2(只剩下一个位置)。
1. 第 1 次交换:swap(nums[2], nums[2]),数组未变,仍为 [1, 3, 2]。
• 递归调用 dfs(nums, 3),这时 n == nums.size(),说明当前排列已经完成。
2. 将 [1, 3, 2] 加入到 ans 中。
• ans = [[1, 2, 3], [1, 3, 2]]
回溯:恢复状态
• 交换回去,恢复原数组 [1, 3, 2]。
• 返回到 n = 1,恢复原数组 [1, 2, 3]。
• 返回到 n = 0,恢复原数组 [1, 2, 3]。
第 2 次交换:n = 0 (处理第一个位置)
3. 第 2 次交换:swap(nums[0], nums[1]),数组变为 [2, 1, 3]。
• 递归调用 dfs(nums, 1),进入处理第二个位置。
第 2 层递归:n = 1 (处理第二个位置)
• 当前节点的起始值是 nums = [2, 1, 3],n = 1,遍历 i = 1 到 i = 2。
1. 第 1 次交换:swap(nums[1], nums[1]),数组未变,仍为 [2, 1, 3]。
• 递归调用 dfs(nums, 2),进入处理第三个位置。
第 3 层递归:n = 2 (处理第三个位置)
• 当前节点的起始值是 nums = [2, 1, 3],n = 2,遍历 i = 2 到 i = 2(只剩下一个位置)。
1. 第 1 次交换:swap(nums[2], nums[2]),数组未变,仍为 [2, 1, 3]。
• 递归调用 dfs(nums, 3),这时 n == nums.size(),说明当前排列已经完成。
2. 将 [2, 1, 3] 加入到 ans 中。
• ans = [[1, 2, 3], [1, 3, 2], [2, 1, 3]]
回溯:恢复状态
• 交换回去,恢复原数组 [2, 1, 3]。
• 返回到 n = 2,继续处理 i = 2。
2. 第 2 次交换:swap(nums[1], nums[2]),数组变为 [2, 3, 1]。
• 递归调用 dfs(nums, 2),进入处理第三个位置。
第 3 层递归:n = 2 (处理第三个位置)
• 当前节点的起始值是 nums = [2, 3, 1],n = 2,遍历 i = 2 到 i = 2(只剩下一个位置)。
1. 第 1 次交换:swap(nums[2], nums[2]),数组未变,仍为 [2, 3, 1]。
• 递归调用 dfs(nums, 3),这时 n == nums.size(),说明当前排列已经完成。
2. 将 [2, 3, 1] 加入到 ans 中。
• ans = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]
回溯:恢复状态
• 交换回去,恢复原数组 [2, 3, 1]。
• 返回到 n = 1,恢复原数组 [2, 1, 3]。
• 返回到 n = 0,恢复原数组 [1, 2, 3]。
第 3 次交换:n = 0 (处理第一个位置)
4. 第 3 次交换:swap(nums[0], nums[2]),数组变为 [3, 2, 1]。
• 递归调用 dfs(nums, 1),进入处理第二个位置。
第 2 层递归:n = 1 (处理第二个位置)
• 当前节点的起始值是 nums = [3, 2, 1],n = 1,遍历 i = 1 到 i = 2。
1. 第 1 次交换:swap(nums[1], nums[1]),数组未变,仍为 [3, 2, 1]。
• 递归调用 dfs(nums, 2),进入处理第三个位置。
第 3 层递归:n = 2 (处理第三个位置)
• 当前节点的起始值是 nums = [3, 2, 1],n = 2,遍历 i = 2 到 i = 2(只剩下一个位置)。
1. 第 1 次交换:swap(nums[2], nums[2]),数组未变,仍为 [3, 2, 1]。
• 递归调用 dfs(nums, 3),这时 n == nums.size(),说明当前排列已经完成。
2. 将 [3, 2, 1] 加入到 ans 中。
• ans = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1]]
回溯:恢复状态
• 交换回去,恢复原数组 [3, 2, 1]。
• 返回到 n = 2,恢复原数组 [3, 2, 1]。
• 返回到 n = 1,恢复原数组 [3, 2, 1]。
• 返回到 n = 0,恢复原数组 [1, 2, 3]。
最终结果
最终生成的排列 ans 中包含了所有可能的排列:
ans = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
总结
1. DFS 遍历:通过递归逐个处理每个位置,生成所有可能的字符组合。
2. 回溯:通过交换和恢复数组状态,确保生成所有排列。
3. 最终生成了所有的排列,并存储在 ans 中。
这样,我们使用回溯和 DFS 的方法成功计算出了所有的排列,并保存在 ans 数组中。
相关文章:
LeetCodehot 力扣热题100 全排列
这段代码的目的是计算给定整数数组的所有全排列(permutations),并返回一个包含所有排列的二维数组。 思路解析 在这段代码中,采用了 深度优先搜索(DFS) 和 回溯 的方法来生成所有的排列。 关键步骤…...
SQL笔记#数据更新
一、数据的插入(INSERT语句的使用方法) 1、什么是INSERT 首先通过CREATE TABLE语句创建表,但创建的表中没有数据;再通过INSERT语句向表中插入数据。 --创建表ProductIns CREATE TABLE ProductIns (product_id CHAR(4) NOT NULL,product_name VARCHAR(1…...
GCC 和 G++的基本使用
GCC 和 G 命令 GCC 和 G 命令GCC(GNU C 编译器)基本用法常用选项示例 G(GNU C 编译器)基本用法常用选项示例 GCC 与 G 的区别选择使用 GCC 还是 G C编译流程1. 预处理(Preprocessing)2. 编译(Co…...
Maven中一些基础知识点
早些时候只知道创建或者开发springboot项目时候,有一个叫pom.xml的文件可以用来管理项目所需的依赖/第三方工具。 索性稍微深入了解了一下,然后把自己认为重要的记录下来。 首先我们要引入新的依赖自然是在dependencies下写dependency,这个…...
论文阅读笔记:Deep Face Recognition: A Survey
论文阅读笔记:Deep Face Recognition: A Survey 1 介绍2 总览2.1 人脸识别组件2.1.1 人脸处理2.1.2 深度特征提取2.1.3 基于深度特征的人脸对比 3 网络结构和损失函数3.1 判别损失函数的演化3.1.1 基于欧式距离的损失3.1.2 基于角度/余弦边距的损失3.1.3 Softmax损失…...
JVM生产环境问题定位与解决实战(三):揭秘Java飞行记录器(JFR)的强大功能
提到飞行记录器,或许你的脑海中并未立刻浮现出清晰的画面,但一说起“黑匣子”,想必大多数人都能恍然大悟,知晓其重要性及用途。在航空领域,黑匣子作为不可或缺的设备,默默记录着飞行过程中的每一项关键数据…...
爬虫框架与库
爬虫框架与库是用于网络数据抓取的核心工具,帮助开发者高效地从网页中提取结构化数据。 Requests:用于发送HTTP请求。 BeautifulSoup:用于解析HTML和XML。 Scrapy:强大的爬虫框架,适合大规模爬取。 Selenium&#…...
PyTorch常用函数总结(持续更新)
本文主要记录自己在用 PyTorch复现经典模型 过程中遇到的一些函数及用法,以期对 常见PyTorch函数 更加熟练~ 官方Docs:PyTorch documentation — PyTorch 2.6 documentation 目录 数据层面 torch.sign(tensor) torch.tensor(np.eye(3)[y]) torch.on…...
代码异常(js中push)NO.4
1. 环境 Vue3,Element Plsu 2. 示例代码 const { updateBy, updateTime, ...curObj } form.valuecurObj.id props.tableData.length 1var newTableData props.tableData.push(curObj)updateTableData(newTableData)3. 情景描述 newTableData变成了整数&#…...
Anaconda 2025 最新版安装与Python环境配置指南(附官方下载链接)
一、软件定位与核心功能 Anaconda 2025 是Python/R数据科学集成开发平台,预装1500科学计算库,新增AI模型可视化调试、多环境GPU加速等特性。相较于传统Python安装,其优势包括: 环境隔离:通过conda工具实现多版本Pyth…...
Vue 中动态实现进度条
在 Vue 中动态实现进度条,基本上有两种常见的方法:直接通过 Vue 数据绑定控制样式,或者利用外部库来实现更复杂的功能。我们会深入探讨这两种方式,并且详细说明每种方法的实现步骤、优缺点以及使用场景。 1. 使用 Vue 数据绑定来…...
CSS滚动条原理与自定义样式指南,CSS滚动条样式失效,滚动条样式无效,-webkit-scrollbar无效,overflow不显示滚动条
滚动内容形成的必要条件 CSS Overflow属性解析 MDN官方文档-Overflow属性 菜鸟教程-Overflow属性 overflow 属性控制内容溢出元素框时在对应的元素区间内是否添加滚动条。 值描述visible默认值。内容不会被修剪,会呈现在元素框之外。hidden内容会被修剪…...
Three.js 入门(辅助、位移、父子关系、缩放旋转、响应式布局)
本篇主要学习内容 : 三维坐标系与辅助坐标系物体位移与父子元素物体的缩放与物体的旋转设置响应式画布与全屏控制 点赞 关注 收藏 学会了 本文使用 Three.js 的版本:171 基于 Vue3vite开发调试 1.三维坐标系与辅助坐标系 1.1) 导入three和轨道控制器 // 导入…...
python算法-用递归打印数字3的幂--Day017
文章目录 前言采用创新方式,精选趣味、实用性强的例子,从不同难度、不同算法、不同类型和不同数据结构进行总结,全面提升算法能力。例1.用递归打印数字例2.相对排名 总结 前言 采用创新方式,精选趣味、实用性强的例子,…...
Selenium 与 Coze 集成
涵盖两者的基本概念、集成步骤、代码示例以及相关注意事项。 基本概念 Selenium:是一个用于自动化浏览器操作的工具集,支持多种浏览器(如 Chrome、Firefox 等),能够模拟用户在浏览器中的各种操作,如点击、输入文本、选择下拉框等,常用于 Web 应用的自动化测试。Coze:它…...
AWS CLI将读取器实例添加到Amazon Aurora集群
Amazon Aurora是AWS提供的一种兼容MySQL和PostgreSQL的关系数据库服务。Aurora集群由一个写入器实例和多个读取器实例组成,可以提供高可用性、高性能和可扩展性。在本文中,我们将介绍如何使用AWS命令行界面(CLI)将读取器实例添加到现有的Aurora集群中。 © ivwdcwso (ID: u…...
NTS库学习,找bug中......
基础知识 Coordinate: 表示一个二维坐标点,包括 X 和 Y 坐标值。 CoordinateSequence: 由一系列 Coordinate 对象组成的序列,可以表示线、多边形等几何对象的顶点。 CoordinateFilter: 用于对几何对象的坐标进行过滤或修改的接口。 Geometry: 表示一个几…...
五十天精通硬件设计第40天-硬件测试流程
目录 一、硬件测试流程概述 二、详细测试流程 1. 需求分析与测试计划 2. 测试环境搭建 3. 测试执行 3.1 基本功能测试 3.2 性能测试 3.3 环境与可靠性测试 3.4 安全与合规性测试 4. 问题分析与调试 5. 回归测试与报告输出 三、关键注意事项 四、常见问题与解决 五…...
R语言安装教程(附安装包)R语言4.3.2版本安装教程
文章目录 前言一、安装包下载二、R-4.3.2安装步骤三、rtools43安装步骤四、RStudio安装步骤 前言 本教程将详细、全面地为你介绍在 Windows 系统下安装 R 语言 4.3.2 的具体步骤。无论你是初涉数据领域的新手,还是希望更新知识体系的专业人士,只要按照本…...
数据库 安装initializing database不通过
出现一下情况时: 处理方法: 将自己的电脑名称 中文改成英文 即可通过...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
微服务通信安全:深入解析mTLS的原理与实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言:微服务时代的通信安全挑战 随着云原生和微服务架构的普及,服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...
Pydantic + Function Calling的结合
1、Pydantic Pydantic 是一个 Python 库,用于数据验证和设置管理,通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发(如 FastAPI)、配置管理和数据解析,核心功能包括: 数据验证:通过…...
