LeetCode 46 & 47. Permutations I&II

本文讲述的是有关于排列问题,这也是算法中的一个重要的方法:回溯法。

46. Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

题目大意:给出一个数组,这个数组是没有重复数字的,求出这个数组的全排列。

解法:

思路:这个其实就是一个树形问题。树形问题采用回溯法是较为经典的方法。

    List<List<Integer>> res = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) return res;
        LinkedList<Integer> p = new LinkedList<>();
        used = new boolean[nums.length];
        permuteHelper(nums,0,p);
        return res;
     }

     public void permuteHelper(int[] nums,int index,LinkedList<Integer> list){
        if (nums.length == index) {
            LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
            res.add(listClone);
            return;
        }

        for (int i = 0 ;i< nums.length;i++){
            if(used[i] == false){
                list.addLast(nums[i]);
                used[i] = true;
                permuteHelper(nums,index+1,list);
                used[i] = false;
                list.removeLast();
            }
        }
     }

我个人是不喜欢采用全局变量的,所以还是该为了函数变量。代码如下:

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> permuteRes = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        if (nums == null || nums.length == 0) return permuteRes;
        LinkedList<Integer> p = new LinkedList<>();
        permuteHelper(nums,p,permuteRes,used);
        return permuteRes;
    }

    public void permuteHelper(int[] nums,LinkedList<Integer> list, List<List<Integer>> permuteRes, boolean[] used){
        if (nums.length == list.size()) {
            LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
            permuteRes.add(listClone);
            return;
        }
        for (int i = 0 ;i<nums.length;i++){
            if(used[i] == false){
                list.addLast(nums[i]);
                used[i] = true;
                permuteHelper(nums,list,permuteRes,used);
                used[i] = false;
                list.removeLast();
            }
        }
    }

这是一个最为基本的排列问题,下面我们来看看一个有重复数字的数组,看看是如何让进行排列的。

    List<List<Integer>> res = new ArrayList<>();
    boolean[] used;   //采用的是全局变量,记录当前的元素是否已经使用了
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];  // 注意,虽然 used是定义的类的成员变量,但是分配空间可以在子函数里面进行
        if (nums.length == 0||nums == null) return res;   //如果数组为空或者数组里面没有元素 返回res
        LinkedList<Integer> p = new LinkedList<>();  //这里定义为LinkedList的目的是在结尾进行增删操作。
                                                     // 如果是ArrayList的话,只能在结尾添加,不能在结尾删除
        permute_recursion( nums,0,p);   // 初始时候。index的值为0,
        return res;
    }

    /**
     *
     * @param nums
     * @param index
     * @param list
     */
    public void permute_recursion(int[] nums, int index, LinkedList<Integer> list ) {
        if (nums.length == index) {    //当前的索引已经超出了 数组的最大的索引 ,说明list中存储的数据已经是一个完整的组合了
            LinkedList<Integer> list_clone = (LinkedList<Integer>)list.clone();//java参数是引用专递机制,发现list中存储的是一个完整的组合后,
                                                                               //将这个组合  克隆一份  添加到res中,否则后续的程序会修改list                 
            res.add(list_clone);  //将克隆后的组合添加到res中
            return;
        }


        for (int i =0;i <nums.length ;i++){
            if (used[i] == false ){   //这里采用的是一个boolean的数组,来记录当前的索引的元素是否已经使用过
                list.addLast(nums[i]); //将新的元素添加到list的尾部,
                used[i]  = true;  // 同时将used的数组 设置为true  表示这个元素已经使用过了
                permute_recursion(nums,index+1,list);  // 递归
                used[i] = false; //清除这个used的标记
                list.removeLast(); // 递归完毕后,将最后一个数据删除,以便于尝试其他的组合,这一步也就是回溯算法的“回溯”的体现所在
            }
        }
    }

47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解法一:

思路:有重复数字的排列的结果与没有重复数字的排列结果相比较,就是把没有重复数字的排列结果中相同的去掉了。所以我们可以很容易的想到借用java的Set数据结构,可以很容易的排重。

 public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> permuteRes = new ArrayList<>();
        Set<LinkedList<Integer>> set = new HashSet<>();
        boolean[] used = new boolean[nums.length];;
        if (nums == null || nums.length == 0) return permuteRes;
        LinkedList<Integer> p = new LinkedList<>();
        permuteHelper(nums,p,set,used);
        return new ArrayList<>(set);
    }

    public void permuteHelper(int[] nums,LinkedList<Integer> list, Set<LinkedList<Integer>> set, boolean[] used){
        if (nums.length == list.size()) {
            LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
            set.add(listClone);
            return;
        }
        for (int i = 0 ;i< nums.length;i++){
            if(used[i] == false){
                list.addLast(nums[i]);
                used[i] = true;
                permuteHelper(nums,list,set,used);
                used[i] = false;
                list.removeLast();
            }
        }
    }

解法二:

