LeetCode 751. IP 到 CIDR
题目描述
题意分析
把 IPv4 地址看成一个 32 位无符号整数，要求用尽量少的 CIDR 块恰好覆盖
[ip, ip + n - 1]，其中包含起始地址本身，不能多覆盖范围外的地址。前缀长度为
p的 CIDR 块固定高p位，低32 - p位可以任意变化，因此包含 $2^{32-p}$ 个连续地址。若把这一块写成从最小地址开始的形式，它的起点还必须是块大小的整数倍，这就是对齐要求。
解法：贪心分块
核心思路
[!blue]
用
start表示第一个尚未覆盖的地址，n表示还需覆盖的数量。IPv4 的四段相当于四位 256 进制数，逐段执行num = num * 256 + part即可转成整数；在整数上加块大小，也就自然处理了地址低位向高位的进位。若
start的二进制末尾有t个零，它能对齐的最大块是 $2^t$，由start & -start直接得到。更大的块会要求更多低位为零，从而把块的实际起点移到start之前，覆盖不需要的地址。start == 0时所有低位都为零，但位运算结果也是零，需单独把对齐上界设为完整地址空间大小 $2^{32}$。对齐只是一个限制，块还不能超过剩余的
n个地址。将对齐上界不断除以2，直到不大于n，就得到当前能取的最大合法块。这个缩小过程始终保持块大小为二的幂，不能直接用min(lowbit, n)代替。贪心成立依赖 CIDR 区间的对齐结构：任意两个这样的二幂区间，要么互不相交，要么一个完全包含另一个，不会只交叠一部分。设当前最大合法前缀块为
B，任何合法覆盖中与它相交的块都只能在B内部；否则就会有一个包含B的更大合法前缀块，与B的最大性矛盾。把覆盖B的所有小块替换成B，不会增加块数，也不会影响后面的覆盖。因此，总存在一个最优方案先取B，余下部分继续使用同一规则即可。块大小为 $2^t$ 时，输出的前缀长度是
32 - t。记录这一块后，将start增加块大小、n减少相同数量。已输出部分与剩余部分恰好首尾相接，既没有缺口也没有重复；每轮至少覆盖一个地址，n == 0时结束。
解题步骤
- 将地址转为宽整数。
- 计算对齐上界，按剩余数量缩成二幂块。
- 块大小二的 t 次方对应前缀长度32−t。
- 同步前移起点并扣除覆盖数量。
地址可能超过有符号 32 位整数上限，因此 Java 用
long、Go 用int64保存地址和对齐块。题目保证所有待覆盖地址都在 IPv4 范围内；处理最后一个地址后，start即使暂时到达 $2^{32}$，此时剩余数量也已归零，不会再输出它。块大小为1时前缀自然为32，适用于无法合并的单个地址。
代码实现
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);
}
}
import (
"math/bits"
"strconv"
"strings"
)
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(B\cdot32)$，B 为输出块数，整数位宽固定。
- 空间复杂度：输出 $O(B)$，其余辅助空间 $O(1)$。
关键点总结
[!green]
- 对齐与剩余数量两个上界都要满足，块大小仍须是二的幂。
- 起点零的 lowbit 为零，必须单独转换为对齐上界。
易错点总结
[!yellow]
- 直接取 lowbit 与 n 的较小数，可能得到非二幂块。
- 只考虑对齐，会覆盖超过所需的地址。
- 起点与剩余数量使用不同步长更新，会产生缺口或重复覆盖。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 补充题 22. IP 地址与整数的转换 | 中等 | 先把IPv4转为整数，才能按二进制对齐边界划分连续地址区间。 |
| 201. 数字范围按位与 | 中等 | CIDR前缀表示高位固定的地址块，按位与同样利用区间公共高位。 |