代码随想录补|leetcode 46、47全排列问题

2024-01-03 09:29:13

46.力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

这道题和组合问题不同的是,本题允许[1,2,3][1,3,2]这种重复的,所以就不需要for循环时设定开始的索引避免重复。只需要先判断一下list集合里是不是有过这个元素了?如果有了,就continue本轮。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backtracking(nums);
        return result;
    }
    public void backtracking(int[] nums){
        if(list.size() == nums.length){
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0 ; i < nums.length; i++){
            if(list.contains(nums[i])){
                continue;
            }
            list.add(nums[i]);
            backtracking(nums);
            list.remove(list.size() - 1);
        }
    }
}

47.https://leetcode.cn/problems/permutations-ii/description/

这道题和上面不同的地方是本题的nums数组允许有重复,涉及去重问题。我们前面讲到了去重有两种方法:
1.nums数组可以进行sort——used数组去重

2.nums数组里的数不能随意改变顺序——set集合去重

本题显然是可以sort改变内部数的顺序的,所以本题采用used数组去重:

解释和day24-CSDN博客的40题一样,i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0时,continue;此外,和46一样,当list.contains(nums[i]) && used[i] == 1时,说明竖着的已经用过这个数了,也需要continue

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        int[] used = new int[nums.length];
        Arrays.sort(nums);
        backtracking(nums,used);
        return result;
    }
    public void backtracking(int[] nums, int[] used){
        if(nums.length == list.size()){
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0 ; i < nums.length; i++){
            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0 || used[i] == 1){
                continue;
            }
            list.add(nums[i]);
            used[i] = 1;
            backtracking(nums,used);
            used[i] = 0;
            list.remove(list.size() - 1);
        }
    }
}

文章来源:https://blog.csdn.net/l82049/article/details/135294686
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。