Day36——435. 无重叠区间 763.划分字母区间 56. 合并区间

简介: Day36——435. 无重叠区间 763.划分字母区间 56. 合并区间

前言


今日文案:

其实,余生并不长,做喜欢的事情,在一个正当好的人,东有飘雪,夏有凉风,以美好的心态对待每一天,尽量把遗憾降到最低,如此才是不辜负自己。

一、无重叠区间


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

力扣

贪心思路:


我们只需要找出单独的区间有多少个,然后总数减去单独区间就是要去掉的区间。

右边界排序,每次取非交叉区间的时候,都是可右边界最小的来做分割点(这样留给下一个区间的空间就越大),所以第一条分割线就是区间1结束的位置。

class Solution {
public:
    static bool cmp(vector<int>&a,vector<int>&b)
    {
        return a[1]<b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int count=1;
        sort(intervals.begin(),intervals.end(),cmp);        //右边界升序排序
        int end=intervals[0][1];                    //初始化
        for(int i=1;i<intervals.size();i++)
        {
            if(end<=intervals[i][0])        //如果是单独区间
            {
                end=intervals[i][1];        //右边界推进
                count++;                //数量加1
            }
        }
        return intervals.size()-count;
    }
};

二、划分字母区间


力扣

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表.

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[27]={0};
        vector<int>res;
        for(int i=0;i<s.size();i++)
        {
            hash[s[i]-'a']=i;        //哈希记录字母出现的最远的值
        }
        int right=0;
        int left=0;
        for(int i=0;i<s.size();i++)
        {
            right=max(right,hash[s[i]-'a']);    //right记录当前字母区间的最远值
            if(i==right)                        //相等的时候就是找到了当前字母区间最远值
            {
                res.push_back(right-left+1);    //保存长度
                left=right+1;                    //更新起始位置
            }    
        }
        return res;
    }
};

三、合并区间


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

力扣

class Solution {
public:
    static bool cmp(vector<int>&a,vector<int>&b)
    {
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()==1||intervals.size()==0)
        {
            return intervals;
        }
        sort(intervals.begin(),intervals.end(),cmp);    //右边界排序
        int right=intervals[0][1];                    //初始化
        int left=intervals[0][0];
        int flag=0;
        vector<vector<int>> res;
        vector<int>path;
        for(int i=1;i<intervals.size();i++)
        {
            flag=0;
            while(i<intervals.size()&&right>=intervals[i][0])    //右边界关系
            {
                right=max(right,intervals[i][1]);        //更新区间
                left=min(left,intervals[i][0]);
                i++;                                //直接跳下一个
            }
            res.push_back({left,right});        //插入
            if(i<intervals.size())            //准备退出辽
            {
                left=intervals[i][0];            //最后记录一波
                right=intervals[i][1];
                flag=1;                //记下标志
            }
        }
        if(flag)
        res.push_back({left,right});        //插入,否则会漏一个
        return res;
    }
};

总结


1、关键是记录单个区间的值,右边界排序后,删最小右边界,右边会有更大空间。

2、用哈希来记录最长延长距离

3、排序后,分清记录值。

相关文章
|
6月前
|
算法 前端开发
统计定界子数组的数目
统计定界子数组的数目
42 0
|
6月前
|
算法 测试技术 C#
C++二分查找算法:包含每个查询的最小区间
C++二分查找算法:包含每个查询的最小区间
|
6月前
leetcode-435:无重叠区间
leetcode-435:无重叠区间
33 0
|
6月前
代码随想录Day30 贪心05 LeetCode T435无重叠区间 T763划分字母区间 T56 合并区间
代码随想录Day30 贪心05 LeetCode T435无重叠区间 T763划分字母区间 T56 合并区间
51 0
|
6月前
|
Java
leetcode-763:划分字母区间
leetcode-763:划分字母区间
45 0
|
算法 索引
算法训练Day36|435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间
算法训练Day36|435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间
leetcode 763划分字母区间
leetcode 763划分字母区间
92 0
leetcode 763划分字母区间
|
Python
LeetCode 435. 无重叠区间
给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
99 0
代码随想录刷题|LeetCode 435. 无重叠区间 763.划分字母区间 56. 合并区间
代码随想录刷题|LeetCode 435. 无重叠区间 763.划分字母区间 56. 合并区间
代码随想录刷题|LeetCode 435. 无重叠区间 763.划分字母区间 56. 合并区间