算法leetcode

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

字数统计: 937字   |   阅读时长: 4分
,

摘要:

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

算法: 分治 + 位运算

代码(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);
        L |= (1 << (32 - (len + 1)));
        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