LeetCode 751. IP 到 CIDR

2023-12-17 HGNULB 约 12 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 751. IP 到 CIDR

题意分析

给一个起始 IPv4 地址 ip 和一个正整数 n，要求用尽可能少的 CIDR 块，恰好覆盖从 ip 开始的连续 n 个 IP 地址，一个不多一个不少。CIDR 块写成 a.b.c.d/k 的形式，它表示「前 k 位固定、后 $32 - k$ 位任意」的一整段地址，因此一个块恰好包含 $2^{32-k}$ 个连续地址。

这个定义里藏着两条硬约束，它们决定了整道题的形状。第一，块的大小必须是 $2$ 的幂——不存在覆盖 $3$ 个地址的 CIDR 块。第二，块的起始地址必须按块大小对齐：一个大小为 $2^t$ 的块，其起点的低 $t$ 位必须全是 $0$，否则「前 $32-t$ 位固定」这个描述就框不住这段地址。这两条合起来意味着我们不能随便切，切法受到起点二进制形态的强约束。

题目要求「块数最少」，且不允许覆盖超出 n 个的额外地址。这就排除了「直接找一个足够大的块把 n 个地址包进去」的偷懒解法。

另一个信号是：IPv4 是 $32$ 位，最大地址是 $2^{32} - 1$，超过 int 的正数范围。所以内部表示必须用 $64$ 位整数（Java 的 long、Go 的 int64），否则在 255.255.255.255 附近会溢出成负数。

边界上要覆盖：起点是 0.0.0.0（低位全零，start & -start 会得到 $0$，需要特判）；n = 1（每块只能是 /32）；起点已经高度对齐但 n 很小（块要被 n 反向压缩）；n 恰好是 $2$ 的幂且起点对齐（一块就够）；跨越 x.x.x.255 到 x.x.(x+1).0 的进位。题目保证不会越过 $2^{32}$ 的边界，所以不用担心地址回绕。

解法：贪心分块

核心思路

先想一个最朴素的做法：把 n 个地址一个一个地输出成 /32 块。这显然满足「恰好覆盖」，但块数是 n，远不是最少。

再想一个稍聪明的做法：把 n 二进制分解，比如 n = 5 = 4 + 1，就切成一个 $4$ 大小的块和一个 $1$ 大小的块。问题在于——大小为 $4$ 的块要求起点低两位为 $0$，如果起点是 255.0.0.7（低三位是 111），这个块根本不合法。所以瓶颈在于：块大小不仅受 n 限制，还受起点对齐程度限制，两者必须同时满足。

关键观察：在任意时刻，以当前 start 为起点能开出的最大合法块，其大小由两个上界共同决定。上界一是对齐上界：start 的二进制里最低位的那个 $1$ 所代表的权值，即 lowbit = start & -start——因为大小为 $2^t$ 的块要求 start 的低 $t$ 位全零，所以 $t$ 最多等于 start 末尾连续零的个数，对应的块大小恰好就是 lowbit。上界二是剩余量上界：块不能超过还没覆盖的地址数 n，否则会多覆盖。取两者的较小值，就是这一步能开的最大块。

