[数据结构与算法]LeetCode(每日一题)-全排列系列

LeetCode(每日一题)-全排列系列

说明此文章是对于力扣的全排列题目的一个总结
其中序号46. 全排列、47. 全排列 II、剑指 Offer II 084. 含有重复元素集合的全排列、剑指 Offer II 083. 没有重复元素集合

【题目描述】
给定一个不含重复数字的数组 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]]

【题解】
我们可以定义定义递归函数backtrack(int[] nums, List perm ,int num)

• nums表示传入的数组
• perm是当前的排序
• num是数组中已经排序的个数

那么就可以分成两种情况

• num == nums.length 说明我们已经排序完 n 个位置（注意下标从 00 开始），找到了一个可行的解，我们将放入答案数组中，递归结束
• num < nums.length 我们要考虑这第num个位置我们要填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组vis[] 来标记已经填过的数。那么在填第 num个数的时候我们遍历题目给定的 n 个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(first + 1, perm)。回溯的时候要撤销这一个位置填的数以及标记，并继续尝试其他没被标记过的数。

当数组中有重复的数字
我们可以先排序数组，然后配合vis数组以及剪纸来完成去重

// 已经用过的数字不可用
if(vis[i]){
    continue;
}
// 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
// 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
if(i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]){
    continue;
}

【完成代码】

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author cVzhanshi
 * @create 2022-03-20 9:59
 */
public class FullArrangement {
    /**
     * 全排列  可重复
     */
    boolean[] vis;
    List<List<Integer>> result = new ArrayList<>();
    public  List<List<Integer>> permute(int[] nums) {
        //每次排序放到这个里面
        List<Integer> perm = new ArrayList<>();
        Arrays.sort(nums);
        vis = new boolean[nums.length];
        backtrack(nums,perm,0);
        return result;
    }

    public  void backtrack(int[] nums, List<Integer> perm ,int num) {
        if(num == nums.length){
            result.add(new ArrayList<>(perm));
            return;
        }
        for(int i = 0; i < nums.length; i++){
        	// 已经用过的数字不可用
            if(vis[i]){
                continue;
            }
            // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
            // 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
            if(i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]){
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums,perm,num + 1);
            vis[i] = false;
            perm.remove(num);
        }
    }
    
    
    
    public static void main(String[] args) {
        List<String> list = Arrays.asList(new String[]{"1","2","3","4"});
        System.out.println(permutation(list, 4));
        // 输出： [11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44]
        //System.out.println(permutationNoRepeat(list, 4));

    }


    /**
     * 排列组合（字符重复排列）<br>
     * 内存占用：需注意结果集大小对内存的占用（list:10位，length:8，结果集:[10 ^ 8 = 100000000]，内存占用:约7G）
     * @param list 待排列组合字符集合
     * @param length 排列组合生成长度
     * @return 指定长度的排列组合后的字符串集合
     * @author www@yiynx.cn
     */
    public static List<String> permutation(List<String> list, int length) {
        Stream<String> stream = list.stream();
        for (int n = 1; n < length; n++) {
            stream = stream.flatMap(i -> list.stream().map(j -> i.concat(j)));
        }
        return stream.collect(Collectors.toList());
    }

    /**
     * 排列组合(字符不重复排列)<br>
     * 内存占用：需注意结果集大小对内存的占用（list:10位，length:8，结果集:[10! / (10-8)! = 1814400]）
     * @param list 待排列组合字符集合(忽略重复字符)
     * @param length 排列组合生成长度
     * @return 指定长度的排列组合后的字符串集合
     * @author www@yiynx.cn
     */
    public static List<String> permutationNoRepeat(List<String> list, int length) {
        Stream<String> stream = list.stream().distinct();
        for (int n = 1; n < length; n++) {
            stream = stream.flatMap(i -> list.stream().filter(j -> !i.contains(j)).map(j -> i.concat(j)));
        }
        return stream.collect(Collectors.toList());
    }
}