当前位置: 首页 > 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法加里宁-阿里巴扬…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

页面渲染流程与性能优化

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

如何将联系人从 iPhone 转移到 Android

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

AI,如何重构理解、匹配与决策?

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

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

视觉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模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...