代码随想录算法训练营第三十六天|435. 无重叠区间、763.划分字母区间、56. 合并区间

本文介绍: 【代码】代码随想录算法训练营第三十六天|435. 无重叠区间、763.划分字母区间、56. 合并区间。

图释：

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

文章链接：代码随想录

视频链接：LeetCode:763.划分字母区间

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[27]={0};
        for(int i=0; i<s.size(); i++){
            // s[i]-'a' ask||码，对应下标
            hash[s[i]-'a'] = i;  // 反复更新最远距离 
        }
        vector<int> result;
        int left = 0, right = 0;
        for(int i=0; i<s.size(); i++){
            right = max(right, hash[s[i]-'a']); // 每经过一格更新一下最远距离
            if(i==right){
                result.push_back(right-left+1);
                left = i+1;
            }
        }
        return result;
    }
};

class Solution {
public:
    static bool cmp(const vector<int>&a, const vector<int>&b){
         return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()<=1) return intervals;
        vector<vector<int>> result;
        vector<int> path;
        sort(intervals.begin(), intervals.end(), cmp);
        path.push_back(intervals[0][0]);
        for(int i=1; i<intervals.size(); i++){
            if(intervals[i-1][1] >= intervals[i][0]){
                // 更新右边边界
                intervals[i][1] = max(intervals[i][1], intervals[i-1][1]);
            }else{//没有重叠
                 path.push_back(intervals[i-1][1]);
                 result.push_back(path);
                 path.clear();
                 path.push_back(intervals[i][0]);
            }
        }
        path.push_back(intervals[intervals.size()-1][1]);
        result.push_back(path);
        return result;
    }
};

显示所有内容

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。