考試平臺(tái)： 時(shí)習(xí)知

題目類型： 3 道編程題 （100分 + 200分 + 300分）

題目描述

給定多個(gè)IP區(qū)間，其中每個(gè)區(qū)間表示為[start_ip, end_ip]，請(qǐng)合并所有重疊和連續(xù)的IP區(qū)間，并返回一個(gè)IP區(qū)間順序集合。區(qū)間順序要求按照start_ip從小到大升序排序。

輸入

第一行為區(qū)間個(gè)數(shù)N，其值為[1,100] 。

接下來輸入N個(gè)IP地址區(qū)間，每個(gè)區(qū)間的格式為[start_ip,end_ip]，其中start_ip和end_ip為合法的IPv4地址點(diǎn)分十進(jìn)制格式，即A.B.C.D，其中A、B、C和D的取值范圍為[0,255] 。IP地址大小的比較，是按照A、B、C和D的順序進(jìn)行比較。

輸出

輸出合并且排序好的M個(gè)區(qū)間，每個(gè)區(qū)間的格式為[start_ip,end_ip]。

示例1

輸入：
3
[192.168.1.1,192.168.1.3]
[192.168.1.2,192.168.1.3]
[192.168.1.4,192.168.1.5]

輸出：
[192.168.1.1,192.168.1.5]

解釋： 
區(qū)間 [192.168.1.1,192.168.1.3] 和區(qū)間 [192.168.1.2,192.168.1.3] 重疊部分是 [192.168.1.2,192.168.1.3]，因此可合并為 [192.168.1.1,192.168.1.3]。
區(qū)間 [192.168.1.3] 與 [192.168.1.4,192.168.1.5] 為連續(xù)區(qū)間，因此可以合并為 [192.168.1.1,192.168.1.5]。

示例2

輸入：
3
[192.168.1.5,192.168.1.8]
[192.168.1.6,192.168.1.7]
[192.168.1.2,192.168.1.3]

輸出：
[192.168.1.2,192.168.1.3][192.168.1.5,192.168.1.8]

解釋： 
區(qū)間 [192.168.1.2,192.168.1.7] 和區(qū)間 [192.168.1.5,192.168.1.8] 的重疊部分是 [192.168.1.5,192.168.1.7]，因此可合并為 [192.168.1.2,192.168.1.8]，而區(qū)間 [192.168.1.2,192.168.1.3] ，1.5,1.2,1.8] 既不重疊，也不連續(xù)。

題解

題目類型

此題屬于 構(gòu)造類型的問題。主要是通過按某些條件排序區(qū)間并進(jìn)行合并，適用于可以逐步構(gòu)建最優(yōu)解的場(chǎng)景。

解題思路

1. IP 地址轉(zhuǎn)換為整數(shù)：
   • 首先，題目中給定的 IP 地址是以點(diǎn)分十進(jìn)制表示的（如 192.168.1.1）。為了便于比較和處理，我們可以將每個(gè) IP 地址轉(zhuǎn)換為一個(gè) 32 位的整數(shù)。這樣做是為了簡化比較和區(qū)間的合并操作，因?yàn)檎麛?shù)的比較操作比 IP 字符串更為高效。
   • 將 A.B.C.D 轉(zhuǎn)換為整數(shù)的方法是：A * 256^3 + B * 256^2 + C * 256 + D。
2. 排序：
   • 首先，將所有的 IP 區(qū)間按 start_ip 從小到大排序。這一步是保證合并區(qū)間時(shí)能夠逐個(gè)比較并合并相鄰或重疊的區(qū)間。
3. 合并區(qū)間：
   • 遍歷排序后的區(qū)間，逐一比較當(dāng)前區(qū)間的起始 IP 和上一個(gè)合并區(qū)間的結(jié)束 IP。
   • 如果當(dāng)前區(qū)間的起始 IP 大于上一個(gè)區(qū)間的結(jié)束 IP，說明沒有重疊或連續(xù)，可以將當(dāng)前區(qū)間直接加入結(jié)果。
   • 如果當(dāng)前區(qū)間與上一個(gè)區(qū)間重疊或連續(xù)（即 start_ip <= end_ip + 1），則合并兩個(gè)區(qū)間，將結(jié)束 IP 更新為兩個(gè)區(qū)間中更大的那個(gè)。
4. 將整數(shù)轉(zhuǎn)換回 IP 地址：
   • 合并完成后，所有的區(qū)間都是以整數(shù)形式存儲(chǔ)的，最后需要將它們轉(zhuǎn)換回 IP 格式的字符串。

C++

[代碼僅供學(xué)習(xí)參考并未進(jìn)行大量數(shù)據(jù)測(cè)試]

#include <bits/stdc++.h>

using namespace std;

// 將A.B.C.D格式 IP 地址轉(zhuǎn)成 int 數(shù)字
unsigned int ip_to_int(const string &ip) {
    int ipnum = 0;
    stringstream ss(ip);
    string num;
    while (getline(ss, num, '.')) {  // 按'.'分割I(lǐng)P地址
        ipnum = (ipnum << 8) | stoi(num);
    }

    return ipnum;
}

// 將int類型的ip轉(zhuǎn)成A.B.C.D格式的ip地址
string int_to_ip(unsigned int num) {
    return to_string((num >> 24) & 0xff) + "." +
           to_string((num >> 16) & 0xff) + "." +
           to_string((num >> 8) & 0xff) + "." +
           to_string(num & 0xff);
}

int main() {
    int n;
    cin >> n;
    cin.ignore();  // 忽略換行符

    vector<pair<unsigned int, unsigned int>> ip_intervals;
    for (int i = 0; i < n; ++i) {
        string line;
        getline(cin, line);
        size_t pos = line.find(',');
        string st = line.substr(1, pos);
        string ed = string(line.begin() + pos + 1, line.end() - 1);
        ip_intervals.emplace_back(ip_to_int(st), ip_to_int(ed));
    }

    // 按區(qū)間起始值升序排序
    sort(ip_intervals.begin(), ip_intervals.end());

    // 存儲(chǔ)合并后的結(jié)果區(qū)間
    vector<pair<unsigned int, unsigned int>> merge;
    for (auto &[start_ip, end_ip]: ip_intervals) {
        if (merge.empty() || merge.back().second + 1 < start_ip) {
            merge.emplace_back(start_ip, end_ip);
        } else {
            merge.back().second = max(merge.back().second, end_ip);
        }
    }

    // 輸出合并后的結(jié)果
    for (auto &[start_ip, end_ip]: merge) {
        cout << "[" + int_to_ip(start_ip) + "," + int_to_ip(end_ip) + "]";
    }

    cout << endl;
    return 0;
}

希望這個(gè)專欄能讓您熟練掌握算法, ?????? 立即訂閱。

整理題解不易， 如果有幫助到您，請(qǐng)給點(diǎn)個(gè)贊 ???? 和收藏 ?，讓更多的人看到。??????