溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

C++如何插入?yún)^(qū)間

發(fā)布時間:2022-03-28 13:46:36 來源:億速云 閱讀:142 作者:iii 欄目:大數(shù)據(jù)

這篇文章主要介紹“C++如何插入?yún)^(qū)間”,在日常操作中,相信很多人在C++如何插入?yún)^(qū)間問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對大家解答”C++如何插入?yún)^(qū)間”的疑惑有所幫助!接下來,請跟著小編一起來學習吧!

插入?yún)^(qū)間

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ū)間插入到對應的位置即可,重疊的情況比較復雜,有時候會有多個重疊,需要更新新區(qū)間的范圍以便包含所有重疊,之后將新區(qū)間加入結果 res,最后將后面的區(qū)間再加入結果 res 即可。具體思路是,用一個變量 cur 來遍歷區(qū)間,如果當前 cur 區(qū)間的結束位置小于要插入的區(qū)間的起始位置的話,說明沒有重疊,則將 cur 區(qū)間加入結果 res 中,然后 cur 自增1。直到有 cur 越界或有重疊 while 循環(huán)退出,然后再用一個 while 循環(huán)處理所有重疊的區(qū)間,每次用取兩個區(qū)間起始位置的較小值,和結束位置的較大值來更新要插入的區(qū)間,然后 cur 自增1。直到 cur 越界或者沒有重疊時 while 循環(huán)退出。之后將更新好的新區(qū)間加入結果 res,然后將 cur 之后的區(qū)間再加入結果 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)結束后就只需要插入新區(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;
    }
};

到此,關于“C++如何插入?yún)^(qū)間”的學習就結束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習,快去試試吧!若想繼續(xù)學習更多相關知識,請繼續(xù)關注億速云網(wǎng)站,小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>

向AI問一下細節(jié)

免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內容。

c++
AI