leetcode第46题

简介: 这是自己开始想到的一个方法,考虑的思路是,先考虑小问题怎么解决,然后再利用小问题去解决大问题。没错,就是递归的思路。比如说,如果只有 1 个数字 [ 1 ],那么很简单,直接返回 [ [ 1 ] ] 就 OK 了。如果加了 1 个数字 2, [ 1 2 ] 该怎么办呢?我们只需要在上边的情况里,在 1 的空隙,也就是左边右边插入 2 就够了。变成 [ [ 2 1 ], [ 1 2 ] ]。

image.png

描述的很简单,就是给定几个数,然后输出他们所有排列的可能。

解法一 插入

这是自己开始想到的一个方法,考虑的思路是,先考虑小问题怎么解决,然后再利用小问题去解决大问题。没错,就是递归的思路。比如说,

如果只有 1 个数字 [ 1 ],那么很简单,直接返回 [ [ 1 ] ] 就 OK 了。

如果加了 1 个数字 2, [ 1 2 ] 该怎么办呢?我们只需要在上边的情况里,在 1 的空隙,也就是左边右边插入 2 就够了。变成 [ [ 2 1 ], [ 1 2 ] ]。

如果再加 1 个数字 3,[ 1 2 3 ] 该怎么办呢?同样的,我们只需要在上边的所有情况里的空隙里插入数字 3 就行啦。例如 [ 2 1 ] 在左边,中间,右边插入 3 ,变成 3 2 1,2 3 1,2 1 3。同理,1 2 在左边,中间,右边插入 3,变成 3 1 2,1 3 2,1 2 3,所以最后的结果就是 [ [ 3 2 1],[ 2 3 1],[ 2 1 3 ], [ 3 1 2 ],[ 1 3 2 ],[ 1 2 3 ] ]。

如果再加数字也是同样的道理,只需要在之前的情况里,数字的空隙插入新的数字就够了。

思路有了,直接看代码吧。

publicList<List<Integer>>permute(int[] nums) {
returnpermute_end(nums,nums.length-1);
}
// end 表示当前新增的数字的位置privateList<List<Integer>>permute_end(int[] nums, intend) {
// 只有一个数字的时候if(end==0){
List<List<Integer>>all=newArrayList<>();
List<Integer>temp=newArrayList<>();
temp.add(nums[0]);
all.add(temp);
returnall;
    }
//得到上次所有的结果List<List<Integer>>all_end=permute_end(nums,end-1);
intcurrent_size=all_end.size();
//遍历每一种情况for (intj=0; j<current_size; j++) { 
//在数字的缝隙插入新的数字for (intk=0; k<=end; k++) {
List<Integer>temp=newArrayList<>(all_end.get(j));
temp.add(k, nums[end]);
//添加到结果中all_end.add(temp);
        };
    }
//由于 all_end 此时既保存了之前的结果,和添加完的结果,所以把之前的结果要删除for (intj=0; j<current_size; j++) {
all_end.remove(0);
    }
returnall_end;
}

既然有递归的过程,我们也可以直接改成迭代的,可以把递归开始不停压栈的过程省略了。

publicList<List<Integer>>permute(int[] nums) {
List<List<Integer>>all=newArrayList<>();
all.add(newArrayList<>());
//在上边的基础上只加上最外层的 for 循环就够了,代表每次新添加的数字for (inti=0; i<nums.length; i++) {
intcurrent_size=all.size();
for (intj=0; j<current_size; j++) {
for (intk=0; k<=i; k++) {
List<Integer>temp=newArrayList<>(all.get(j));
temp.add(k, nums[i]);
all.add(temp);
            }
        }
for (intj=0; j<current_size; j++) {
all.remove(0);
        }
    }
returnall;
}

时间复杂度,如果只分析代码的话挺复杂的。如果从最后的结果来说,应该是 n! 个结果,所以时间复杂度应该是 O(n!)。

空间复杂度:O(1)

这道题很经典了,用动态规划,回溯,递归各实现了一遍,当然解法一强行递归了一下,和解法三相比真是相形见绌,解法三才是原汁原味的递归,简洁优雅。


目录
打赏
0
0
0
0
10
分享
相关文章
LeetCode第66题加一
LeetCode第66题"加一"的解题方法,通过遍历数组从后向前处理每一位的加法,并考虑进位情况,最终实现给定数字加一的功能。
LeetCode第66题加一
|
9月前
|
leetcode:389. 找不同
leetcode:389. 找不同
40 0
leetcode 827 最大人工岛
leetcode 827 最大人工岛
69 0
leetcode 827 最大人工岛
LeetCode 354. Russian Doll Envelopes
给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。
88 0
LeetCode 354. Russian Doll Envelopes
leetcode第51题
较经典的回溯问题了,我们需要做的就是先在第一行放一个皇后,然后进入回溯,放下一行皇后的位置,一直走下去,如果已经放的皇后的数目等于 n 了,就加到最后的结果中。然后再回到上一行,变化皇后的位置,然后去找其他的解。 期间如果遇到当前行所有的位置都不能放皇后了,就再回到上一行,然后变化皇后的位置。再返回到下一行。 说起来可能还费力些,直接看代码吧。
leetcode第51题
leetcode第49题
时间复杂度:两层 for 循环,再加上比较字符串,如果字符串最长为 K,总的时间复杂度就是 O(n²K)。 空间复杂度:O(NK),用来存储结果。 解法一算是比较通用的解法,不管字符串里边是大写字母,小写字母,数字,都可以用这个算法解决。这道题的话,题目告诉我们字符串中只有小写字母,针对这个限制,我们可以再用一些针对性强的算法。 下边的算法本质是,我们只要把一类的字符串用某一种方法唯一的映射到同一个位置就可以。
200 0
leetcode第49题
leetcode第56题
常规的思想,将大问题化解成小问题去解决。 假设给了一个大小为 n 的列表,然后我们假设 n - 1 个元素的列表已经完成了全部合并,我们现在要解决的就是剩下的 1 个,怎么加到已经合并完的 n -1 个元素中。 这样的话分下边几种情况, 我们把每个范围叫做一个节点,节点包括左端点和右端点。 1. 如下图,新加入的节点左端点和右端点,分别在两个节点之间。这样,我们只要删除
121 0
leetcode第56题
leetcode第47题
基本上都是在上道题的基础上改出来了,一些技巧也是经常遇到,比如先排序,然后判断和前一个是否重复。利用 Hash 去重的功能。利用原来的存储空间隐藏掉数据,然后再想办法还原。
100 0
leetcode第47题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等