为什么贪心地每次都取最大块是最优的？因为每个 CIDR 块的大小都是 $2$ 的幂，且必须对齐。假设某一步不取最大块而取了一个更小的 $2^{t'}$（$t' < t$），那么覆盖完这一小块之后新的起点 start + 2^{t'} 的末尾零个数恰好变成 $t'$，后续能开的块只会更小或相等，总块数不可能减少。换句话说，取最大块不会让后续变差，这就是交换论证意义下的贪心正确性。

于是维护的不变量是：每一轮循环开始时，start 是「还未被覆盖的第一个地址」，n 是「还需覆盖的地址个数」，且已输出的所有块恰好无缝无重地覆盖了从原始起点到 start - 1 的全部地址。每轮取 size = min(lowbit(start), 最大不超过 n 的 2 的幂)，输出对应块后令 start += size、n -= size，不变量得以保持；n 降到 $0$ 时循环结束，覆盖恰好完成。

把块大小换算成前缀长度也很直接：块大小为 $2^t$ 对应前缀 k = 32 - t，而 $t$ 就是 size 的末尾零个数，用 numberOfTrailingZeros 一步得到。

两个实现细节值得单独点明。其一，start == 0 时 start & -start 结果是 $0$，代表「任意对齐都可以」，此时把 lowbit 置成 $2^{32}$（超过任何合法 n 的上界），交给后面的收缩循环去压到不超过 n 即可，不需要写第二套分支。其二，「压到不超过 n」用 while (lowbit > n) lowbit >>= 1 反复右移，而不是去算 n 的最高位——右移写法既处理了 lowbit 过大的情况，又天然保证结果仍是 $2$ 的幂，代码只有一行。

解题步骤

写 ipToLong：按 . 切成四段，用 num = num * 256 + part 依次拼成一个 $64$ 位整数。理由：把点分十进制转成单一整数后，「连续的 n 个地址」就等价于「连续的 n 个整数」，所有对齐判断都能用位运算表达；用 long 而不是 int 是因为 $2^{32}-1$ 超出 int 正数范围，且 start += size 之后可能触及 $2^{32}$。

写 longToIp：依次右移 $24$、$16$、$8$、$0$ 位后与 $255$ 相与，拼成四段。理由：与 $255$ 相与能截出恰好一个字节，避免高位残留污染。

主循环条件是 n > 0。理由：n 表示尚未覆盖的地址数，它归零即代表任务完成，比用块数或起点做条件都更直接。

每轮先算 long lowbit = start & -start。理由：这是取最低位 $1$ 的标准写法，它的值恰好等于「start 能对齐的最大块大小」；补码下 -start 是按位取反加一，与原数相与只留最低位的 $1$。

若 lowbit == 0 则置为 1L << 32。理由：只有 start == 0 时低位全零，此时对齐没有任何限制；给一个大于任何合法 n 的哨兵值，让后面的收缩循环统一处理，避免写额外分支。注意必须写 1L 而不是 1，否则 int 左移 $32$ 位在 Java 里等于左移 $0$ 位，结果是 $1$。

用 while (lowbit > n) lowbit >>= 1 把块压到不超过剩余量。理由：右移一位就是块大小减半，始终保持 $2$ 的幂；由于 n >= 1，循环必然在 lowbit 降到 $1$ 之前停止，不会死循环。

计算 prefix = 32 - numberOfTrailingZeros(lowbit)，把 longToIp(start) + "/" + prefix 加入结果。理由：块大小 $2^t$ 与前缀长度 $32 - t$ 一一对应，而 $t$ 就是末尾零的个数；这一步是「大小」到「CIDR 记法」的翻译。

执行 start += lowbit、n -= lowbit 后进入下一轮。理由：这两句同步推进不变量的两半——起点跳到刚覆盖区间之后，剩余量扣掉刚覆盖的数量；两者必须用同一个 lowbit，任何一边用错值都会导致漏覆盖或重复覆盖。

以 ip = "255.0.0.7"、n = 10 走一遍。转成整数 start = 255 * 2^{24} + 7 = 4278190087，二进制末尾是 ...0111。第一轮：lowbit = start & -start = 1（末尾是 $1$，完全不对齐），$1 \le 10$ 不需收缩，prefix = 32 - 0 = 32，输出 255.0.0.7/32；start 变 4278190088（即 255.0.0.8），n 变 $9$。第二轮：start 末尾三位是 000，lowbit = 8，$8 \le 9$，prefix = 32 - 3 = 29，输出 255.0.0.8/29（覆盖 .8 到 .15 共 $8$ 个）；start 变 255.0.0.16，n 变 $1$。第三轮：start 末尾四位是 0000，lowbit = 16，但 $16 > 1$，收缩循环把它右移四次降到 $1$，prefix = 32，输出 255.0.0.16/32；n 变 $0$，循环结束。结果是 ["255.0.0.7/32", "255.0.0.8/29", "255.0.0.16/32"]，三块共覆盖 $1 + 8 + 1 = 10$ 个地址，与期望一致——注意第一轮被对齐卡住只能取 $1$，第三轮被剩余量卡住也只能取 $1$，两个上界各生效了一次。

代码实现

class Solution {
    public List<String> ipToCIDR(String ip, int n) {
        List<String> res = new ArrayList<>();
        long start = ipToLong(ip);

        while (n > 0) {
            long lowbit = start & -start;
            if (lowbit == 0) {
                lowbit = 1L << 32;
            }

            while (lowbit > n) {
                lowbit >>= 1;
            }

            int prefix = 32 - Long.numberOfTrailingZeros(lowbit);
            res.add(longToIp(start) + "/" + prefix);
            start += lowbit;
            n -= (int) lowbit;
        }

        return res;
    }

    private long ipToLong(String ip) {
        String[] parts = ip.split("\\.");
        long num = 0;
        for (String part : parts) {
            num = num * 256 + Integer.parseInt(part);
        }
        return num;
    }

    private String longToIp(long num) {
        return ((num >> 24) & 255) + "." + ((num >> 16) & 255) + "." + ((num >> 8) & 255) + "." + (num & 255);
    }
}

func ipToCIDR(ip string, n int) []string {
    res := make([]string, 0)
    start := ipToLong(ip)

    for n > 0 {
        lowbit := start & -start
        if lowbit == 0 {
            lowbit = 1 << 32
        }

        for lowbit > int64(n) {
            lowbit >>= 1
        }

        prefix := 32 - bits.TrailingZeros64(uint64(lowbit))
        res = append(res, longToIp(start)+"/"+itoa(prefix))
        start += lowbit
        n -= int(lowbit)
    }

    return res
}

func ipToLong(ip string) int64 {
    parts := strings.Split(ip, ".")
    var num int64
    for _, part := range parts {
        val, _ := strconv.Atoi(part)
        num = num*256 + int64(val)
    }
    return num
}

func longToIp(num int64) string {
    return itoa(int(num>>24&255)) + "." + itoa(int(num>>16&255)) + "." + itoa(int(num>>8&255)) + "." + itoa(int(num&255))
}

func itoa(v int) string {
    if v == 0 {
        return "0"
    }

    buf := make([]byte, 0, 3)
    for v > 0 {
        buf = append(buf, byte('0'+v%10))
        v /= 10
    }

    for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 {
        buf[i], buf[j] = buf[j], buf[i]
    }

    return string(buf)
}

复杂度分析

时间复杂度：$O(k \cdot 32)$，其中 $k$ 是输出的块数。每轮循环内部的 lowbit 计算和前缀换算都是常数时间，只有收缩循环最多右移 $32$ 次；而块数 $k$ 本身是 $O(\log n)$ 级别——因为每次要么被对齐卡住（此后起点的对齐度严格提升），要么被剩余量卡住（此后剩余量至少减半），两类情形各自最多发生约 $32$ 次，所以 $k \le 64$。整体可视为常数级的小循环。

空间复杂度：$O(k)$，只有结果列表随块数增长，其余变量都是标量；字符串转换过程中产生的临时对象也是常数个。

关键点总结

遇到「必须按 $2$ 的幂对齐切分」的问题，先把对象转成整数，然后用 x & -x 提取最低位 $1$——它的物理含义正是「这个位置最大能对齐多大的块」。这个技巧在内存分配器的伙伴系统、树状数组的区间跳跃、位图分段里是同一件事。

贪心的正确性要用「取最大不会让后续变差」来论证，而不是凭直觉。本题的论证核心是：少取一步会让新起点的对齐度反而降低，后续块只会更碎，所以贪心不劣。面试时能说出这一句，比写对代码更重要。

当一个量同时受多个上界约束时，写成「先取其中一个上界，再逐步收缩到满足其余上界」往往比一次性算出最小值更简洁。本题的 lowbit 先按对齐取值、再用 while 压到不超过 n，两个约束用两行代码分别表达，互不纠缠。

IPv4 必须用 $64$ 位整数承载。$2^{32}-1$ 超出 int 正数范围，且哨兵值 1L << 32 也需要 long；这类「位宽刚好差一位」的坑在网络、时间戳、哈希题里反复出现。

0 的 lowbit 是 $0$，必须特判。凡是用 x & -x 的代码都要先问一句「x 可能为 0 吗」，本题的 0.0.0.0 就是专门用来卡这一点的。

面试视角：字节和网易考这题看的是能否把网络协议的规则准确翻译成位运算。理想的作答顺序是先解释 CIDR 块「大小是 2 的幂 + 起点必须对齐」这两条约束，再指出「每步取 min(对齐上界, 剩余量上界)」，最后才写代码。写完主动举 255.0.0.7 这种低位不齐的用例走一遍，能证明你理解了对齐约束而不是死记 lowbit 模板。

易错点总结

错误写法：用 int 存 IP 整数 → 用例 ip = "255.255.255.255"，n = 1 → 转换结果 $4294967295$ 溢出成 $-1$，start & -start 得到 $1$ 虽然侥幸对，但 longToIp 里右移会做符号扩展，输出变成负数段；必须用 long / int64。

错误写法：lowbit == 0 时不特判 → 用例 ip = "0.0.0.0"，n = 5 → lowbit 恒为 $0$，收缩循环 while (0 > 5) 不执行，prefix 算成 $32 - 64$ 之类的非法值，且 start += 0、n -= 0 导致死循环。

错误写法：哨兵写成 lowbit = 1 << 32（Java 中 int 字面量）→ 用例 ip = "0.0.0.0"，n = 5 → Java 对 int 移位只取低 $5$ 位，1 << 32 等于 $1$，块被限制成 $1$，输出 $5$ 个 /32 块而不是最优的 0.0.0.0/30 加 0.0.0.4/32，块数不是最少。

错误写法：只按 n 的二进制分解切块，不考虑起点对齐 → 用例 ip = "255.0.0.7"，n = 10 → 会输出 255.0.0.7/28 这样的块，但 .7 的低四位不是 $0$，该 CIDR 实际覆盖的是 .0 到 .15，越界覆盖了起点之前的地址，结果非法。

错误写法：只按起点对齐取块，不用 n 收缩 → 用例 ip = "255.0.0.8"，n = 1 → lowbit = 8，直接输出 255.0.0.8/29 覆盖了 $8$ 个地址，比要求的 $1$ 个多覆盖 $7$ 个，答案错误。

错误写法：收缩用 lowbit = Math.min(lowbit, n) 而不是右移 → 用例 n = 5，lowbit = 8 → 得到 lowbit = 5，但 $5$ 不是 $2$ 的幂，numberOfTrailingZeros(5) = 0，prefix 算成 $32$，输出的块只覆盖 $1$ 个地址却把 n 减了 $5$，覆盖出现缺口。

错误写法：前缀写成 prefix = numberOfTrailingZeros(lowbit) 而漏掉 32 - → 用例块大小 $8$ → 输出 /3 而不是 /29，/3 代表 $2^{29}$ 个地址，覆盖范围严重超标。

错误写法：更新时写成 start += lowbit 但 n-- → 用例 ip = "255.0.0.8"，n = 8 → 起点一次跳 $8$ 个但计数只减 $1$，循环要跑 $8$ 轮，输出 $8$ 个块且总覆盖范围远超 $8$ 个地址。

错误写法：longToIp 里忘记与 $255$ 相与，直接写 num >> 24 等 → 用例 ip = "1.2.3.4" → 第二段算成 num >> 16 的完整值（含最高字节），得到 $258$ 这样的非法段值。

错误写法：ipToLong 用 split(".") 而不是 split("\\.") → 用例任意 IP → Java 的 split 接收正则，. 匹配任意字符，切出全是空串的数组，解析直接抛异常。

相似题目

题目	难度	考察点
201. 数字范围按位与	中等	同样围绕「区间与二进制前缀的关系」，求的是公共前缀而非切分区间
231. 2 的幂	简单	`x & -x == x` 的最小应用，是理解 lowbit 语义的入门题
93. 复原 IP 地址	中等	同为 IP 格式处理，但考点是回溯枚举分段位置与前导零校验
468. 验证IP地址	中等	纯字符串校验，要同时处理 IPv4 与 IPv6 的格式规则，无位运算
190. 颠倒二进制位	简单	同样在 $32$ 位无符号语义下操作，考察 Java 中有符号右移带来的陷阱