专栏首页LeetCodeLeetCode 46 & 47. Permutations I&II
原创

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 条评论
登录 后参与评论

相关文章

  • LeetCode <dfs>108&109. Array & List to Binary Search Tree

    Given an array where elements are sorted in ascending order, convert it to a hei...

    大学里的混子
  • LeetCode <dp>152&628 Maximum Product Subarray

    Given an integer array nums, find the contiguous subarray within an array (conta...

    大学里的混子
  • Mysql基础

    1、Serializable (串行化):最严格的级别,事务串行执行,资源消耗最大;

    大学里的混子
  • LeetCode91|寻找重复数

    给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个...

    后端Coder
  • LeetCode_1. Two Sum_Solution

    这道题目的意思是给定一个数组和一个值,要求出这个数组中两个值的和等于这个给定值target。

    Zoctopus
  • 普通程序员该如何进阶为全栈工程师?

    如何成为一名全栈工程师(full stack developer)?互联网最热的话题之一。LinkedIn, Facebook上标榜自己是全栈工程师的人也越来...

    奔跑的小鹿
  • 车辆目标检测

    机器学习AI算法工程
  • 顺序栈的实现和两栈共享空间

    顺序栈的实现和两栈共享空间 一.顺序栈的实现        栈(stack)是限定仅在表尾进行插入或删除操作的线性表。我们把允许插入和删除的一端称为栈顶(t...

    猿人谷
  • 在vue中使用swiper

    用户4344670
  • Android ListView异步加载图片乱序问题,原因分析及解决方案

    在Android所有系统自带的控件当中,ListView这个控件算是用法比较复杂的了,关键是用法复杂也就算了,它还经常会出现一些稀奇古怪的问题,让人非常头疼。比...

    用户1158055

扫码关注云+社区

领取腾讯云代金券