day 36贪心(5)

2024-01-03 11:28:52

day 36

2024.1.3

1. 435无重叠区间
这道题我的做法与上一道题一致,多加了个记录变化区间范围的标量,本来向删除的,但想了想,没必要,结果返回删除的数量即可,所以将要删除的区间范围更改为不影响判断即可。

class Solution {
public:
    static bool compare(vector<int> a, vector<int> b){
        return a[1]<b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int result = 0;
        sort(intervals.begin(), intervals.end(), compare);
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0] < intervals[i-1][1]){
                result++;
                intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);
            }
        }
        return result;
    }
};

2. 763划分字母区间
这道题开始没思路,看了文字讲解后才明白。方法很巧妙。
分割的地方就是字母最后出现的位置,所以首先利用哈希原理记录每个字母出现的最后位置,然后比大小,直到遇到最大的,也就是最后位置了,则分为一段。以此类推。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hush[27] = {0};
        for(int i=0;i<s.size();i++){
            hush[s[i]-'a'] =i ;
        }
        int left = 0 ;
        int right = 0;
        vector<int> result;
        for(int i=0;i<s.size();i++){
            right = max(right, hush[s[i] - 'a']); 
                if (i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};

3. 56合并区间
这道题开始陷入了写代码误区,每次比较跟原始数组比较的,所以结果不正确,最后发现,直接跟result最后一个元素比较就好!

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        if (intervals.size() == 0) return result; // 区间集合为空直接返回
        // 排序的参数使用了lambda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});

        // 第一个区间就可以放进结果集里,后面如果重叠,在result上直接合并
        result.push_back(intervals[0]); 

        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
                // 合并区间,只更新右边界就好,因为result.back()的左边界一定是最小值,因为我们按照左边界排序的
                result.back()[1] = max(result.back()[1], intervals[i][1]); 
            } else {
                result.push_back(intervals[i]); // 区间不重叠 
            }
        }
        return result;
    }
};

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