算法训练营Day36(贪心-重叠区间)

2024-01-07 23:43:02

都算是?重叠区间?问题,大家可以好好感受一下。?都属于那种看起来好复杂,但一看贪心解法,惊呼:这么巧妙!?

还是属于那种,做过了也就会了,没做过就很难想出来。

不过大家把如下三题做了之后,?重叠区间?基本上差不多了

435.?无重叠区间?

435. 无重叠区间 - 力扣(LeetCode)

我这里先给一下为什么不取最大值的问题吧,我没看视频自己做的时候写的

如果用max的话,就是直接计算重复区间了,但是这道题还要删去,所以直接取右边界的最小值

答案:

这是我写的,和卡哥的也不一样,很简单

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

        }
        return count;
    }
}

763.划分字母区间?

763. 划分字母区间 - 力扣(LeetCode)

题意难,听卡哥讲,easy很多。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int [] hash = new int[27];
        //记录每个字母的最远位置
        for(int i = 0;i<s.length();i++){
            hash[s.charAt(i)-'a'] = i; 
        }
        List<Integer> res = new ArrayList<>();

        //找left和right
        int left= 0,right=0;
        for(int i = 0;i<s.length();i++){
            right = Math.max(right,hash[s.charAt(i)-'a']);
            if(i == right){
                res.add(right-left+1);
                //更新边界
                left = i+1;
            }
        }
        return res;
    }
}

56.?合并区间?

56. 合并区间 - 力扣(LeetCode)

这个很easy

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0])); 
        List<int[]> res = new ArrayList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];
        for(int i =1;i< intervals.length;i++){
            if(intervals[i][0]<=end){
                //更新右边界
                end = Math.max(end,intervals[i][1]);
               
            }else{
                 //收集结果
                int [] subRes = new int[]{start,end};
                res.add(subRes);
                //更新 新的begin 和end
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        res.add(new int[]{start,end});
        return res.toArray(new int[res.size()][]);
    }
}

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