LeetCode 751. IP to CIDR

一点感慨

这道题真是让人印象深刻,我之前在面airbnb的时候遇到了。
要求把IP转换为CIDR表示
题目链接 https://leetcode.com/problems/ip-to-cidr/

题目意思

首先这个题目意思就不太好理解。
题目输入会给一个ip,以及一个n
比如 ip = “255.0.0.7”, n = 10
这个输入代表这个从 255.0.0.7 开始的10个ip
然后我们的算法给出的输出应该是 [“255.0.0.7/32”,”255.0.0.8/29”,”255.0.0.16/32”]
这个输出是一个数组,数组里面的每一个元素都是CIDR表示.
ip 可以用32位来表示 比如
255.0.0.711111111 00000000 00000000 00000111
255.0.0.7/32255.0.0.7 前32位相同的ip,那么就一个咯。
255.0.0.8/29255.0.0.8 前29位相同的ip.
255.0.0.8 -> 11111111 00000000 00000000 00001000
那么就有8个咯

1
2
3
4
5
6
7
8
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

我们要返回最短的CIDR表示

思路

首先,我们需要知道一个ip转换为CIDR表示,如何让这个范围最大。
比如从 255.0.0.7开始, 我们先要计算出二进制表示的最后一个1所在的地方
11111111 00000000 00000000 00000111 最后的一个1 在最后一位
那么这个IP的CIDR表示 最大也就是它本身了 2^0 = 1
还剩下9个
然后 255.0.0.7 + 1 就是 255.0.0.8
255.0.0.8 -> 11111111 00000000 00000000 00001000
最后的一个1在倒数第四位
那么最大的CIDR表示范围就是 2^3 = 8了
还剩下1个
255.0.0.8 + 8 就是 255.0.0.16了,
然后类似的,我们继续从255.0.0.16计算一直到剩下0个。
有了这样的思路,我们就好写代码了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def ip_to_bit(self, ip):
num_list = [ int(x) for x in ip.split('.')]
return (num_list[0]<<24) + (num_list[1]<<16) + (num_list[2]<<8) + num_list[3]

def bit_to_ip(self, num):
return ".".join([str((num >> x) % 256) for x in [24, 16, 8, 0]])
def ipToCIDR(self, ip, n):
"""
:type ip: str
:type n: int
:rtype: List[str]
"""
r = []
left = n
next_i = ip
while left >0:
ip_bit = self.ip_to_bit(next_i)
i_length = (ip_bit & -ip_bit).bit_length()
min_v = min(i_length, left.bit_length())
left -= 1<<(min_v - 1)
r.append("{}/{}".format(next_i, 33 - min_v))
next_i = self.bit_to_ip(ip_bit + (1<<(min_v -1)))
return r