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法加里宁-阿里巴扬…...

visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...

莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...

FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
二维FDTD算法仿真
二维FDTD算法仿真,并带完全匹配层,输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...

Web APIS Day01
1.声明变量const优先 那为什么一开始前面就不能用const呢,接下来看几个例子: 下面这张为什么可以用const呢?因为复杂数据的引用地址没变,数组还是数组,只是添加了个元素,本质没变,所以可以用con…...