leetcode刷題12——區間系列

1.合并區間

以數組 intervals 表示若幹個區間的集合，其中單個區間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區間，并傳回一個不重疊的區間數組，該數組需恰好覆寫輸入中的所有區間。

考察知識點：排序

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> v;
        v.push_back(intervals[0]);
        for(int i=1;i<intervals.size();++i)
        {
            int left=intervals[i][0],right=intervals[i][1];
            if(left>v.back()[1])
                v.push_back(intervals[i]);
            else
                v.back()[1]=max(right,v.back()[1]);
        }
        return v;
    }
};
           

2.插入區間

給你一個 無重疊的 ，按照區間起始端點排序的區間清單。

在清單中插入一個新的區間，你需要確定清單中的區間仍然有序且不重疊（如果有必要的話，可以合并區間）。

考察知識點：模拟

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> v;
        int left=newInterval[0],right=newInterval[1];
        bool placed=false;
        for(int i=0;i<intervals.size();++i)
        {
            if(intervals[i][1]<left)
                v.push_back(intervals[i]);
            else if(intervals[i][0]>right)
            {
                if(!placed)
                {
                    v.push_back({left,right});
                    placed=true;
                }
                v.push_back(intervals[i]);
            } 
            else
            {
                left=min(intervals[i][0],left);
                right=max(intervals[i][1],right);                        
            }
        }
        if(!placed)
            v.push_back({left,right});
        return v;
    }
};
           

3.彙總區間

給定一個無重複元素的有序整數數組 nums 。傳回 恰好覆寫數組中所有數字 的 最小有序 區間範圍清單。也就是說，nums 的每個元素都恰好被某個區間範圍所覆寫，并且不存在屬于某個範圍但不屬于 nums 的數字 x 。

清單中的每個區間範圍 [a,b] 應該按如下格式輸出：

“a->b” ，如果 a != b

“a” ，如果 a == b

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int n=nums.size();
        if(n==0)  return {};
        vector<string> v;
        string s;
        int left=0,right=0;
        for(int i=1;i<n;++i)
        {
            if(long(nums[i])-long(nums[i-1])>1)
            {
                right=i-1;
                if(left==right)
                    s=to_string(nums[left]);
                else
                    s=to_string(nums[left])+"->"+to_string(nums[right]);
                v.push_back(s);
                left=i;
            }
        }
        if(left==n-1)
             s=to_string(nums[left]);
        else
             s=to_string(nums[left])+"->"+to_string(nums[n-1]);
         v.push_back(s);
        return v;
    }
};