算法训练营Day32

#Java #贪心

开源学习资料

Feeling and experiences：

无重叠区间：力扣题目链接

给定一个区间的集合?intervals?，其中 intervals[i] = [starti, endi]?。返回 需要移除区间的最小数量，使剩余区间互不重叠?。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

这道题和之前做的射气球几乎一模一样

一看到重叠区间问题，首先想到的就是排序（我以左边界排序）

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b)-> {
            return Integer.compare(a[0],b[0]);
        });
        int count = 1;
        for(int i = 1;i < intervals.length;i++){
            if(intervals[i][0] < intervals[i-1][1]){
                intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);    
            }else{
                count++;
            }    
        }
        return intervals.length - count;
    }
}

结合代码随想录中的图例：

当两个区间重叠时，保留右边界较小的区间意味着结束时间更早，因此与后续区间重叠的可能性更小。这是因为一个区间结束得越早，它就越不可能与后面的区间重叠。

划分字母区间：力扣题目链接

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

这道题其实不难，但是要结合图示才好理解

?

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
    int []edge = new int[26];
    int length = s.length();
    for(int i =0;i<length;i++){
        edge[s.charAt(i)-'a'] = i;
    }
    
    int start = 0;
    int end =0;
    for(int i =0;i<length;i++){
        end = Math.max(end,edge[s.charAt(i)-'a']);
        if(i==end){
            list.add(end-start+1);
            //跟新开始位置
            start = end+1;
        }
    }
    return list;
    }
}

第一次遍历：遍历字符串?s。对于字符串中的每个字符，更新?edge?数组，使?edge[s.charAt(i)?-?'a']?存储字符?s.charAt(i)?最后一次出现的索引。

第二次遍历：再次遍历字符串?s。在这次遍历中，用?Math.max(end,?edge[s.charAt(i)?-?'a'])?更新?end?的值。这里的目标是找到当前部分的最远结束位置，即当前部分中所有字符的最后出现位置的最大值。

合并区间：力扣题目链接

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回?一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间?。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

仿照力扣写的：

class Solution {
    public int[][] merge(int[][] intervals) {
    //重写compare方法
   // if(intervals.length == 0){
       // return new int[0][2];
   // }
   //按照左边界
    Arrays.sort(intervals,new Comparator<int[]>(){
        public int compare(int[] intervals1,int [] intervals2){
            return intervals1[0] -intervals2[0];
        }
    });
    //创建一个集合来存储区间
    ArrayList<int[]> merged = new ArrayList<int[]>();
    for(int i =0;i<intervals.length;++i){
        int Left = intervals[i][0];
        int Right = intervals[i][1];
        if(merged.size() == 0 || merged.get(merged.size()-1)[1]<Left){  //右边界小于左边界，说明不重合，则直接添加到集合中
        merged.add(new int[]{Left,Right});
    }
    else{
        merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1],Right);
    }
    }
    return merged.toArray(new int[merged.size()][]);
    }
    }

?第二次，自己重新写了一遍，并整理了思路，简化了一些步骤

class Solution {
    public int[][] merge(int[][] intervals) {
    //常见一个集合存答案
    List<int[]> list = new ArrayList<>();

    //用lambda表达式，重写compere方法进行左边界排序
    Arrays.sort(intervals,(x,y)->x[0]-y[0]);

    int start = intervals[0][0]; //最初左边界
    int maxEnd = intervals[0][1];//最大右边界
    //进入for循环
    for(int i = 1;i<intervals.length;i++){
        //如果当前区间的左边界大于最大右边界（说明这个两个区间已经没有公共区间了），则把该区间加入到集合中
        if(intervals[i][0]>maxEnd){
            list.add(new int[]{start,maxEnd});
            //并且还要跟新左右边界
            start = intervals[i][0];
            maxEnd = intervals[i][1];
        }
        else{
            //说明有重叠，则跟新最大右边界
            maxEnd=Math.max(maxEnd,intervals[i][1]);
        }
    }
    //最后还要加一次
     list.add(new int[]{start,maxEnd});
      return list.toArray(new int[list.size()][]);
}
}

? 对?intervals?进行遍历，从第二个区间开始。
? 如果当前区间的左边界大于?maxEnd，说明当前区间与之前的区间没有重叠。这时，将之前的区间?[start,?maxEnd]?加入到结果列表中，并更新?start?和?maxEnd?为当前区间的值。
? 如果当前区间的左边界小于或等于?maxEnd，说明有重叠。在这种情况下，更新?maxEnd?为当前区间的右边界和?maxEnd?中的较大值，以扩展当前合并区间的右边界。

谎言不会伤人，

真相才是快到~

Fighting！