排列"/>
LeetCode高频题46. 全排列
LeetCode高频题46. 全排列
提示:本题是系列LeetCode的150道高频题,你未来遇到的互联网大厂的笔试和面试考题,基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们,吃完饭就是设计考题,然后去考应聘人员,你要做的就是学基础树结构与算法,然后打通任督二脉,以应对波云诡谲的大厂笔试面试题!
你要是不扎实学习数据结构与算法,好好动手手撕代码,锻炼解题能力,你可能会在笔试面试过程中,连题目都看不懂!比如华为,字节啥的,足够让你读不懂题
文章目录
- LeetCode高频题46. 全排列
- @[TOC](文章目录)
- 题目
- 一、审题
- DFS枚举所有数字开头的情况,然后恢复现场,尝试别的数字做开头的情况
- 你也可以暴力试试:贼慢
- 总结
- @[TOC](文章目录)
题目
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
DFS呗,还要剪枝,恢复现场
一、审题
示例 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 中的所有整数 互不相同
来源:力扣(LeetCode)
链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
DFS枚举所有数字开头的情况,然后恢复现场,尝试别的数字做开头的情况
本题老油条了
(1)每个i位置的数字做一次开头,它只能跟j=i–N-1每个位置交换一次【包括i自己哦!!!】
(2)剩下的数,又当一个新的数组,递归干这件事(1)
(3)直到i越界,此时的arr数组就是一个答案,收集放入ans,返回上一级,恢复现场,上次你怎么交换的,这次给我换回来,方便我尝试别的情况
举例:
arr=a b c
dfs的函数f,来到i=0位置,它可以跟谁交换?j=i–N-1,也就是它可以跟0 1 2 都交换一次
(1)i=0跟j=0交换,等于没换,arr=abc不动
然后,继续递归,i来到i+1=1处,i=1可以跟谁交换?j=1,2交换,它跟j=1交换试试,等于没换arr=abc
继续递归,i来到i+1=2处,i=2可以跟谁交换?j=2交换,它跟j=2交换试试,等于没换arr=abc
继续递归,i来到i+1=3处,i=3越界,收集答案,ans加一个arr就是当前的第一个排列结果
ans=abc
然后,返回上一级,恢复现场,i=2可以跟谁交换?j=2交换,它跟j=2交换试试,arr=abc
i来到i+1=1处,i=1可以跟谁交换?j=1,2交换,它跟j=2交换试试,arr=acb
继续递归,i来到i+1=2处,i=2可以跟谁交换?j=2交换,它跟j=2交换试试,等于没换arr=acb
继续递归,i来到i+1=3处,i=3越界,收集答案,ans加一个arr就是当前的第2个排列结果
ans=abc,acb
然后,返回上一级,恢复现场,i=2可以跟谁交换?j=2交换,它跟j=2交换试试,arr=acb
i来到i+1=1处,i=1可以跟谁交换?j=1,2交换,上面都换过了!,arr=acb
然后,返回上一级,恢复现场,刚刚1 2交换,现在2 1交换,arr=abc
然后,返回上一级,恢复现场,刚刚0 0交换,现在0 0交换,arr=abc
ans=abc,acb
现在基本就回到了当初i=0那会的情况,dfs的函数f,来到i=0位置,它可以跟谁交换?j=i–N-1,也就是它可以跟0 1 2 都交换一次
(2)i=0跟j=1交换【上面是先跟0交换的,你看看区别哦】,arr=bac,已经不再是abc了哦
其实又把上面的(1)走一遍
来到i=1位置,i可以跟j=1,2交换一次
i先跟1交换,就是自己bac
来到i=2位置,i可以跟j=2交换一次,没变,就是自己bac
来到i=3位置,i越界,ans加此时的arr,bac
ans=abc,acb,bac
返回i=2恢复现场,返回i=1,恢复现场,arr=bac
来到i=1位置,i可以跟j=1,2交换一次
i跟2交换,arr=bca
来到i=2位置,i可以跟j=2交换一次,没变,就是自己bca
来到i=3位置,i越界,ans加此时的arr,bca
ans=abc,acb,bac,bca
返回i=2恢复现场,arr=bca,返回i=1,恢复现场,arr=bac
返回i=0,恢复现场,arr=abc
(3)i=0跟j=2交换【上面是先跟0,再跟1交换的,你看看区别哦,现在是i=0与j=2交换】,arr=cba,已经不再是abc了哦
其实又把上面的(1)走一遍
来到i=1位置,i可以跟j=1,2交换一次
i=1跟j=1交换,arr=cba,
来到i=2位置,i可以跟j=2交换一次,arr=cba
来到i=3位置,越界,收集答案cba
ans=abc,acb,bac,bca,cba
返回i=2位置,恢复现场,arr=cba
返回i=1位置,恢复现场,arr=cba
来到i=1位置,i可以跟j=1,2交换一次
i=1跟j=2交换,arr=cab
来到i=2位置,i可以跟j=2交换一次,arr=cab
来到i=3位置,越界,收集答案cab
ans=abc,acb,bac,bca,cba,cab
返回i=2,恢复现场,arr=cab
返回i=1,恢复现场,arr=cba
返回i=0,恢复现场,arr=abc
结束!
ans=abc,acb,bac,bca,cba,cab就是所有的排列组合
a=1,b=2,c=3,就是本题的最优解,我们不浪费交换,也不会多找结果,也不会缺少结果!
我们就干一件事!
来此来到i,让i和j=i–N-1交换一次,剩下的数字继续递归i+1位置,但是干的事情,又是这个递归
不断往下,基本就让所有的数字做了开头,然后还考虑别的数字依次做了开头的情况
就是排列组合,每个数字做一次开头,剩下的数字继续缩短长度,又玩一次每个数字做一次开头,这样枚举下去
直到i越界,收集此刻的arr
返回上一层,你上次怎么交换的,给我换回来,恢复现场,我方便在i-1层继续让i和别的j位置交换,让另外的j来做排头
这样才公平
刚刚开始看很难,但是手撕一次代码,你基本就熟悉了
手撕代码!
public void swap(int[] arr, int i, int j){int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}//复习:依次从arr的i位置决定谁做排头,然后去i+1继续做决定public void f(int[] arr, int i, List<List<Integer>> ans){//直到i越界,收集此刻的arrif (i == arr.length){//每次都要把arr转ListList<Integer> cur = new ArrayList<>();for(Integer x : arr) cur.add(x);//全部加入ans.add(cur);//作为一个排列组合结果,放入ans}else {//没有越界,决定让i跟谁换?//来此来到i,让i和j=i--N-1交换一次,剩下的数字继续递归i+1位置,但是干的事情,又是这个递归for (int j = i; j < arr.length; j++) {swap(arr, i, j);//不断往下,基本就让所有的数字做了开头,然后还考虑别的数字依次做了开头的情况//就是排列组合,每个数字做一次开头,剩下的数字继续缩短长度,// 又玩一次每个数字做一次开头,这样枚举下去f(arr, i + 1, ans);//返回上一层,你上次怎么交换的,给我换回来,恢复现场,// 我方便在i-1层继续让i和别的j位置交换,让另外的j来做排头swap(arr, j, i);}}}//主函数,就从i=0开始调用递归public List<List<Integer>> permuteReview(int[] nums) {List<List<Integer>> ans = new ArrayList<>();//从i=0开始决定谁做排头,收集一波答案f(nums, 0, ans);return ans;}
测试:
public static void test(){int[] arr = {1,2,3};Solution solution = new Solution();List<List<Integer>> res = solution.permute(arr);for(List<Integer> list : res){for(Integer i : list) System.out.print(i +" ");System.out.println();}System.out.println();res = solution.permuteReview(arr);for(List<Integer> list : res){for(Integer i : list) System.out.print(i +" ");System.out.println();}}public static void main(String[] args) {test();}
问题不大:
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2 1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
LeetCode测试:
你也可以暴力试试:贼慢
枚举arr中的每一位置i
把每个数i加到path中,然后把arr中的这个数i删除,从新递归收集剩下的情况
当剩下的arr为null了,说明path就是一种排列组合
(1)比如arr=1 2 3
先加1到path,path=1
然后将arr中的1抹掉,arr=2 3
再递归去(1)
arr=2 3
先加2到path,path=1,2
然后将arr中的2抹掉,arr=3
再递归去(1)
arr=3
先加3到path,path=1,2,3
然后将arr中的3抹掉,arr=null
收集ans=path=123
然后从新考虑
(1)arr=1 2 3
先加2到path,path=2
然后将arr中的1抹掉,arr=1 3
再递归去(1)
arr=1 3
先加1到path,path=21
然后将arr中的1抹掉,arr=3
再递归去(1)
arr=3
先加3到path,path=213
然后将arr中的3抹掉,arr=null
收集ans=path=123,213
然后从新考虑……
这样子暴力递归,也可以,但是非常耗费时间
你只需要搞懂上面的交换,恢复现场,让每个i做一次排头就行。
总结
提示:重要经验:
1)来此来到i,让i和j=i–N-1交换一次,剩下的数字继续递归i+1位置,但是干的事情,又是这个递归
不断往下,基本就让所有的数字做了开头,然后还考虑别的数字依次做了开头的情况
就是排列组合,每个数字做一次开头,剩下的数字继续缩短长度,又玩一次每个数字做一次开头,这样枚举下去
直到i越界,收集此刻的arr
返回上一层,你上次怎么交换的,给我换回来,恢复现场,我方便在i-1层继续让i和别的j位置交换,让另外的j来做排头
这样才公平
3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。
更多推荐
LeetCode高频题46. 全排列
发布评论