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

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 递归流程:

  1. 首先定义一个二维数ret用来存放所有可能的排列,一个一维数组path用来存放正在构建的排列路径,一个一维数组用check来标记每个元素是否已经被使用过,然后从第一个位置开始进行递归
  2. 在每个递归的状态中,我们维护一个步数path,表示当前已经处理了几个数字
  3. 递归结束条件:当path等于nums数组的长度时,说明我们已经处理完了所有数字,将当前数组存入结果中
  4. 在每个递归状态中,枚举所有下标i,若这个下标未被标记,则使用nums数组中当前下标的元素:
    1. check[i]标记为 true
    2. 数组中第path个元素被nums[i]覆盖
    3. 对第path+1个位置进行递归
    4. check[i]重新赋值为flase,表示回溯
  5. 最后,返回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. 题目链接&#xff1a;46. 全排列 2. 题目描述&#xff1a; 给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],…...

JSONP 跨域访问(1), 简介, 原理, 实验, 缺点

JSONP 跨域访问(1), 简介, 原理, 实验, 缺点 一, JSONP 简介 JSONP&#xff08;JSON with Padding&#xff09;是一种非官方跨域数据交互协议。它允许web页面从不同的域名下加载数据。 由于同源策略&#xff0c;web页面通过XMLHttpRequest调用通常只允许访问与其自身相同域名…...

velero备份k8s集群

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

描述低轨星座的特点和通信挑战,以及它们在5G和B5G中的作用。

文章目录 2章4 章5章&#xff08;没看&#xff09;6章&#xff08;没看&#xff09; 2章 将卫星星座中每个物理链路中可实现的数据速率、传播延迟和多普勒频移与3GPP技术报告中的参数进行分析和比较[3]。 相关配置 面向连接的网络&#xff0c;预先简历链路 卫星和地面终端有…...

Spring Boot实践 --windows环境下 K8s 部署 Docker

第一步&#xff1a;搭建项目并制作合适的jar包 这里我们准备好前面项目 用户管理系统 项目里的jar包。测试功能&#xff0c;定时任务会每过10s打印一次日志&#xff1a; E:\test>java -jar demospringboot-0.0.1-SNAPSHOT.jar2023-11-01 20:24:21.059 INFO 11848 --- [ …...

Linux 将Qt程序打包为AppImage包

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

修复国产电脑麒麟系统开机出现initramfs 问题

目录预览 一、问题描述二、原因分析三、解决方案四、知识点呀initramfsBusyBox 五、参考链接 一、问题描述 国产麒麟系统出现 initramfs 模式 二、原因分析 一般在拷贝卡顿过程【强制关机】或者电【脑异常断电】的情况下概率性导致系统分区损坏&#xff0c;重启后大概率就会进…...

机器人控制算法—如何使用C++读取pgm格式的栅格地图并转化为ROS地图格式的data?

1.Introduction 近期正在做全局规划局部动态规划的项目&#xff0c;目前遇到的问题是&#xff0c;我们如何利用C处理pgm地图文件。即将地图信息要与像素点结合起来。所以我们需要知道地图读取和处理的底层原理&#xff0c;这样更好地在非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 时延相关 之前我们学习过&#xff0c;时延由发送时延、传播时延和处理时延三部分构成。 发送时延的计算公式为“分组长度除以发送速率”&#xff0c; 发送速率应该从网卡速率、信道带宽、以及对端的接口速率中取最小。 传播时延的计…...

CSS3媒体查询与页面自适应

2017年9月&#xff0c;W3C发布媒体查询(Media Query Level 4)候选推荐标准规范&#xff0c;它扩展了已经发布的媒体查询的功能。该规范用于CSS的media规则&#xff0c;可以为文档设定特定条件的样式&#xff0c;也可以用于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服务磁盘存储告急&#xff0c;最高可扩容16T。排查如下&#xff1a;主要是视频文件存在大量复制使用的情况。例如发布节目时复制、预览时复制&#xff0c;这样上传一份视频后最大会有四份拷贝&#xff08;预览、普通发布、互动…...

C++适配器

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

基于openresty waf二次开发多次匹配到的ip再做拉黑

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

新一代构建工具Vite-xyphf

一、什么vite? vite:是一款思维比较前卫而且先进的构建工具,他解决了一些webpack解决不了的问题——在开发环境下可以实现按需编译&#xff0c;加快了开发速度。而在生产环境下&#xff0c;它使用Rollup进行打包&#xff0c;提供更好的tree-shaking、代码压缩和性能优化&…...

Flink源码解析三之执行计划⽣成

JobManager Leader 选举 首先flink会依据配置获取RecoveryMode,RecoveryMode一共两两种:STANDALONE和ZOOKEEPER。 如果用户配置的是STANDALONE,会直接去配置中获取JobManager的地址如果用户配置的是ZOOKEEPER,flink会首先尝试连接zookeeper,利用zookeeper的leadder选举服务发现…...

Flutter 常见错误记录总结

1、当 flutter pub get 指令报如下错误时&#xff1a; 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

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

【Hydro】部分基流分割方法及程序代码说明

目录 说明一、数字滤波法单参数数字滤波Lyne-Hollick滤波法Chapman滤波法Chapman-Maxwell滤波法Boughton-Chapman滤波法 双参数滤波法Eckhardt滤波法 二、其他基流分割方法基流指数&#xff08;BFI&#xff09;法时间步长&#xff08;HYSEP&#xff09;法PART法加里宁-阿里巴扬…...

visual studio 2022更改主题为深色

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

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

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 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

莫兰迪高级灰总结计划简约商务通用PPT模版

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

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

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# 如果存在&#xff0…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

二维FDTD算法仿真

二维FDTD算法仿真&#xff0c;并带完全匹配层&#xff0c;输入波形为高斯波、平面波 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呢&#xff0c;接下来看几个例子&#xff1a; 下面这张为什么可以用const呢&#xff1f;因为复杂数据的引用地址没变&#xff0c;数组还是数组&#xff0c;只是添加了个元素&#xff0c;本质没变&#xff0c;所以可以用con…...