莺时

东边日出西边雨,道是无晴却有晴

Open Source, Open Mind,
Open Sight, Open Future!
  menu
18 文章
3692 浏览
2 当前访客
ღゝ◡╹)ノ❤️

Leetcode 每日抑题 (47. 全排列 II)

wallhavendg13mj.jpg

LeetCode的每日抑题系列 , LeetCode会每天随机一道题作为签到题。我也是菜鸡,如果今天没A掉,那只能证明我离大神又进了一步。

这次为什么使用java呢,是因为java版本使用的内存少,写起来方便,如果是scala的话,需要写大量的ListBuffer

image.png

题目链接

题名 通过率 难度
全排列 II 60.7% 中等

解题思路

就是求解去重后的全排列

暴力思路

1DFS枚举出所有的情况,枚举完成之后去重处理.最坏的情况就是原数组数字全是一样的,可能会出现超时.

优化搜索

1DFS枚举的过程中利用剪枝,减少重复排列的遍历,有前提,要经过排序,使得重复数字相邻出现.

java代码

 1import java.util.ArrayList;
 2import java.util.Arrays;
 3import java.util.List;
 4
 5/**
 6 * 描述:
 7 *
 8 * @author ludengke
 9 * @create 2020-09-14 10:58
10 */
11public class Solution3Java {
12    public List<List<Integer>> permuteUnique(int[] nums) {
13        boolean[] use = new boolean[nums.length];
14        List<List<Integer>> result = new ArrayList<>();
15        List<Integer> path = new ArrayList<>();
16        Arrays.sort(nums);
17        permuteUnique(nums,nums.length,0,use,path,result);
18        return result;
19    }
20
21    /**
22     * 
23     * @param nums 排序后原数组
24     * @param length 数组长度
25     * @param depth 已加入遍历路径path的元素的个数
26     * @param use 标记当前元素是否使用
27     * @param path 已遍历的路径
28     * @param result 存储全部结果
29     */
30    public void permuteUnique(int[] nums,int length,int depth,boolean[] use,List<Integer> path,List<List<Integer>> result) {
31        //全部元素已加入,则输出排序
32        if(length == depth){
33            result.add(new ArrayList<>(path));
34        }else {
35            //依次把未使用的数字加入到路径中,递归处理
36            for(int i = 0;i < length; i++){
37                //已使用略过
38                if(use[i] == true){
39                    continue;
40                }
41                //剪枝操作: 当前值和前一个值一样,并且前一个值经过了回溯 use[i-1] == false必须得有
42                //剪掉的分支是 本次循环和上次循环的取得的数字一样则可以略过. 
43                //use[i-1] = =true的时候是某重复元素的第一个实例已加入,进入递归,选择到了某重复元素的第一个实例,这种情况不需要剪枝处理
44                if(i > 0 && nums[i] == nums[i-1] && use[i-1] == false ){
45                    continue;
46                }
47
48                //标记已使用
49                use[i] = true;
50                //加入路径
51                path.add(nums[i]);
52                //递归处理子节点
53                permuteUnique(nums,length,depth+1,use,path,result);
54                //回溯处理,删除加入的最后一个节点,以及标记为未使用
55                path.remove(depth);
56                use[i] = false;
57            }
58        }
59    }
60
61    public static void main(String[] args) {
62        Solution3Java test = new Solution3Java();
63        System.out.println(test.permuteUnique(new int[]{1,2,3}));
64    }
65}
66

算法or数据结构

  1. DFS递归交换求全排列算法
  2. DFS,递归,全排列

扩展问题

种草


标题:Leetcode 每日抑题 (47. 全排列 II)
作者:ludengke95
地址:http://xvhi.ludengke95.xyz/articles/2020/09/18/1600398453093.html