当前位置：首页 > article >正文

代码随想录day24 | leetcode 491.递增子序列 46.全排列 47.全排列 II

article 2025/1/14 18:35:12

递增子序列

题目：给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

解答：
对给定序列不能做改动。
使用set 来判断原序列中元素是否被使用。
不能使用boolean数组来记录。

 LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        
         backpacking(nums,0);
        return result;
    }


        public void backpacking(int[] nums,int startIndex){
        if (path.size()>1){
            result.add(new ArrayList<>(path));
        }
        if (startIndex>=nums.length){
            return;
        }
         Set<Integer> th = new HashSet<>();
        for (int i = startIndex; i <nums.length; i++) {
           
            if (!path.isEmpty()&&nums[i]<path.getLast()||th.contains(nums[i])){
             continue;
            }
            th.add(nums[i]);
            path.add(nums[i]);
           
            backpacking(nums,i+1);
            path.removeLast();
           
        }

    }

全排列

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

排列中要使用之前的元素，剪枝与去重不同于之前。解法：使用used布尔类型的数组，来记录以取过的数，path中存的数的是未选过的数。

LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
           boolean[] used = new boolean[nums.length];
        Arrays.fill(used,false);
        backtracking(nums,used);
        return result;
    }

    public void backtracking(int[] nums,boolean[] used){
        if (path.size()==nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(used[i] == true){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtracking(nums,used);
            used[i] = false;
            path.removeLast();

        }
    }

全排列II

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

排列中要使用之前的元素，剪枝与去重不同于之前。
解法：使用used布尔类型的数组，来记录以取过的数，path中存的数的是未选过的数。

这是去重逻辑的核心部分。它执行以下检查：

i > 0：确保不是在第一个元素上执行此检查（因为第一个元素没有前一个元素）。
nums[i] == nums[i - 1]：检查当前元素是否与它的前一个元素相同。
used[i - 1] == false：检查前一个元素是否没有被使用过。如果前一个元素没有被使用过，则意味着在当前递归层级中，我们已经处理过相同的元素，因此应该跳过当前元素以避免重复。

如果上述条件都满足，continue 语句将跳过当前循环的剩余部分，并开始下一次循环迭代。

LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
          boolean[] used = new boolean[nums.length];
        Arrays.fill(used,false);
        Arrays.sort(nums);
        backtracking(nums,used);
        return result;
    }

    public void backtracking(int[] nums,boolean[] used){
        if (path.size()==nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i>0&&nums[i] == nums[i-1]&&used[i-1] == false){
                continue;
            }
            if(used[i]==false){
            used[i] = true;
            path.add(nums[i]);
            backtracking(nums,used);
            used[i] = false;
            path.removeLast();
            }
        }
    }