【代码随想录】刷题Day36-Toy模板网

这篇具有很好参考价值的文章主要介绍了【代码随想录】刷题Day36。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.无重叠区间

435. 无重叠区间

先从小到大排序，其实本题依然是求出共同区域，只不过题目需要我们删除尽量少的区间。所以我们需要删除的一定是范围跨度大的并且跟其他有公共区间的区域。所以每次更新右边范围都需要考虑最小的范围。

1.if(intervals[i][0]<end)，说明有重复的区间，那么我们需要ret++，并且更新较小的右边范围end=(intervals[i][1]>end)?end:intervals[i][1];

2.if(intervals[i][0]>=end)，说明是不同的区间，那么我们更新右边范围即可end=intervals[i][1];

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()==0)
            return 0;
        sort(intervals.begin(),intervals.end());
        int ret = 0;
        int end = intervals[0][1];
        for(int i=1;i<intervals.size();i++)
        {
            if(intervals[i][0]<end)
            {
                ret++;
                end=(intervals[i][1]>end)?end:intervals[i][1];
            }
            else
                end=intervals[i][1];
        }
        return ret;
    }
};

2.划分字母区间

763. 划分字母区间

1.首先我们必须记录每一个出现过的英语字母最后一次在哪个位置。由于英语字母会重复出现，所以使用哈希表进行去重处理，遍历整个字符串，而um[s[i]]=i就是记录每个字符最后出现的位置。

2.设立begin和end记录当前的左边和右边范围。

3.遍历一遍字符串，如果i>=end&&end<um.find(s[i])->second+1，说明此时是一个新的字符，那么更新begin和end：begin=end，begin为上一次的最右边；end=um.find(s[i])->second+1为当下字符对应最后出现的位置。ret.push_back(end-begin)，不过要注意，此时的push的元素只是目前位置当前字母的最大范围内有多少字母，不是真正题目要求的

4.if(i<end)，说明当下的字母依然是在一个范围内的，但是这个字母出现的最后位置需要我们和end比较，因为此时的end是上一次字母的最后位置，不是整个非重复字符的，那么end=(end>um.find(s[i])->second+1)?end:um.find(s[i])->second+1;就是更新当前最右边范围，那么不管更新与否，我们都将ret最后的元素更新，即ret[ret.size()-1]=end-begin;都能满足当前调整的要求

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> ret;
        unordered_map<char,int> um;
        int begin = 0;
        int end = 0;
        for(int i=0;i<s.size();i++)
            um[s[i]]=i;
        for(int i=0;i<s.size();i++)
        {
            if(i<end)
            {
                end=(end>um.find(s[i])->second+1)?end:um.find(s[i])->second+1;
                ret[ret.size()-1]=end-begin;
            }
            else if(end<um.find(s[i])->second+1)
            {
                begin=end;
                end=um.find(s[i])->second+1;
                ret.push_back(end-begin);
            } 
        }
        return ret;
    }
};

3.合并区间

56. 合并区间

1.排序，得到顺序的范围

2.if(i==0)，ret.push_back(intervals[i]);如果i==0，那么此时直接将第一个范围push到ret

3.其他情况下，只有两个可能：

if(ret[ret.size()-1][1]>=intervals[i][0])：说明此时有重复的范围，那么int end = (ret[ret.size()-1][1]>intervals[i][1])?ret[ret.size()-1][1]:intervals[i][1];将最右边的范围确定下来，由于我们会修改最后的ret，那么先将当前的左边范围int begin = ret[ret.size()-1][0];保持不变，修改当前最后的retret.pop_back();此时更新当前的当前的范围ret.push_back({begin,end});

else：说明此时没有公共区域，那么就需要新开辟空间随后让后面的判断是否还有公共空间，此时的思路与i==0相同，ret.push_back(intervals[i]);文章来源地址https://www.toymoban.com/news/detail-467130.html

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ret;
        sort(intervals.begin(),intervals.end());
        for(int i=0;i<intervals.size();i++)
        {
            if(i==0)
                ret.push_back(intervals[i]);
            else
            {
                if(ret[ret.size()-1][1]>=intervals[i][0])
                {
                    int end = (ret[ret.size()-1][1]>intervals[i][1])?ret[ret.size()-1][1]:intervals[i][1];
                    int begin = ret[ret.size()-1][0];
                    ret.pop_back();
                    ret.push_back({begin,end});
                }
                else
                    ret.push_back(intervals[i]);
            }
        }
        return ret;
    }
};

到了这里，关于【代码随想录】刷题Day36的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！