C++實現(xiàn)LeetCode(57.插入?yún)^(qū)間)

更新時間：2021年07月16日 09:08:26 作者：Grandyang

這篇文章主要介紹了C++實現(xiàn)LeetCode(57.插入?yún)^(qū)間),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下

[LeetCode] 57. Insert Interval 插入?yún)^(qū)間

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

這道題讓我們在一系列非重疊的區(qū)間中插入一個新的區(qū)間，可能還需要和原有的區(qū)間合并，可以對給定的區(qū)間集進行一個一個的遍歷比較，那么會有兩種情況，重疊或是不重疊，不重疊的情況最好，直接將新區(qū)間插入到對應(yīng)的位置即可，重疊的情況比較復(fù)雜，有時候會有多個重疊，需要更新新區(qū)間的范圍以便包含所有重疊，之后將新區(qū)間加入結(jié)果 res，最后將后面的區(qū)間再加入結(jié)果 res 即可。具體思路是，用一個變量 cur 來遍歷區(qū)間，如果當前 cur 區(qū)間的結(jié)束位置小于要插入的區(qū)間的起始位置的話，說明沒有重疊，則將 cur 區(qū)間加入結(jié)果 res 中，然后 cur 自增1。直到有 cur 越界或有重疊 while 循環(huán)退出，然后再用一個 while 循環(huán)處理所有重疊的區(qū)間，每次用取兩個區(qū)間起始位置的較小值，和結(jié)束位置的較大值來更新要插入的區(qū)間，然后 cur 自增1。直到 cur 越界或者沒有重疊時 while 循環(huán)退出。之后將更新好的新區(qū)間加入結(jié)果 res，然后將 cur 之后的區(qū)間再加入結(jié)果 res 中即可，參見代碼如下：

解法一：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int n = intervals.size(), cur = 0;
        while (cur < n && intervals[cur][1] < newInterval[0]) {
            res.push_back(intervals[cur++]);
        }
        while (cur < n && intervals[cur][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[cur][0]);
            newInterval[1] = max(newInterval[1], intervals[cur][1]);
            ++cur;
        }
        res.push_back(newInterval);
        while (cur < n) {
            res.push_back(intervals[cur++]);
        }
        return res;
    }
};

下面這種方法的思路跟上面的解法很像，只不過沒有用 while 循環(huán)，而是使用的是 for 循環(huán)，但是思路上沒有太大的區(qū)別，變量 cur 還是用來記錄新區(qū)間該插入的位置，稍有不同的地方在于在 for 循環(huán)中已經(jīng)將新區(qū)間后面不重疊的區(qū)間也加進去了，for 循環(huán)結(jié)束后就只需要插入新區(qū)間即可，參見代碼如下：

解法二：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int n = intervals.size(), cur = 0;
        for (int i = 0; i < n; ++i) {
            if (intervals[i][1] < newInterval[0]) {
                res.push_back(intervals[i]);
                ++cur;
            } else if (intervals[i][0] > newInterval[1]) {
                res.push_back(intervals[i]);
            } else {
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
            }
        }
        res.insert(res.begin() + cur, newInterval);
        return res;
    }
};

下面這種解法就是把上面解法的 for 循環(huán)改為了 while 循環(huán)，其他的都沒有變，代碼如下：

解法三：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int n = intervals.size(), cur = 0, i = 0;
        while (i < n) {
            if (intervals[i][1] < newInterval[0]) {
                res.push_back(intervals[i]);
                ++cur;
            } else if (intervals[i][0] > newInterval[1]) {
                res.push_back(intervals[i]);
            } else {
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
            }
            ++i;
        }
        res.insert(res.begin() + cur, newInterval);
        return res;
    }
};

到此這篇關(guān)于C++實現(xiàn)LeetCode(57.插入?yún)^(qū)間)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)插入?yún)^(qū)間內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: