算法leetcode

【减治难题】力扣751-IP到CIDR

字数统计: 1.6k字   |   阅读时长: 7分
, ,

摘要: 减治法，模拟难题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个困哪的模拟题，直接按照要求实现功能即可，难点在于对问题的拆解带有一些减治的思想、以及位运算的一些细节。

$1 题目

给定一个起始 IP 地址 ip 和一个我们需要包含的 IP 的数量 n，返回用列表（最小可能的长度）表示的 CIDR块的范围。

CIDR 块是包含 IP 的字符串，后接斜杠和固定长度。例如：“123.45.67.89/20”。固定长度 “20” 表示在特定的范围中公共前缀位的长度。

注：

1
2
3
ip 是有效的 IPv4 地址。
每一个隐含地址 ip + x (其中 x < n) 都是有效的 IPv4 地址。
n 为整数，范围为 [1, 1000]。

示例 1：

输入：ip = “255.0.0.7”, n = 10
输出：[“255.0.0.7/32”,”255.0.0.8/29”,”255.0.0.16/32”]
解释：
转换为二进制时，初始IP地址如下所示（为清晰起见添加了空格）：
255.0.0.7 -> 11111111 00000000 00000000 00000111
地址 “255.0.0.7/32” 表示与给定地址有相同的 32 位前缀的所有地址，
在这里只有这一个地址。

地址 “255.0.0.8/29” 表示与给定地址有相同的 29 位前缀的所有地址：
255.0.0.8 -> 11111111 00000000 00000000 00001000
有相同的 29 位前缀的地址如下：
11111111 00000000 00000000 00001000
11111111 00000000 00000000 00001001
11111111 00000000 00000000 00001010
11111111 00000000 00000000 00001011
11111111 00000000 00000000 00001100
11111111 00000000 00000000 00001101
11111111 00000000 00000000 00001110
11111111 00000000 00000000 00001111

地址 “255.0.0.16/32” 表示与给定地址有相同的 32 位前缀的所有地址，
这里只有 11111111 00000000 00000000 00010000。

总之，答案指定了从 255.0.0.7 开始的 10 个 IP 的范围。

有一些其他的表示方法，例如：
[“255.0.0.7/32”,”255.0.0.8/30”, “255.0.0.12/30”, “255.0.0.16/32”],
但是我们的答案是最短可能的答案。

另外请注意以 “255.0.0.7/30” 开始的表示不正确，
因为其包括了 255.0.0.4 = 11111111 00000000 00000000 00000100 这样的地址，
超出了需要表示的范围。

$2 题解

算法: 模拟

本题的需求还是非常明确的，就是给一个起始的 IP 地址，以及数量 n。从起始 IP 地址向后依次取 IP，直至取到 n 个。然后用 CIDR 块的方式表示出这 n 个 IP 地址。

CIDR 块是基于 IP 地址的二进制表示的，因此整体的模拟过程如下：

  • 第 1 步: 需要首先将字符串形式的起始 IP 地址转换为二进制形式。
  • 第 2 步: 往后数 n 个，找到二进制形式的终止的 IP 地址。
  • 第 3 步: 在二进制形式下用 CIDR 规则分组。
  • 第 4 步: 对每个分组，转换回字符串形式，压入结果数组中。

下面我们依次来看。第 1 步就是实现一个函数 ip2uint，将字符串形式的 IP 地址转换为二进制形式，比较简单但是需要注意细节，见后面的代码：

1
ull ip2uint(const string& ip)

有了以上函数，第 1 步和第 2 步就可以直接解决了，如下：

1
2
ull start = ip2uint(ip);
ull end = start + n - 1;

第 3 步比较复杂，我们要把 [left, right] 这 n 个二进制形式的 IP 用 CIDR 规则表示出来，接口如下：

1
void solve(ull left, ull right, vector<string>& result)

以上函数表示将 [left, right] 这 n 个 IP 按 CIDR 规则分组后，将各组的字符串表示压入 result。

如果 left 大于 right，则不做任何操作直接返回。

如果 left 与 right 相等，则直接把 left 的字符串形式的后面加上 /32 返回即可。

下面看 left < right 的情况。

首先找到这 n 个数 [left, right] 的最大公共前缀长度 len = common_prefix_len(left, right)。

left/len 表示的是与 left 有相同的 len 位前缀的所有地址，这个范围记为 [L, R]，通过以下函数得到：

1
void get_LR(ull x, int l, ull& L, ull& R)

[L, R] 的范围是有可能大于 [left, right] 的，也就是 L <= left、right <= R。

如果 left == L 且 R == right，那么将 left/len 压入 result 返回即可。

否则，left/len 表示的 [L, R] 覆盖到了不在 [left, right] 之间的数，也就是范围大了，需要在更小的范围考虑问题，因此自然想到考察最大公共前缀为 len+1 的情况。

由于 [left, right] 的最大公共前缀长度为 len，因此 left 在第 len + 1 位为 0，right 在第 len + 1 位为 1。

调用 get_LR(left, len + 1, L, R) 得到与 left 有相同的 len + 1 位前缀的所有地址的范围 [L, R]

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
using ull = unsigned long long;

class Solution {
public:
    vector<string> ipToCIDR(string ip, int n) {
        // 1 <= n < = 1000
        ull start = ip2uint(ip);
        ull end = start + n - 1;
        vector<string> result;
        solve(start, end, result);
        return result;
    }

private:
    void solve(ull left, ull right, vector<string>& result)
    {
        if(left > right) return;
        if(left == right)
        {
            string part = uint2ip(left);
            part += '/' + to_string(32);
            result.push_back(part);
            return;
        }
        // left < right
        int len = common_prefix_len(left, right);
        // len ... 31 逐个尝试(32的话，前面 left == right 那步特判就返回了)
        ull L = 0, R = 0;
        get_LR(left, len, L, R);
        // L<=left   right>=R
        if(left == L && R == right)
        {
            string part = uint2ip(L);
            part += '/' + to_string(len);
            result.push_back(part);
            return;
        }
        // L > left 或 right < R
        get_LR(left, len + 1, L, R);
        ull l = (L | (1 << (32 - (len + 1))));
        ull r = (R & (~(1 << (32 - (len + 1)))));
        solve(left, r, result);
        solve(l, right, result);
    }

    void get_LR(ull x, int l, ull& L, ull& R)
    {
        L = x, R = x;
        L &= ~((1 << (32 - l)) - 1);
        R |= ((1 << (32 - l)) - 1);
    }

    string uint2ip(ull x)
    {
        string ans;
        ull mask = pow(2, 8) - 1;
        for(int i = 3; i >= 0; --i)
        {
            // 8 * i
            ull part = (x >> (8 * i)) & mask;
            ans += to_string(part) + '.';
        }
        ans.pop_back();
        return ans;
    }

    ull ip2uint(const string& ip)
    {
        int n = ip.size();
        ull ans = 0;
        int i = 0;
        while(i < n)
        {
            int j = i;
            while(j < n && ip[j] != '.')
                ++j;
            ull k;
            stringstream ss;
            ss << ip.substr(i, j - i);
            ss >> k;
            ans <<= 8;
            ans += k;
            i = j + 1;
        }
        return ans;
    }

    int common_prefix_len(ull x, ull y)
    {
        // x < y
        int i = 31;
        while(i >= 0 && ((x >> i) & 1) == ((y >> i) & 1))
            --i;
        int len = 32 - i - 1;
        return len;
    }
};
Share