Leetcode刷题详解——全排列
1. 题目链接:46. 全排列
2. 题目描述:
给定一个不含重复数字的数组
nums
,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。示例 1:
输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:
输入:nums = [0,1] 输出:[[0,1],[1,0]]
示例 3:
输入:nums = [1] 输出:[[1]]
提示:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums
中的所有整数 互不相同
3.解法(递归):
3.1 算法思路:
典型的回溯题目,我们需要在每一个位置上考虑所有的可能情况并且不能出现重复。通过深度优先搜索的方式,不断地枚举每个数在当前位置的可能性,并且回溯到上一个状态,直到枚举完所有的可能性,得到正确的结果
每个数是否可能出现在当前位置,只需要判断这个数在之前是否出现即可。
3.2 递归流程:
- 首先定义一个二维数
ret
用来存放所有可能的排列,一个一维数组path
用来存放正在构建的排列路径,一个一维数组用check
来标记每个元素是否已经被使用过,然后从第一个位置开始进行递归 - 在每个递归的状态中,我们维护一个步数
path
,表示当前已经处理了几个数字 - 递归结束条件:当
path
等于nums
数组的长度时,说明我们已经处理完了所有数字,将当前数组存入结果中 - 在每个递归状态中,枚举所有下标
i
,若这个下标未被标记,则使用nums
数组中当前下标的元素:- 将
check[i]
标记为true
- 数组中第
path
个元素被nums[i]
覆盖 - 对第
path+1
个位置进行递归 - 将
check[i]
重新赋值为flase
,表示回溯
- 将
- 最后,返回
ret
特别地,我们可以不使用标记数组,直接遍历path
之后的元素(未被使用),然后将其与需要递归的位置进行交换即可
3.3 C++算法代码:
class Solution {vector<vector<int>> ret; // 存储所有可能的排列结果vector<int> path; // 当前正在构建的排列路径bool check[7]; // 标记数组,用于记录每个元素是否已经被使用过public:vector<vector<int>> permute(vector<int>& nums) {dfs(nums); // 调用深度优先搜索函数进行全排列return ret; // 返回所有可能的排列结果}void dfs(vector<int>& nums) {if (nums.size() == path.size()) { // 如果当前路径的长度等于输入数组的长度,说明已经找到了一个排列ret.push_back(path); // 将当前路径添加到结果中return; // 结束当前递归分支}for (int i = 0; i < nums.size(); i++) {if (!check[i]) { // 如果当前元素没有被使用过path.push_back(nums[i]); // 将当前元素添加到当前路径中check[i] = true; // 标记当前元素已经被使用过dfs(nums); // 继续递归搜索下一个元素// 回溯操作path.pop_back(); // 移除当前路径中的最后一个元素check[i] = false; // 标记当前元素未被使用过}}}
};
相关文章:

Leetcode刷题详解——全排列
1. 题目链接:46. 全排列 2. 题目描述: 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1: 输入:nums [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],…...
JSONP 跨域访问(1), 简介, 原理, 实验, 缺点
JSONP 跨域访问(1), 简介, 原理, 实验, 缺点 一, JSONP 简介 JSONP(JSON with Padding)是一种非官方跨域数据交互协议。它允许web页面从不同的域名下加载数据。 由于同源策略,web页面通过XMLHttpRequest调用通常只允许访问与其自身相同域名…...

velero备份k8s集群
流程图 velero备份原理 本地 Velero 客户端发送备份指令。Kubernetes 集群内就会创建一个 Backup 对象。BackupController 监测 Backup 对象并开始备份过程。BackupController 会向 API Server 查询相关数据。BackupController 将查询到的数据备份到远端的对象存储。 velero的…...

