2021-7-12 LeetCode

全排列

46. 全排列 - 力扣(LeetCode) (leetcode-cn.com)

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序*返回答案。

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路:

采用递归,核心思想如:需要将[1,2,3]全排列,拆分成两部分,第一个数字和剩下的数字,在这里,可以拆分为1 和2 3,2 和 1 3,3 和1 2。则[1,2,3]的全排列相当于 1加上[2,3]的全排列,即[2,3],[3,2],最终以1开头的结果为[1,2,3]和[1,3,2],剩下的数字类似,最终把分别以1,2,3开头的全排列加起来就是所有排列结果。整体思路就是这样,能力不足,不太容易用更通俗的语言和原理来解释,只能通过例子来解释。

代码:

未优化版本:

时间和空间复杂度都很高。。。。

// 交换数组中两个数
public void swap(int[] list, int idx1, int idx2) {
    int tmp = list[idx1];
    list[idx1] = list[idx2];
    list[idx2] = tmp;
}

public List<List<Integer>> permute(int[] nums) {
    if (nums.length == 0)
        return null;
    List<List<Integer>> perList = new ArrayList<>();
    List<Integer> per = new ArrayList<>();
    if (nums.length == 1) {
        per.add(nums[0]);
        perList.add(per);
        return perList;
    }
    // 遍历以每个数字作为首字母的排列
    for (int j = 0; j < nums.length; j++) {
        swap(nums, 0, j);
        List<List<Integer>> tmp = permute(Arrays.copyOfRange(nums, 1,nums.length));
        for (List<Integer> i : tmp) {
            per = new ArrayList<>();
            per.add(nums[0]);
            per.addAll(i);
            perList.add(per);
        }
        swap(nums, j, 0);
    }
    return perList;
}
优化版本:
public void backTrace(int first, List<Integer> out, List<List<Integer>> res,int len){
    if (first == len) {
        res.add(new ArrayList<>(out));
        return;
    }
    for (int i = first; i < len; i++) {
        Collections.swap(out, i, first);
        backTrace(first + 1,out, res, len);
        Collections.swap(out, first, i);
    }
}
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> perList = new ArrayList<>();
    List<Integer> out = new ArrayList<>();
    for (int i : nums) {
        out.add(i);
    }
    backTrace(0, out,perList, nums.length);
    return perList;
}

这是参照题解写的代码(虽然基本上和题解一模一样了),看了这个代码后分析了一下自己前面写的代码存在的问题。 我前面是通过nums来在递归过程中生成一个个List<Integer>,再通过addAll方法一个个添加进上一级递归的结果中。。。现在看来这样的方法真的很蠢,浪费了很多空间不说,时间也用了很多。还有就是我之前是通过交换nums里面的元素再添加进List<Integer>中,其实这完全可以合并成一步:先把nums的全部元素添加进一个List中,然后只需要不断递归交换里面的元素就行了。这样就剩下了很多中间产生的List,还节约了时间。

2021-7-12 LeetCode

上一篇:Pytorch数据读取机制(DataLoader)与图像预处理模块(transforms)


下一篇:7.事务+乐观锁