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

痛定思痛。 2023-09-30 12:08 47阅读 0赞

## 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());
        }
    }