难度: Medium
Submission
运行时间: 31 ms
内存: 16.0 MB
class Solution:
def ipToCIDR(self, ip: str, n: int) -> List[str]:
ipStart =list(map(int, ip.split('.')))
intIPStart = ipStart[0]*(1<<24) + ipStart[1]*(1<<16) + ipStart[2]*(1<<8)+ipStart[3]
intIPEnd = intIPStart+n-1
ans=list()
while intIPStart<=intIPEnd:
strIPStart = bin(intIPStart)
strIPStart = '0'*(34-len(strIPStart)) + strIPStart[2:]
cnt0=0 #for start
for i in range(len(strIPStart)-1, -1, -1):
if strIPStart[i] == '1':
break
cnt0+=1
k=cnt0
while k>0:
if intIPStart | int('1'*k, base=2)<=intIPEnd:
break
k-=1
curCIDR=str(int(strIPStart[0:8], base=2))
for i in range(1,4):
curCIDR += ('.' + str(int(strIPStart[8*i:8*(i+1)], base=2)))
curCIDR += ('/' + str(32-k))
ans.append(curCIDR)
if k==0:
intIPStart += 1
else:
intIPStart = (intIPStart | int('1'*k, base=2))+1
return ans
Explain
这道题目要求将IP地址转换为CIDR表示法，覆盖给定数量的IP地址。题解的思路是首先将IP地址转换为整数形式，然后根据给定的数量计算出范围内的IP地址，并逐个将它们转换回CIDR表示法。在转换过程中，需要注意的是计算出最大可能的子网掩码位数，以覆盖尽可能多的IP地址。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def ipToCIDR(self, ip: str, n: int) -> List[str]:
# 将IP地址转换为整数
ipStart = list(map(int, ip.split('.')))
intIPStart = ipStart[0]*(1<<24) + ipStart[1]*(1<<16) + ipStart[2]*(1<<8) + ipStart[3]
intIPEnd = intIPStart + n - 1
ans = list()
# 遍历IP地址范围，逐个转换为CIDR表示法
while intIPStart <= intIPEnd:
# 将整数形式的IP地址转换为二进制字符串
strIPStart = bin(intIPStart)
strIPStart = '0'*(34-len(strIPStart)) + strIPStart[2:]
cnt0 = 0 # 计算末尾连续0的个数，即子网掩码位数
for i in range(len(strIPStart)-1, -1, -1):
if strIPStart[i] == '1':
break
cnt0 += 1
k = cnt0
# 确定最大可能的子网掩码位数
while k > 0:
if intIPStart | int('1'*k, base=2) <= intIPEnd:
break
k -= 1
# 转换为CIDR表示法
curCIDR = str(int(strIPStart[0:8], base=2))
for i in range(1, 4):
curCIDR += ('.' + str(int(strIPStart[8*i:8*(i+1)], base=2)))
curCIDR += ('/' + str(32-k))
ans.append(curCIDR)
# 更新IP地址范围
if k == 0:
intIPStart += 1
else:
intIPStart = (intIPStart | int('1'*k, base=2)) + 1
return ans
Explore
在将IP地址转换为整数形式时，首先将IP地址按点分隔成四个部分，每部分代表一个8位的二进制数。这四个部分分别对应IP地址的四个字节。将这四个部分转换为整数后，通过位运算将它们组合成一个32位的整数。具体操作为：第一部分乘以2的24次方（即左移24位），第二部分乘以2的16次方（即左移16位），第三部分乘以2的8次方（即左移8位），第四部分保持不变。这样，第一部分在最高的8位，第二部分在接下来的8位，依此类推，组成了一个完整的32位整数。这个整数的二进制表示就是原IP地址的直接表达形式。
CIDR（无类别域间路由）表示法中，子网掩码表示为斜杠后的数字，这个数字表示网络地址中固定不变的位数。在计算子网掩码时，末尾连续0的个数表示当前可用于分配的IP地址范围的位数，这些0可以变化以形成新的IP地址。从末尾连续0的个数开始计算是为了确定在当前IP地址后可以连续分配的最大IP地址数量。例如，如果末尾有3个连续的0，则可以表示8个（2^3）连续的IP地址。这种计算方式直接关联到CIDR的网络和主机部分的划分，其中网络部分由1的位表示，主机部分由0的位表示。
这个条件使用的是位或运算来确定所选子网掩码是否可以覆盖要求的IP地址范围。`int('1'*k, base=2)`生成一个数，其二进制表示中末尾有k个1，其余位都是0。当这个数与intIPStart进行位或运算时，它实际上是将intIPStart的末尾k个位设置为1，这代表了当前子网掩码下，intIPStart可以表示的最大IP地址。如果这个结果小于或等于intIPEnd，那么说明当前的子网掩码可以包括从intIPStart到intIPEnd的所有IP地址。这个操作保证了所选子网掩码的有效性，确保它能覆盖指定的IP地址范围。
这条更新语句的目的是将当前范围的起始IP地址更新为下一个子网的起始地址。`intIPStart | int('1'*k, base=2)`的操作将intIPStart的末尾k位设置为1，这表示当前子网可以包含的最大IP地址。通过在这个结果后加1，将IP地址更新到下一个可能的子网的起始地址。这样做的特定优势在于能够快速跳过当前已经计算和分配的CIDR块，直接移动到下一个需要计算的IP地址段，提高了算法的效率和执行速度。通过这种方式，我们可以保证每次循环处理的都是一个新的子网范围，避免了重复处理或IP地址的遗漏。