思路:能不能在查找的过程中就排除重复的情况呢?若果能,那么怎么排除呢?重复的情况又是怎样的呢?带着这些问题,我们发现重复的情况是:拿题目中[1,1,2]来说,如果第一次选1(0),第二次选择1(1),与第一次选1(1),第二次选择1(0),这是同样的结果,这就是重复的原因,所以当索引为i的数字等于索引为i-1的数字时候,如果索引为i-1的数字没有被使用,那么这种情况就是重复的,应该跳过,转化为程序就是:nums[i]== nums[i-1]&&used[i-1]==false,同时要要考虑此时i>0;所以这个时候,for循环中的判断就是if(used[i]||(i>0&&nums[i]== nums[i-1]&&used[i-1]==false)),满足条件则跳过。

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> permuteRes = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        if (nums == null || nums.length == 0) return permuteRes;
        permuteHelper(nums,new LinkedList<>(),permuteRes,used);
        return permuteRes;
    }

    public void permuteHelper(int[] nums,LinkedList<Integer> list, List<List<Integer>> permuteRes, boolean[] used){
        if (nums.length == list.size()) {
            LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
            permuteRes.add(listClone);
            return;
        }

        for (int i = 0 ;i< nums.length;i++){
            if(used[i]||(i>0&&nums[i] == nums[i-1]&&used[i-1]==false))  continue;
            list.addLast(nums[i]);
            used[i] = true;
            permuteHelper(nums,list,permuteRes,used);
            used[i] = false;
            list.removeLast();
        }
    }

还要注意的是,这样的解法必须数组数有序的数组,由于LeetCode46中的数组是没有重复数字的,因此不需要有序,所以首先要将数组进行一个排序处理。另外:解法二在查找的过程中就已经排除了重复的值,解法一是将左右的找到放在一个Set中进行去重,这样的时间效率显然没有解法二高。这种解法与解法一的不同之处在于,本解法是在查找到过程中就将不符合要求的情况排除出去,因此算法的效率有很明显的提升。

总结:

对与排列组合问题,首先想到的是采用回溯算法,回溯算法是算法中的几个较为经典的算法之一,这个算法的核心思想就是回溯的过程,代码中的list.removeLast();

很多人认为回溯和递归是一样的,其实不然。在回溯法中可以看到有递归的身影,但是两者是有区别的。回溯法从问题本身出发,寻找可能实现的所有情况。和穷举法的思想相近,不同在于穷举法是将所有的情况都列举出来以后再一一筛选,而回溯法在列举过程如果发现当前情况根本不可能存在,就停止后续的所有工作,返回上一步进行新的尝试。递归是从问题的结果出发,例如求 n!,要想知道 n!的结果,就需要知道 n*(n-1)! 的结果,而要想知道 (n-1)! 结果,就需要提前知道 (n-1)*(n-2)!。这样不断地向自己提问,不断地调用自己的思想就是递归。回溯和递归唯一的联系就是,回溯法可以用递归思想实现。

本算法就是回溯的体现,有关组合的问题可以参照《leetCode 77&39. Combinations & Combination Sum》;

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏架构之路

Combination Sum II 组合数求和之2-Leetcode

原题: Given a collection of candidate numbers (C) and a target number (T), find al...

3065
来自专栏java一日一条

Java 容器&泛型(1):认识容器

容器是Java语言学习中重要的一部分。泥瓦匠我的感觉是刚开始挺难学的,但等你熟悉它,接触多了,也就“顺理成章”地知道了。Java的容器类主要由两个接口派生而出:...

1192
来自专栏小灰灰

JDK容器学习之LinkedHashMap(二):迭代遍历的实现方式

LinkedHashMap 如何保障有序的遍历 前一篇《JDK容器学习之LinkedHashMap (一):底层存储结构分析》 中介绍了LinkedHashM...

3577
来自专栏来自地球男人的部落格

[LeetCode] 78. Subsets

【原题】 Given a set of distinct integers, nums, return all possible subsets. Not...

2769
来自专栏猿人谷

二叉搜索树的后序遍历序列

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一...

2087
来自专栏静默虚空的博客

排序六 堆排序

堆的概念 在介绍堆排序之前,首先需要说明一下,堆是个什么玩意儿。 堆是一棵顺序存储的完全二叉树。 其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小...

18710
来自专栏武培轩的专栏

Java中Set集合是如何实现添加元素保证不重复的?

Java中Set集合是如何实现添加元素保证不重复的? Set集合是一个无序的不可以重复的集合。今天来看一下为什么不可以重复。 Set是一个接口,最常用的实现类就...

3957
来自专栏郭耀华‘s Blog

剑指offer第六天

29.最小的K个数 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 解法一: Part...

2706
来自专栏DHUtoBUAA

找出该树中第二小的值--思路及算法实现

  在二叉树中最重要的操作莫过于遍历,即按照某一顺序访问树中的所有节点。二叉树的前序遍历、中序遍历、后序遍历都有递归和循环两种不同的实现方法。每种遍历的递归实现...

3125
来自专栏俞其荣的博客

HashMap内部原理解析HeaderHashMap 必知源码分析Java 1.8 中 HashMap 的不同Footer

27910

扫码关注云+社区

领取腾讯云代金券