By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、全排列1

给定一个 没有重复 数字的序列，返回其所有可能的全排列

示例:

输入: [1,2,3]      

输出:
    [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
    ]

1.1、解题思路

回溯法

1587455840358

1.2、算法=>回溯法

1.2.1、去重判断1


    /**
     * 1、使用 集合本身判断是否重复
     */
    public List<List<Integer>> permute2(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        huisu(nums, lists, new LinkedList<>());
        return lists;
    }

    public void  huisu(int[] nums, List<List<Integer>> list, LinkedList<Integer> array){
        if (array.size() == nums.length){
            list.add(new ArrayList<>(array));
            return;
        }
        for (int i = 0 ; i < nums.length; i++){
            //结果集中不能包含重复的
            if (array.contains(nums[i])){
                continue;
            }
            array.add(nums[i]);
            huisu(nums, list, array);
            //删除后一个节点，向上回溯
            array.removeLast();
        }
    }

1.2.2、去重判断2


    /**
     * 2、开启一个新的数组判断是否重复
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        huisu(nums,used, lists, new LinkedList<>());
        return lists;
    }

    public void  huisu(int[] nums,boolean[] used, List<List<Integer>> list, LinkedList<Integer> array){
        if (array.size() == nums.length){
            list.add(new ArrayList<>(array));
            return;
        }
        for (int i = 0 ; i < nums.length; i++){
            //结果集中不能包含吃不惯分页
            // if (array.contains(nums[i])){
            //     continue;
            // }
            if (used[i] == true){
                continue;
            }
            array.add(nums[i]);
            used[i] = true ;
            huisu(nums,used, list, array);
            //删除后一个节点，向上回溯
            used[i] = false ;
            array.removeLast();
        }
    }

1.3、测试

   @Test
    public void test(){
        int nums[] = {1,2,3,4};
        System.out.println(permute(nums));
    }

控制台：

[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]

1、全排列2

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

1.1、解题思路

同上，也是使用回溯法，我们唯一需要注意的地方就是去重 。层与层直接无需去重，如果是同一层，则需要去重

一定要排序，只有排序了，我们才能判断相邻的相等

1.2、算法

 public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        dfs(nums, used, new LinkedList<>(), list);
        return list;
    }

    private void dfs(int[] nums, boolean[] used, LinkedList array, List<List<Integer>> list) {
        if (array.size() == nums.length) {
            list.add(new ArrayList<>(array));
            return;
        }

        for (int i = 0; i < nums.length; ++i) {
            //当前值用过了(从开始回溯，肯定会重复使用，所以要判断) 或
            //当前值等于前一个值： 两种情况：（归根接地，就是要保证 同一层的时候，num[n-1] 如果不等于true了，continue）
            //1 [i-1] = false,没有被使用, 说明回溯到了同一层 ，这个时候满足了 nums[i] == nums[i - 1]，肯定是重复，所以continue
            //2 [i-1] = true, 用过了 说明此时在num[i-1]的下一层，这种情况可以往下走，不需要continue
            if (used[i] || (i > 0  && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }

            array.add(nums[i]);
            used[i] = true;
            dfs(nums, used, array, list);
            // 回溯部分的代码，和 dfs 之前的代码是对称的
            used[i] = false;
            array.removeLast();
        }
    }

1.3、测试

  @Test
    public void test(){
        int nums[] = {1,1,2};
        //切记必须要先排序啊！！！！！！这样只有相邻的才可能相等，才可以判断去除！！！！！
        Arrays.sort(nums);
        System.out.println(permuteUnique(nums));
    }

控制台：

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

​

ContactAuthor