201812-03 CIDR合并 （Python实现）

• 逻辑应该是正确的，就是超时了(⊙﹏⊙)

  
  image.png

from operator import itemgetter
n = input()
n = int(n)

standard_ip_list = []
for i in range(n):
    input_ip = input()
    if '/' in input_ip:
        ip_str, ip_len = input_ip.split('/')
        ip_len = int(ip_len)
    else:
        ip_str = input_ip
        ip_len = (input_ip.count('.')+1) * 8
        
    tmp_list = [0]*4
    ip_str_list = list(map(int, ip_str.split('.')))
    tmp_list[0:len(ip_str_list)] = ip_str_list[:]
    standard_ip_list.append( (tmp_list[0], tmp_list[1], tmp_list[2], tmp_list[3], ip_len) )
#sort
standard_ip_list.sort(key = itemgetter(0, 1, 2, 3, 4))  

def dec2bino(decimalNum):
    remain_list = []
    while True:
        num, remainder = divmod(decimalNum, 2)
        decimalNum = num
        remain_list.append(str(remainder))
        if num==0:
            resultStr = ''.join(remain_list[::-1])
            return '0'*( 8-len(resultStr) ) + resultStr

def needMerge(ip_a, ip_len_a, ip_b, ip_len_b):
    if ip_len_a <= ip_len_b:
        bioStrIp_a = dec2bino(ip_a[0]) + dec2bino(ip_a[1]) + dec2bino(ip_a[2]) + dec2bino(ip_a[3])
        bioStrIp_a = bioStrIp_a[0:ip_len_a]
        bioStrIp_b = dec2bino(ip_b[0]) + dec2bino(ip_b[1]) + dec2bino(ip_b[2]) + dec2bino(ip_b[3])
        bioStrIp_b = bioStrIp_b[0:ip_len_a]
        if bioStrIp_a == bioStrIp_b:
            return True
        else:
            return False
    else:
        return False

#从小到大合并
i = 0
j = 1
while True:
    if needMerge( list(standard_ip_list[i][:4]), standard_ip_list[i][4], list(standard_ip_list[j][:4]), standard_ip_list[j][4] ):
        standard_ip_list.pop(j)
    else:
        i += 1
        j += 1
        if j+1 > len(standard_ip_list):
            break
#print(standard_ip_list)
#同级合并
i = 0
while True:
    if len(standard_ip_list)>1 and standard_ip_list[i][4]==standard_ip_list[i+1][4]:
        bioStrIp_a = dec2bino(standard_ip_list[i][0]) + dec2bino(standard_ip_list[i][1]) + dec2bino(standard_ip_list[i][2]) + dec2bino(standard_ip_list[i][3])
        bioStrIp_a = bioStrIp_a[:standard_ip_list[i][4]-1] + bioStrIp_a[standard_ip_list[i][4]:]
        bioStrIp_b = dec2bino(standard_ip_list[i+1][0]) + dec2bino(standard_ip_list[i+1][1]) + dec2bino(standard_ip_list[i+1][2]) + dec2bino(standard_ip_list[i+1][3])
        bioStrIp_b = bioStrIp_b[:standard_ip_list[i][4]-1] + bioStrIp_b[standard_ip_list[i][4]:]
        if bioStrIp_a == bioStrIp_b:
            tmpList = list(standard_ip_list[i][:4])
            tmpList.append(standard_ip_list[i][4] - 1)
            standard_ip_list.insert(i,  tuple(tmpList) )
            standard_ip_list.pop(i+1)
            standard_ip_list.pop(i+1)
            if i!=0:
                i -= 1
        else:
            i += 1
            if i >= len(standard_ip_list) - 1:
                break
    else:
        i += 1
        if i >= len(standard_ip_list) - 1:
            break
    


#output
for ele in  standard_ip_list:
    print( str(ele[0])+'.'+str(ele[1])+'.'+str(ele[2])+'.'+str(ele[3])+'/'+str(ele[4]) )