算法题解记录29+++全排列(百日筑基)
一、题目描述
题目难度:中等
给定一个不含重复数字的数组 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 中的所有整数 互不相同
二、解题准备
第一,题意
不解释
第二,基本操作
涉及到数组的遍历,List的增加,可能还有List的删除。
第三,基础原理
对于回溯算法,从大的方面讲,题解一般涉及递归(迭代解法过于复杂)。
从小的方面讲,可能会关系到将题目、解题过程转化为解空间树。
这棵解空间树,一般都是满多叉树(可能会用剪枝算法,降低运行时间)
一般来说,这棵解空间树,有这样的特点:
它的叶子节点是真正的题解。
它的其它节点,可以理解为解题过程。
因此,学会遍历多叉树,是解题的基础算法,链接如下:
多叉树遍历算法
三、解题思路
针对该题,我们先手动地解题。
对于数组【a,b,c】
它的排列有以下可能:
第一,如果先选择a,
那么,余下【b,c】进行选择。
紧接着1,如果选择b,余下c进行选择
有答案1为【a,b,c】
紧接着1,如果选择c,余下b选择
有答案2为【a,c,b】
第二,如果先选择b,
那么,余下【a,c】进行选择。
紧接着2,如果选择a,余下c,
有答案3为【b,a,c】
其它同理
我们可以发现,这颗多叉树,从空节点开始,每一层都会减少一个节点,如下图:
问题1:这不是满多叉树
想必你也发现了,随着层次减少,上一层总比下一层多出一个节点。
这是因为,在全排列中,如果某个位置使用了a,那么,其它的位置就不能使用a。
根据全排列的性质,我们可以得到这么个规律(假设length是输入数组的长度):
第一层:有length个节点【忽略,根节点】
第二层:有length-1个节点
……
第length层:有1个节点。此时,这个节点是叶子节点。【也就是我们需要的答案】
问题2:这棵多叉树难以遍历
这棵多叉树虽然结构鲜明,但明显是个刺头,难以下手。
假如,我们使用一个boolean数组,来标记哪个节点被访问,然后根据访问情况,进行遍历判断。
也许可行,不过我没写出来,主要问题出现在:
// 随机拿一个未访问的节点
// 使boolean数组为true
访问。
// 设置boolean数组为false
这几个步骤中,有2大问题:
第一,随机访问节点,很可能会访问到上一次的节点,这会造成答案重复。
第二,我们不能确定,究竟要访问多少次。【如果用nums的长度为标准,我们会发现,下一层节点,又只有上一层-1个。】
四、解题难点分析
难点如上所示。(我的观点)
难点定义:在数据处理的过程中,数据结构在不断变化。
最开始,有length个节点。
第二层,剩下length-1个。
……
到最后一层,只有1个了。
我们没法用统一的结构,处理这个问题。
A1思考:递归函数的解决结构
我们学习过二叉树的DFS深度优先遍历,以及斐波那契的递归函数。
其实可以发现,它有递归调用递归的过程。
// 斐波那契
return feibo(n-1) + feibo(n-2);
然而,这两个方案处理的数据结构,是一致的。
虽然斐波那契每次往前回调2次,但是,至始至终,处理的数据量都是2。
二叉树同理,每次处理的都是左子、右子两个节点。
在本题的多叉树中,每次处理的节点在依次减少。
B2解决方案:双层递归函数
我们定义函数A,它提供一个方案:
A处理数据量为len的数组,依次从数组中拿出一个数,然后将此数移出数组,递归调用A函数,处理len-1的数组。
也就是说,A处理的对象是固定的:
只处理数据量为len的数组,其它的情况,交给它的子递归函数。
并且,A处理的结构,每次会按要求减少,直到符合叶子节点,然后返回答案。
代码在下方,在此仅解释。
C3难点:确定参数
A的参数比较难以确定,这属于是回溯法的特点之一。
我在此介绍一种思路:
3个关键词:结果集、答案集、输入集
结果集:求解过程中的临时变量,到达叶子节点时,就是一个答案。
答案集:存储所有答案的全局或局部变量。
输入集:变化的数据结构。
另外的参数,需要看题目情况,动态地变化。
D4难点:变化的输入集
由上可知,输入集在不断变化。
如果现在输入集为【a,b,c】
在选择后,剩下【b,c】
如果采用数组的结构,每次新生成一个数组,然后把【b,c】存储到数组,接着再递归调用。
可以发现,这会占用比较大的内存空间,而且数组复制的时间复杂度也不小。
因此,我们可以采用List链表,每次添加一个数,或者删除一个数,这样使用的内存空间会大大减少。
五、代码
class Solution {public List<List<Integer>> permute(int[] nums) {// 答案集List<List<Integer>> res = new ArrayList<List<Integer>>();// 输入集List<Integer> damn = new ArrayList<>();// 将数组转化为List,节省内存for(int i:nums){damn.add(i);}dfs_n(new ArrayList<>(), res, damn);return res;}// data是结果集,临时答案private void dfs_n(List<Integer> data, List<List<Integer>> res, List<Integer> damn){// size为0,就是叶子节点的下一层,该返回了if(damn.size() == 0){res.add(new ArrayList<>(data));return;}// 每次访问输入集的长度for(int i=0; i<damn.size(); i++){// tem仍要用于回溯,所以用个tem存储int tem = damn.get(i);// 结果集添加,输入集移除data.add(tem);damn.remove(i);// 调用子递归函数dfs_n(data, res, damn);// 结果集移除,输入集恢复data.remove(data.size()-1);damn.add(i, tem);}}
}
六、结语
以上内容即我想分享的关于力扣热题29的一些知识。
我是蚊子码农,如有补充,欢迎在评论区留言。个人也是初学者,知识体系可能没有那么完善,希望各位多多指正,谢谢大家。
相关文章:
算法题解记录29+++全排列(百日筑基)
一、题目描述 题目难度:中等 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1: 输入:nums [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示…...
苹果AI功能,AI训练数据缺乏,SD3推出,MJ6推出新特性
更多信息: https://agifun.love 智源社区 2024智源大会议程公开丨大模型前沿探索 2024年6月14日-15日,第6届北京智源大会将以线下与线上结合的形式召开,线下会场设在中关村国家自主创新示范区会议中心。2024智源大会再次以全球视野&#x…...
超越中心化:Web3如何塑造未来数字生态
随着技术的不断发展,人们对于网络和数字生态的期望也在不断提升。传统的中心化互联网模式虽然带来了便利,但也暴露出了诸多问题,比如数据滥用、信息泄露、权力集中等。在这样的背景下,Web3技术应运而生,旨在打破传统中…...
【ic-tool】timegen使用
一、前言 TimeGen是一个用于时序波形编辑的CAD工具,它允许数字设计工程师快速有效地绘制数字时序图。TimeGen时序图可以很容易地导出到其他窗口程序,如microsoftword,用于编写设计规范。可直接从官网下载TimeGEN软件:TimeGen Pro…...
1:25万基础电子地图(云南版)
我们在《50幅1:25万基础电子地图(四川版)》一文中,为你分享过四川的50幅基础电子地图。 现在我们再为你分享云南的1:25万基础电子地图,你可以在文末查看该数据的领取方法。 基础电子地图云南版 下载后可以看到该数据…...
springboot宠物领养系统-计算机毕业设计源码07863
摘 要 21世纪的今天,随着社会的不断发展与进步,人们对于信息科学化的认识,已由低层次向高层次发展,由原来的感性认识向理性认识提高,管理工作的重要性已逐渐被人们所认识,科学化的管理,使信息存…...
牛客热题:最长回文子串
📟作者主页:慢热的陕西人 🌴专栏链接:力扣刷题日记 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 文章目录 牛客热题:最长回文子串题目链接方法一&am…...
如何访问寄存器
标题 方式一:对地址进行宏定义方式二:用结构体封装寄存器 访问寄存器是CPU执行程序的基础,每种CPU架构都有其特定的寄存器集合和访问方式。 方式一:对地址进行宏定义 #define GPIOA_BASE ((unsigned int)0x48000000) #define GPI…...
苍穹外卖笔记-18-修改密码、bug记录
文章目录 1 修改密码1.1 需求分析和设计1.2 代码实现1.2.1 admin/EmployeeController1.2.2 EmployeeService1.2.3 EmployeeServiceImpl 1.3 功能测试 2 bug记录 1 修改密码 完结的时候发现还有一个接口未实现。这里补充 1.1 需求分析和设计 产品原型: 业务规则&am…...
java如何截取字符串
如果想在一个字符串中截取一段字符,形成新的字符,那么在java中途需要用到substring语句 substring的语法格式是 str.substring(beginindex,endindex) 其中str是字符串 beginindex是起始索引,endindex是结束索引 截取的字符串包含起始索引…...
虚拟淘宝-Virtual-Taobao论文解读(AAAI2019)
目录 1 论文简介 2 文章的主要贡献 3 文章技术的简要说明 4 技术的详细说明 4.1 GAN-SD:生成客户特征 4.2 MAIL:生成交互过程 4.3 ANC:动规范约束 5 实验设定及结果 6 结论 7 参考 1 论文简介 南京大学LAMDA团队的侍竞成、俞扬等…...
低代码组件扩展方案在复杂业务场景下的设计与实践
组件是爱速搭的前端页面可视化模块的核心能力之一,它将前端研发人员从无休止的页面样式微调和分辨率兼容工作中解放了出来。 目前,爱速搭通过内置的上百种功能组件(120),基本可以覆盖大部分中后台页面的可视化设计场景…...
震撼科技界的GPT-4o发布首日即遭“越狱破防”
前言 本文主要解读分析OpenAI最新推出的大型模型GPT-4o可能存在的越狱风险。 5 月14 日凌晨的科技圈再一次被OpenAI轰动,其发布的最新大模型GPT-4o,能力横跨语音、文本和视觉,这一成果无疑再次巩固了OpenAI在人工智能领域的领先地位。 然而…...
保护密码安全,探讨密码加盐及其在Go语言中的实现
介绍 在当今数字化时代,个人隐私和数据安全成为了人们关注的焦点之一。随着网络犯罪的不断增加,用户的密码安全性变得尤为重要。密码加盐作为一种常见的安全措施,被广泛应用于密码存储和认证系统中。本文将深入探讨密码加盐的概念、重要性以…...
Sqoop学习详细介绍!!
一、Sqoop介绍 Sqoop是一款开源的工具,主要用于在Hadoop(HDFS/Hive/HBase)与传统的数据库(mysql、postgresql...)间进行数据的传递,可以将一个关系型数据库(例如 : MySQL ,Oracle ,Postgres等)中的数据导进到Hadoop的H…...
【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 生成哈夫曼树(100分) - 三语言AC题解(Python/Java/Cpp)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 📎在线评测链接 生成哈夫曼树(100分) 🌍 评测功能需要订阅专栏后私信联系清…...
ctfshow web 单身杯
web签到 <?phperror_reporting(0); highlight_file(__FILE__);$file $_POST[file];if(isset($file)){if(strrev($file)$file){ //翻转函数include $file;}}要进行反转并且包含文件用data协议 自己写不好写可以用函数帮你翻转 <?php $adata:text/plain,<?eval(…...
天锐绿盾加密软件,它的适用范围是什么?
天锐绿盾数据防泄密软件的适用范围广泛,主要可以归纳为以下几点: 行业适用性: 适用于各个行业,包括但不限于制造业、设计行业、软件开发、金融服务等,特别是对数据安全性要求较高的行业。企业规模与类型: 适…...
mysql面试题 Day2
1 长文本如何存储? 可以使用Text存储 TINYTEXT(255长度) TEXT(65535) MEDIUMTEXT(int最大值16M) LONGTEXT(long最大值4G) 2 大段文本存储如何设计表结构? 分表存储 分表后多段存储 3 大段文本查找时如何建立索引࿱…...
Excel加密怎么设置?这5个方法不容错过!(2024总结)
Excel加密怎么设置?如何不让别人未经允许查看我的excel文件?如果您也有这些疑问,那么千万不要错过本篇文章了。今天小编将向大家分享excel加密的5个简单方法,保证任何人都可以轻松掌握!毫无疑问的是,为Exce…...
2024年下一个风口是什么?萤领优选 轻资产创业项目全国诚招合伙人
2024年,全球经济与科技发展的步伐不断加快,各行各业都在探寻新的增长点与风口。在这样的时代背景下,萤领优选作为一个轻资产创业项目,正以其独特的商业模式和前瞻的市场洞察力,吸引着众多创业者的目光。(领取ÿ…...
Redis 网络模型
一、用户空间和内核空间 1.1 linux 简介 服务器大多采用 Linux 系统,这里我们以 Linux 为例来讲解,下面有两个不同的 linux 发行版,分别位 ubuntu 和 centos,其实发行版就是在 Linux 系统上包了一层壳。 任何 Linux 发行版&#…...
【设计模式之组合模式 -- C++】
组合模式 – 树状结构,递归遍历 组合模式(Composite Pattern)是一种结构型设计模式,它可以让你将对象组合成树形结构,并且能像使用独立对象一样使用它们。这种模式定义了包含人和组的类,每个类都有可以在树形结构中显示的方法。这…...
C# 通过Win32API设置客户端系统时间
在日常工作中,有时可能会需要获取或修改客户端电脑的系统时间,比如软件设置了Licence有效期,预计2024-06-01 00:00:00到期,如果客户手动修改了客户端电脑时间,往前调整了一年,则软件就可以继续使用一年&…...
VirtualHere 允许通过网络远程使用 USB 设备,就像本地连接一样!
传统上,USB 设备需要直接插入计算机才能使用。有了 VirtualHere,就不再需要这样做,网络本身就变成了传输 USB 信号的电缆(也称为 USB over IP、USB/IP、USB over WiFi、USB over Ethernet、USB 设备服务器)。 此 USB …...
【Kubernetes】k8s 自动伸缩机制—— HPA 部署
一、在K8s中扩缩容分为两种: ●Node层面:对K8s物理节点扩容和缩容,根据业务规模实现物理节点自动扩缩容 ●Pod层面:我们一般会使用Deployment中的Replicas参数,设置多个副本集来保证服务的高可用,但是这是…...
MT1415 大小相同
题目 给定一个由N(<10)个正整数组成的数组A,生成一些最小元素和最大元素相同的子数组数(可以仅包含1个元素),统计这些子数组的数量并输出。 注:最大元素和最小元素相同就是数组中的元素全部为同一个值。如数组&am…...
使用python库moviepy完成视频剪辑
1.关于moviepy和原理 moviepy事github上面的一个开源项目,地址是:GitHub - Zulko/moviepy: Video editing with Python 官方文档地址: User Guide — MoviePy 1.0.2 documentation 中文版文档可参考: MoviePy中文手册 — mov…...
Java高手的30k之路|面试宝典|精通泛型
泛型 知识点 在Java高级开发中,掌握泛型(Generics)是非常重要的,它是Java语言中的一项重要特性,提供了编译时类型安全检查机制,使得代码更加灵活和可重用。以下是Java高级开发需要掌握的泛型知识点&#…...
清理Linux操作系统buff/cache缓存
清理Linux操作系统buff/cache缓存 清理页缓存 echo 1 > /proc/sys/vm/drop_caches 或者 sysctl -w vm.drop_caches1 清理目录项和inode缓存 echo 2 > /proc/sys/vm/drop_caches 或者 sysctl -w vm.drop_caches2 同时清理页缓存、目录项和inode缓存 echo 3 > /pr…...
做外汇的官方网站/站长网
任务是向url发送一个json字符串数据的HTTP post请求,url受HTTP基本身份验证的保护,我需要在头中提供一个授权:字段,emailAdd是基本身份验证的用户ID,生成密码通过TOTP,其中位数为10位,时间步长为…...
网站搭建和网页设计/app推广员怎么做
场景介绍 美国有一家做草地喷水头的公司,市场竞争异常激烈。他们想在产品上做一些突破,在做用户调研的时候发现,用户最大的问题是草地喷水头太费水,于是他们就想能不能让喷水头为用户节省水,比如下雨天就不用浇水了&am…...
商城类网站设计制作/搜索引擎优化技术有哪些
例如: JSON字符串:var str1 { "name": "cxh", "sex": "man" }; JSON对象:var obj { "name": "cxh", "sex": "man" }; 1、在js中把json字符串转json对象的方法不止一种࿰…...
安徽建设相关网站/互联网优化
解决办法:换上usb接口,舍弃esata, 重新上电,就能识别了 转载于:https://www.cnblogs.com/norsd/archive/2012/03/12/6359474.html...
优秀购物网站/百度搜索引擎优化详解
Hadoop2.7伪分布式搭建 软件版本: 系统:CentOS 7 64位 jdk:1.8.0_181 hadoop:hadoop 2.7.2 环境准备: 1.安装Java环境(省略) 2. 创建用户(work): root用户…...
419黄冈分类信息网/惠州seo排名收费
通过上一篇文章我们已经完成了nagios在Centos上的安装配置接下来进行监控windows主机nagios通过Nsclient检测windows工作原理nagios文件说明:nagios配置文件存放于/etc/nagios中,其中nagios.cfg 为主配置文件。objects 文件夹为各种类型的配置文件&#…...