算法训练营Day26

2023-12-27 22:58:41

#Java #全排列 #回溯

开源学习资料

Feeling and experiences:

递增子序列:力扣题目链接

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

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

这道题要注意的点:

目的就是早递增子序列,所以不能对原来的数值进行排列

所以不能像子集II 那个问题一样,先给数组中的元素排好顺序,再来用used数组标记。

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
    back(nums,0);
    return ans;
    }

    public void back(int []nums,int startIndex){
        //什么时候收集?
        if(path.size() >= 2){
            ans.add(new ArrayList<>(path));
        }
         //该题又要去重,又要使其为递增
        //建立一个Set集合
        Set<Integer> set = new HashSet<>();
        for(int i=startIndex;i<nums.length;i++){
        if(!path.isEmpty() && path.get(path.size()-1)>nums[i] || set.contains(nums[i])){
            continue;
        }
        set.add(nums[i]);
        path.add(nums[i]);
        back(nums,i+1);
        path.remove(path.size()-1);
        }
    }
}

?Set集合的使用:(为什么Set集合放在for循环外部?)

1. 去重的目的:

目的是确保在同一递归层级中,不会因为重复选择同一个元素而生成重复的子序列。这是为了防止例如?[1,?2,?2]?这样的数组生成两个相同的子序列?[1,?2]。


2. 作用域的问题:

如果?Set?被放在?for?循环内,那么每次循环时都会创建一个新的?Set。这意味着对于每个元素,Set?都是空的,所以每个元素都会被认为是“新”的,从而无法阻止同一层级中的重复选择。


3. 保持状态:

将?Set?放在?for?循环外部,可以让它在整个递归调用的特定层级中保持状态。这样,当递归到同一层级的不同部分时,Set?中已经包含了该层级中先前考虑过的元素,有效防止重复。

全排列:力扣题目链接

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

经典的模板题

这里引用代码随想录中的图解:

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean []used;
    public List<List<Integer>> permute(int[] nums) {
    used = new boolean[nums.length];
    Arrays.fill(used,false);
    back(nums);
    return ans;
    }
    public void back(int []nums){
    if(path.size() == nums.length){
        ans.add(new ArrayList<>(path));
    }
    for(int i = 0;i<nums.length;i++){
        //判断是否用过
        if(used[i] == true){
          continue;
        }
        used[i] = true;
        path.add(nums[i]);
        back(nums);
        used[i] = false;
        path.remove(path.size()-1);
    }
    }
}

充分利用了used数组~

全排列 II:力扣题目链接

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

关键点:树层去重

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean []used;
    public List<List<Integer>> permuteUnique(int[] nums) {
    //把数组进行排列
     Arrays.sort(nums);
    used = new boolean[nums.length];
     Arrays.fill(used,false);
     back(nums);
     return ans;

   
    }
    public void back(int []nums){
        if(path.size() == nums.length){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i =0;i<nums.length;i++){
            //去重
            if(i>0 && nums[i] == nums[i-1] && used[i-1] == true){
                continue;
            }
            if(used[i] == false){
                used[i] = true;
                path.add(nums[i]);
                 //回溯
            back(nums);
            path.remove(path.size()-1);
            used[i] = false;
            }
           
        }
    }
}

?整体思路:

? 首先,将数组排序。这样,相同的元素会相邻,便于去重。
? 在?back?方法中,使用?if?条件进行去重:
? if?(i?>?0?&&?nums[i]?==?nums[i?-?1]?&&?used[i?-?1]?==?true):这个条件检查当前元素是否与前一个元素相同,并且前一个元素已经被使用过。如果是,就跳过当前元素,避免在同一树层生成重复的排列。

?

此时相望不相闻,

愿逐月华流照君~

Fighting!

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