描述低轨星座的特点和通信挑战,以及它们在5G和B5G中的作用。
文章目录 2章4 章5章(没看)6章(没看) 2章 将卫星星座中每个物理链路中可实现的数据速率、传播延迟和多普勒频移与3GPP技术报告中的参数进行分析和比较[3]。 相关配置 面向连接的网络,预先简历链路 卫星和地面终端有…...
Spring Boot实践 --windows环境下 K8s 部署 Docker
第一步:搭建项目并制作合适的jar包 这里我们准备好前面项目 用户管理系统 项目里的jar包。测试功能,定时任务会每过10s打印一次日志: E:\test>java -jar demospringboot-0.0.1-SNAPSHOT.jar2023-11-01 20:24:21.059 INFO 11848 --- [ …...

Linux 将Qt程序打包为AppImage包
前言 在 Linux 环境下,开发完 Qt 程序后,也需要制作为一个安装包或者可执行文件进行分发。这里介绍使用 linuxdeployqt 将 Qt 程序打包为 .AppImage 应用程序(类似于 Windows 的绿色免安装软件) 环境配置 配置 Qt 环境变量 这…...

修复国产电脑麒麟系统开机出现initramfs 问题
目录预览 一、问题描述二、原因分析三、解决方案四、知识点呀initramfsBusyBox 五、参考链接 一、问题描述 国产麒麟系统出现 initramfs 模式 二、原因分析 一般在拷贝卡顿过程【强制关机】或者电【脑异常断电】的情况下概率性导致系统分区损坏,重启后大概率就会进…...
机器人控制算法—如何使用C++读取pgm格式的栅格地图并转化为ROS地图格式的data?
1.Introduction 近期正在做全局规划局部动态规划的项目,目前遇到的问题是,我们如何利用C处理pgm地图文件。即将地图信息要与像素点结合起来。所以我们需要知道地图读取和处理的底层原理,这样更好地在非ROS平台下移植。 2.Main 如下几条信息…...

牛客项目(五)-使用kafka实现发送系统通知
kafka入门以及与spring整合 Message.java import java.util.Date;public class Message {private int id;private int fromId;private int toId;private String conversationId;private String content;private int status;private Date createTime;public int getId() {retur…...
计算机网络——第一章时延部分深入学习、相关习题及详细解析
目录 时延相关 习题1 习题1-改 习题2 时延相关 之前我们学习过,时延由发送时延、传播时延和处理时延三部分构成。 发送时延的计算公式为“分组长度除以发送速率”, 发送速率应该从网卡速率、信道带宽、以及对端的接口速率中取最小。 传播时延的计…...

CSS3媒体查询与页面自适应
2017年9月,W3C发布媒体查询(Media Query Level 4)候选推荐标准规范,它扩展了已经发布的媒体查询的功能。该规范用于CSS的media规则,可以为文档设定特定条件的样式,也可以用于HTML、JavaScript等语言。 1、媒体查询基础 媒体查询…...

UG\NX二次开发 超长的对象属性值,怎么设置
文章作者:里海 来源网站:里海NX二次开发3000例专栏 感谢粉丝订阅 感谢 Dr. Lin 订阅本专栏,非常感谢。 简介 使用UF_ATTR_assign设置对象属性,如果属性值超过UF_ATTR_MAX_STRING_LEN则会报错。 #define UF_ATTR_MAX_STRING_LEN 132 怎么办呢?下面这种方法可以解决: 效果 …...

流媒体服务实现H5实时预览视频
目录 背景方案业务实践细节注意 待办 背景 客户aws服务磁盘存储告急,最高可扩容16T。排查如下:主要是视频文件存在大量复制使用的情况。例如发布节目时复制、预览时复制,这样上传一份视频后最大会有四份拷贝(预览、普通发布、互动…...

C++适配器
文章目录 引言栈和队列 priority_queue仿函数迭代器区间 引言 栈的特性是先进后出,队列的特性是先进先出,然而双向队列同时具有栈和队列的特性,所以我们可以通过双向队列来适配出栈和队列。 先看库里面 栈和队列 stack和queue模板参数里面都…...

基于openresty waf二次开发多次匹配到的ip再做拉黑
我们想在openresty waf的基础上做二次开发,比如再精确一些。比如我们先匹配到了select的url我们先打分10分,匹配到cc 1000/s我们再给这个ip打10分…直到100分我们就拉黑这个ip。 [openresty waf][1] #cat reids_w.lua require lib local redis require…...

新一代构建工具Vite-xyphf
一、什么vite? vite:是一款思维比较前卫而且先进的构建工具,他解决了一些webpack解决不了的问题——在开发环境下可以实现按需编译,加快了开发速度。而在生产环境下,它使用Rollup进行打包,提供更好的tree-shaking、代码压缩和性能优化&…...
Flink源码解析三之执行计划⽣成
JobManager Leader 选举 首先flink会依据配置获取RecoveryMode,RecoveryMode一共两两种:STANDALONE和ZOOKEEPER。 如果用户配置的是STANDALONE,会直接去配置中获取JobManager的地址如果用户配置的是ZOOKEEPER,flink会首先尝试连接zookeeper,利用zookeeper的leadder选举服务发现…...
Flutter 常见错误记录总结
1、当 flutter pub get 指令报如下错误时: pub get failed command: "/Users/***/developer/flutter/bin/cache/dart-sdk/bin/dart __deprecated_pub --color --directory . get --example" pub env: { "FLUTTER_ROOT": "/Users/***/dev…...

[ASP]校无忧在线报名系统 v2.1
校无忧在线报名系统为了满足各地不同的报名人员的需求,为提供更为高效、方便、快捷的报名条件,同时也为减轻管理人员的工作难度;更为协调报名人员与管理人员的关系,快速提高了报名人员与管理人员的工作效率应运而生。系统适用于政…...

【Hydro】部分基流分割方法及程序代码说明
目录 说明一、数字滤波法单参数数字滤波Lyne-Hollick滤波法Chapman滤波法Chapman-Maxwell滤波法Boughton-Chapman滤波法 双参数滤波法Eckhardt滤波法 二、其他基流分割方法基流指数(BFI)法时间步长(HYSEP)法PART法加里宁-阿里巴扬…...

【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...

页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...

如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...

AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...

视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...