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

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

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

题目链接

解题思路

就是求解去重后的全排列

暴力思路

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

优化搜索

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

java 代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 描述:
 *
 * @author ludengke
 * @create 2020-09-14 10:58
 */
public class Solution3Java {
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] use = new boolean[nums.length];
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);
        permuteUnique(nums,nums.length,0,use,path,result);
        return result;
    }

    /**
     * 
     * @param nums 排序后原数组
     * @param length 数组长度
     * @param depth 已加入遍历路径path的元素的个数
     * @param use 标记当前元素是否使用
     * @param path 已遍历的路径
     * @param result 存储全部结果
     */
    public void permuteUnique(int[] nums,int length,int depth,boolean[] use,List<Integer> path,List<List<Integer>> result) {
        //全部元素已加入,则输出排序
        if(length == depth){
            result.add(new ArrayList<>(path));
        }else {
            //依次把未使用的数字加入到路径中,递归处理
            for(int i = 0;i < length; i++){
                //已使用略过
                if(use[i] == true){
                    continue;
                }
                //剪枝操作: 当前值和前一个值一样,并且前一个值经过了回溯 use[i-1] == false必须得有
                //剪掉的分支是 本次循环和上次循环的取得的数字一样则可以略过. 
                //use[i-1] = =true的时候是某重复元素的第一个实例已加入,进入递归,选择到了某重复元素的第一个实例,这种情况不需要剪枝处理
                if(i > 0 && nums[i] == nums[i-1] && use[i-1] == false ){
                    continue;
                }

                //标记已使用
                use[i] = true;
                //加入路径
                path.add(nums[i]);
                //递归处理子节点
                permuteUnique(nums,length,depth+1,use,path,result);
                //回溯处理,删除加入的最后一个节点,以及标记为未使用
                path.remove(depth);
                use[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Solution3Java test = new Solution3Java();
        System.out.println(test.permuteUnique(new int[]{1,2,3}));
    }
}

算法 or 数据结构

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

扩展问题

• 46. 全排列
• 60. 第 k 个排列 : 这个题暴力真的会超时注意哦.

种草

• https://wallhaven.cc/ : 一个超牛逼的壁纸网站 , 我的封面图就是在上面找到的