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

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

题目：435. 无重叠区间

图释：

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;
    }
};

题目：763.划分字母区间

文章链接：代码随想录

视频链接：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;
    }
};

题目：56. 合并区间

文章链接：代码随想录

视频链接：LeetCode:56.合并区间

题目链接：力扣题目链接

图释：

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;
    }
};

原文地址:https://blog.csdn.net/m0_71413464/article/details/135635680

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_57166.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

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