合并重叠和连续IP区间 - 华为机试真题题解(100分)

考试平台： 时习知

题目类型： 3 道编程题 （100分 + 200分 + 300分）

题目描述

给定多个IP区间，其中每个区间表示为[start_ip, end_ip]，请合并所有重叠和连续的IP区间，并返回一个IP区间顺序集合。区间顺序要求按照start_ip从小到大升序排序。

输入

第一行为区间个数N，其值为[1,100] 。

接下来输入N个IP地址区间，每个区间的格式为[start_ip,end_ip]，其中start_ip和end_ip为合法的IPv4地址点分十进制格式，即A.B.C.D，其中A、B、C和D的取值范围为[0,255] 。IP地址大小的比较，是按照A、B、C和D的顺序进行比较。

输出

输出合并且排序好的M个区间，每个区间的格式为[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]

解释： 
区间 [192.168.1.1,192.168.1.3] 和区间 [192.168.1.2,192.168.1.3] 重叠部分是 [192.168.1.2,192.168.1.3]，因此可合并为 [192.168.1.1,192.168.1.3]。
区间 [192.168.1.3] 与 [192.168.1.4,192.168.1.5] 为连续区间，因此可以合并为 [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]

解释： 
区间 [192.168.1.2,192.168.1.7] 和区间 [192.168.1.5,192.168.1.8] 的重叠部分是 [192.168.1.5,192.168.1.7]，因此可合并为 [192.168.1.2,192.168.1.8]，而区间 [192.168.1.2,192.168.1.3] ，1.5,1.2,1.8] 既不重叠，也不连续。

题解

题目类型

此题属于 构造类型的问题。主要是通过按某些条件排序区间并进行合并，适用于可以逐步构建最优解的场景。

解题思路

1. IP 地址转换为整数：
   • 首先，题目中给定的 IP 地址是以点分十进制表示的（如 192.168.1.1）。为了便于比较和处理，我们可以将每个 IP 地址转换为一个 32 位的整数。这样做是为了简化比较和区间的合并操作，因为整数的比较操作比 IP 字符串更为高效。
   • 将 A.B.C.D 转换为整数的方法是：A * 256^3 + B * 256^2 + C * 256 + D。
2. 排序：
   • 首先，将所有的 IP 区间按 start_ip 从小到大排序。这一步是保证合并区间时能够逐个比较并合并相邻或重叠的区间。
3. 合并区间：
   • 遍历排序后的区间，逐一比较当前区间的起始 IP 和上一个合并区间的结束 IP。
   • 如果当前区间的起始 IP 大于上一个区间的结束 IP，说明没有重叠或连续，可以将当前区间直接加入结果。
   • 如果当前区间与上一个区间重叠或连续（即 start_ip <= end_ip + 1），则合并两个区间，将结束 IP 更新为两个区间中更大的那个。
4. 将整数转换回 IP 地址：
   • 合并完成后，所有的区间都是以整数形式存储的，最后需要将它们转换回 IP 格式的字符串。

C++

[代码仅供学习参考并未进行大量数据测试]

#include <bits/stdc++.h>

using namespace std;

// 将A.B.C.D格式 IP 地址转成 int 数字
unsigned int ip_to_int(const string &ip) {
    int ipnum = 0;
    stringstream ss(ip);
    string num;
    while (getline(ss, num, '.')) {  // 按'.'分割IP地址
        ipnum = (ipnum << 8) | stoi(num);
    }

    return ipnum;
}

// 将int类型的ip转成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));
    }

    // 按区间起始值升序排序
    sort(ip_intervals.begin(), ip_intervals.end());

    // 存储合并后的结果区间
    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);
        }
    }

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

    cout << endl;
    return 0;
}

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