mzoe666888

V1

2022/04/28阅读:24主题:兰青

内卷大厂系列《全排列问题二连击》

大厂高频算法面试题:《全排列问题系列》,您将学到如何设计递归,递归的好坏直接影响到动态规划,其次递归涉及到深度优先遍历时,要考虑恢复现场,如何剪枝,如何去重等技巧。

一、全排列问题 I

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

示例 1

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

示例 2

输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3

输入:nums = [1]
输出:[[1]]

leetcode

1、分析

方法一暴力解,当前来到i位置,i之前的位置(左边)已经做了选择,只能从i开始向右边做选择,从N个数中选一个,然后i+1位置上从N-1个数中选一个,i+2位置从N-2个数中选一个

arr[0...i]已经做了选择,从arr[i+1...]做选择

方法二深度优先遍历,当前来到index位置,arr[0...index-1]位置上的数已经选好了,从arr[index...N-1]选数,把每轮收集的排列用ans收集起来,记得要清理现场,深度优先遍历一概的技巧。

2、实现

2.1、方法一

public static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    HashSet<Integer> rest = new HashSet<>();
    for (int num : nums) {
        rest.add(num);
    }
    ArrayList<Integer> path = new ArrayList<>();
    f(rest, path, ans);
    return ans;
}

// rest中有剩余数字,已经选过的数字不在rest中,选过的数字在path里
public static void f(HashSet<Integer> rest, ArrayList<Integer> path, List<List<Integer>> ans) {
    if (rest.isEmpty()) {
        ans.add(path);
    } else {
        for (int num : rest) {
            ArrayList<Integer> curPath = new ArrayList<>(path);
            curPath.add(num);
            HashSet<Integer> clone = cloneExceptNum(rest, num);
            f(clone, curPath, ans);
        }
    }
}

public static HashSet<Integer> cloneExceptNum(HashSet<Integer> rest, int num) {
    HashSet<Integer> clone = new HashSet<>(rest);
    clone.remove(num);
    return clone;
}

2.2、方法二

public static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    process(nums, 0, ans);
    return ans;
}

// 当前来到 index 位置,之前的nums[0...index-1] 的数已经选好了,从num[index...]开始选数
// 选好的答案放在ans里
public static void process(int[] nums, int index, List<List<Integer>> ans) {
    if (index == nums.length) { // base case
        ArrayList<Integer> cur = new ArrayList<>();
        for (int num : nums) {
            cur.add(num);
        }
        ans.add(cur);
    } else {
        for (int j = index; j < nums.length; j++) {
            swap(nums, index, j);
            process(nums, index + 1, ans);
            swap(nums, index, j); // 深度优先遍历,清理现场
        }
    }
}

public static void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

二、全排列问题 II

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列

示例 1

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

示例 2

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

leetcode

1、分析

全排列问题II就是在全排列问题I的基础上增加去重机制,仅此而已。

2、实现

public static List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    process(nums, 0, ans);
    return ans;
}

public static void process(int[] nums, int index, List<List<Integer>> ans) {
    if (index == nums.length) {
        ArrayList<Integer> cur = new ArrayList<>();
        for (int num : nums) {
            cur.add(num);
        }
        ans.add(cur);
    } else {
        HashSet<Integer> set = new HashSet<>();  // 防重
        for (int j = index; j < nums.length; j++) {
            if (!set.contains(nums[j])) {
                set.add(nums[j]);
                swap(nums, index, j);
                process(nums, index + 1, ans);
                swap(nums, index, j);
            }
        }
    }
}

public static void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

三、总结

增加去重表(剪枝):去重标记,在递归发生的过程中去重,剪掉

不剪枝(过滤):不增加去重表,递归全部跑完,收集的结果中去重(Set)

  1. 递归函数的设计好坏直接影响到动态规划
  2. 递归涉及到深度优先遍历时,要考虑恢复现场
  3. 递归过程中是否走过,可以增加标记表,剪枝效果
  4. 递归完毕后,也可以增加Set表去重,过滤效果

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1