class Solution {
public:
vector<string> ipToCIDR(string ip, int n) {
}
};
751. IP 到 CIDR
IP地址 是一个格式化的 32位 无符号整数，每组 8位 被打印为一个十进制数字和，点字符 '.' 起到了分组的作用。
00001111 10001000 11111111 01101011 ( 为清晰起见增加了空格)被格式化为IP地址将是 “15.136.255.107” 。CIDR块 是一种用来表示一组特定IP地址的格式。字符串形式，由基础IP地址、斜杠和前缀长度 k 组成。它所覆盖的地址是所有IP地址的 前 k 位 与基础IP地址相同的IP地址。
“123.45.67.89/20” 是一个前缀长度为 20 的 CIDR块。任何二进制表示形式匹配 01111011 00101101 0100xxxx xxxxxxxx 的IP地址，其中 x 可以是 0 或 1 ，都在CIDR块覆盖的集合中。给你一个起始IP地址 ip 和我们需要覆盖的IP地址数量 n 。你的目标是使用 尽可能少的CIDR块 来 覆盖范围 [ip, ip + n - 1] 内的所有IP地址 。不应该覆盖范围之外的其他IP地址。
返回 包含IP地址范围的 CIDR块 的 最短 列表。如果有多个答案，返回其中 任何 一个 。
示例 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.8 -> 11111111 00000000 00000000 00001000 - 255.0.0.9 -> 11111111 00000000 00000000 00001001 - 255.0.0.10 -> 11111111 00000000 00000000 00001010 - 255.0.0.11 -> 11111111 00000000 00000000 00001011 - 255.0.0.12 -> 11111111 00000000 00000000 00001100 - 255.0.0.13 -> 11111111 00000000 00000000 00001101 - 255.0.0.14 -> 11111111 00000000 00000000 00001110 - 255.0.0.15 -> 11111111 00000000 00000000 00001111 - 255.0.0.16 -> 11111111 00000000 00000000 00010000 CIDR区块“255.0.0.7/32”包含第一个地址。 CIDR区块255.0.0.8/29包含中间的8个地址(二进制格式为11111111 00000000 00000000 00001xxx)。 CIDR区块“255.0.0.16/32”包含最后一个地址。 请注意，虽然CIDR区块“255.0.0.0/28”覆盖了所有的地址，但它也包括范围之外的地址，所以我们不能使用它。
示例 2:
输入：ip = "117.145.102.62", n = 8 输出：["117.145.102.62/31","117.145.102.64/30","117.145.102.68/31"]
提示:
7 <= ip.length <= 15ip 是一个有效的 IPv4 ，形式为 "a.b.c.d" ，其中 a, b, c, d 是 [0, 255] 范围内的整数1 <= n <= 1000ip + x ( x < n) 都是有效的 IPv4 地址原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-10-22 10:36:51
func ipToInt(ip string) int {
ans := 0
for _, s := range strings.Split(ip, ".") {
x, _ := strconv.Atoi(s)
ans = 256*ans + x
}
return ans
}
func intToIP(x int) string{
ip:=""
for i := 24; i >=0; i-=8 {
ip+= strconv.Itoa((x >>i)%256)+"."
}
return ip[:len(ip)-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func bitLength(x int) int {
if x == 0 {
return 1
}
ans := 0
for x > 0 {
x >>= 1
ans++
}
return ans
}
func ipToCIDR(ip string, n int) []string {
start := ipToInt(ip)
var ans []string
for n > 0 {
mask := max(33-bitLength(start&-start), 33-bitLength(n))
if start==0{
mask = 33-bitLength(n)
}
ans = append(ans, intToIP(start)+"/"+strconv.Itoa(mask))
start += 1 << (32 - mask)
n -= 1 << (32 - mask)
}
return ans
}
python3 解法, 执行用时: 52 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-22 10:36:09
from math import log2
class Solution:
def ipToCIDR(self, ip: str, n: int) -> List[str]:
def ip_to_int(ip):
num = 0
for x in ip.split('.'):
num *= 256
num += int(x)
return num
def int_to_ip(num):
lst = []
for _ in range(4):
num, r = divmod(num, 256)
lst.append(str(r))
return '.'.join(lst[::-1])
def low_bit(num):
return num & (-num)
res = []
num = ip_to_int(ip)
while n:
count = low_bit(num) or 1024
while count > n:
count >>= 1
res.append(int_to_ip(num) + '/' + str(32 - int(log2(count))))
num += count
n -= count
return res
java 解法, 执行用时: 5 ms, 内存消耗: 40.6 MB, 提交时间: 2023-10-22 10:33:00
class Solution {
public List<String> ipToCIDR (String ip,int n){
int start = toInt(ip);//将ip转化为整数
List<String> ans = new ArrayList<>();
while (n > 0) {
int trailingZeros = Integer.numberOfTrailingZeros(start);
System.out.println(trailingZeros);
int mask = 0, bitsInCIDR = 1;
//计算mask
while (bitsInCIDR < n && mask < trailingZeros) {
bitsInCIDR <<= 1;
mask++;
}
if (bitsInCIDR > n) {
bitsInCIDR >>= 1;
mask--;
}
ans.add(toString(start, 32 - mask));
n -= bitsInCIDR;
start += (bitsInCIDR);
}
return ans;
}
private String toString(int number, int range) {
final int WORD_SIZE = 8;
StringBuilder buffer = new StringBuilder();
for (int i = 3; i >= 0; --i) {
buffer.append(((number >> (i * WORD_SIZE)) & 255));
buffer.append(".");
}
buffer.setLength(buffer.length() - 1);
buffer.append("/").append(range);
return buffer.toString();
}
private int toInt(String ip) {
String[] strs = ip.split("\\.");
int sum = 0;
for (String str : strs) {
sum *= 256;
sum += Integer.parseInt(str);
}
return sum;
}
}