汽车是怎么做的视频网站,建站用wordpress好吗,中英双语网站,为什么做织梦网站时图片出不来一、题目描述
题目难度#xff1a;中等 给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1#xff1a;
输入#xff1a;nums [1,2,3] 输出#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示…一、题目描述
题目难度中等 给定一个不含重复数字的数组 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的删除。
第三基础原理
对于回溯算法从大的方面讲题解一般涉及递归迭代解法过于复杂。 从小的方面讲可能会关系到将题目、解题过程转化为解空间树。 这棵解空间树一般都是满多叉树可能会用剪枝算法降低运行时间 一般来说这棵解空间树有这样的特点 它的叶子节点是真正的题解。 它的其它节点可以理解为解题过程。 因此学会遍历多叉树是解题的基础算法链接如下 多叉树遍历算法
三、解题思路
针对该题我们先手动地解题。 对于数组【abc】 它的排列有以下可能
第一如果先选择a,
那么余下【bc】进行选择。
紧接着1如果选择b,余下c进行选择
有答案1为【abc】
紧接着1如果选择c余下b选择
有答案2为【acb】
第二如果先选择b
那么余下【ac】进行选择。
紧接着2如果选择a余下c
有答案3为【bac】 其它同理 我们可以发现这颗多叉树从空节点开始每一层都会减少一个节点如下图
问题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难点变化的输入集
由上可知输入集在不断变化。 如果现在输入集为【abc】 在选择后剩下【bc】 如果采用数组的结构每次新生成一个数组然后把【bc】存储到数组接着再递归调用。 可以发现这会占用比较大的内存空间而且数组复制的时间复杂度也不小。 因此我们可以采用List链表每次添加一个数或者删除一个数这样使用的内存空间会大大减少。
五、代码
class Solution {public ListListInteger permute(int[] nums) {// 答案集ListListInteger res new ArrayListListInteger();// 输入集ListInteger damn new ArrayList();// 将数组转化为List节省内存for(int i:nums){damn.add(i);}dfs_n(new ArrayList(), res, damn);return res;}// data是结果集临时答案private void dfs_n(ListInteger data, ListListInteger res, ListInteger damn){// size为0就是叶子节点的下一层该返回了if(damn.size() 0){res.add(new ArrayList(data));return;}// 每次访问输入集的长度for(int i0; idamn.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的一些知识。 我是蚊子码农如有补充欢迎在评论区留言。个人也是初学者知识体系可能没有那么完善希望各位多多指正谢谢大家。
