题解 | #识别有效的IP地址和掩码并进行分类统计#

识别有效的IP地址和掩码并进行分类统计

http://www.nowcoder.com/practice/de538edd6f7e4bc3a5689723a7435682

题目分析

题目给出了若干个IP地址和子网掩码的字符串

我们要根据给出的信息对这些IP和掩码进行划分工作，统计类型

一共要划分和统计的类型有7种，分别是A、B、C、D、E类IP地址的数量，错误IP或错误掩码的数量、私有IP的数量

这是一个处理字符串的问题，思路其实比较简单，一点点抠细节处理清楚干净就好，但是细节很多比较麻烦。
我们首先要分开IP和掩码，分别在puip，prip，ym函数中对公有IP、私有IP、掩码进行判断和分类
大多数情况下只需要划分清楚，进行条件判断即可，但是对掩码判断我们提出两种解决方案

方法一：通过位运算处理掩码

实现思路
- 我们首先通过移位将掩码处理成32位的格式
- 然后排除全0和全1的两种非法情况
- 将掩码逐位右移，合法的情况应该是先读取到的一部分全部是0
- 然后当出现1之后，我们设置flag为1，以此表示0和1的界限
- 如果再遍历的过程中出现0，则说明掩码非法，反之则说明掩码正确

import sys

res = [0,0,0,0,0,0,0]

def puip(ip):
    if 1 <= ip[0] <= 126:				# A类地址判断条件
        res[0] += 1
    elif 128 <= ip[0] <= 191:			# B类地址判断条件
        res[1] += 1
    elif 192 <= ip[0] <= 223:			# C类地址判断条件
        res[2] += 1
    elif 224 <= ip[0] <= 239:			# D类地址判断条件
        res[3] += 1
    elif 240 <= ip[0] <= 255:			# E类地址判断条件
        res[4] += 1
    return

def prip(ip):			# 私有IP地址判断条件
    if (ip[0] == 10) or (ip[0] == 172 and 16 <= ip[1] <= 32) or (ip[0] == 192 and ip[1] == 168):
        res[6] += 1
    return

def ym(msk):			# 判断掩码合法性
    val = (msk[0] << 24) + (msk[1] << 16) + (msk[2] << 8) + msk[3]		# 转换成32位
    if val == 0:														  # 排除全0的情况
        return False
    if (val+1) == (1<<32):												# 排除全1的情况
        return False
    flag = 0
    while(val):
        digit = val & 1													# 逐位判断
        if digit == 1:
            flag = 1
        if flag == 1 and digit == 0:									# flag=1表示已经不允许再出现0
            return False
        val >>= 1
    return True
    

def judge(line):
    ip, msk = line.strip().split('~')
    ips = [int(x) for x in filter(None, ip.split('.'))]				# 获得表示IP的列表，理论上应该包含四个元素
    msks = [int(x) for x in filter(None, msk.split('.'))]			# 获得表示掩码的列表，理论上应该包含四个元素
    if ips[0] == 0 or ips[0] == 127:								# 排除非法IP不计数
        return
    if len(ips) < 4 or len(msks) < 4:								  # 判断错误掩码或错误IP
        res[5] += 1
        return
    if ym(msks) == True:											# 通过掩码判断的可以进行IP判断
        puip(ips)
        prip(ips)
    else:
        res[5] += 1
    return

for line in sys.stdin:
    judge(line)
# judge("192.168.0.2~255.255.255.0")

res = [str(x) for x in res]
print(" ".join(res))

复杂度分析

时间复杂度： $O (n)$ ，对所有的字符串都需要完全遍历一遍
空间复杂度： $O (n)$ ，存储IP和掩码所需要的额外空间申请

方法二：通过字符串索引处理掩码

实现思路
- 我们直接将掩码转换为32位字符串
- 合法掩码规则是全部非0且全部非1，并且连续的1之后只能出现连续的0
- 因此在字符串看来，0和1的分解点的索引是只差1的
- 所以我们从左到右找到第一个0出现的位置，从右到左找到第一个1出现的位置
- 根据两者相差的位置来判断掩码是否合法

alt

import sys

res = [0,0,0,0,0,0,0]

def puip(ip):
    if 1 <= ip[0] <= 126:				# A类地址判断条件
        res[0] += 1
    elif 128 <= ip[0] <= 191:			# B类地址判断条件
        res[1] += 1
    elif 192 <= ip[0] <= 223:			# C类地址判断条件
        res[2] += 1
    elif 224 <= ip[0] <= 239:			# D类地址判断条件
        res[3] += 1
    elif 240 <= ip[0] <= 255:			# E类地址判断条件
        res[4] += 1
    return

def prip(ip):			# 私有IP地址判断条件
    if (ip[0] == 10) or (ip[0] == 172 and 16 <= ip[1] <= 32) or (ip[0] == 192 and ip[1] == 168):
        res[6] += 1
    return

def ym(msk):
    val = (msk[0] << 24) + (msk[1] << 16) + (msk[2] << 8) + msk[3]	# 获取32位的掩码表示
    s = bin(val)[2:]												  # 去除“0b”字符，并转换成字符串
    pos0 = s.find('0')												  # 从左往右找到0第一次出现的位置 
    pos1 = s.rfind('1')												  # 从右往左找到1第一次出现的位置
    if pos0 != -1 and pos1 != -1 and pos0 - pos1 == 1:				  # 判断两个位置是否相差1，且是否找不到
        return True
    return False
    

def judge(line):
    ip, msk = line.strip().split('~')
    ips = [int(x) for x in filter(None, ip.split('.'))]				# 获得表示IP的列表，理论上应该包含四个元素
    msks = [int(x) for x in filter(None, msk.split('.'))]			# 获得表示掩码的列表，理论上应该包含四个元素
    if ips[0] == 0 or ips[0] == 127:								# 排除非法IP不计数
        return
    if len(ips) < 4 or len(msks) < 4:								  # 判断错误掩码或错误IP
        res[5] += 1
        return
    if ym(msks) == True:											# 通过掩码判断的可以进行IP判断
        puip(ips)
        prip(ips)
    else:
        res[5] += 1
    return

for line in sys.stdin:
    judge(line)
# judge("192.168.0.2~255.255.255.0")

res = [str(x) for x in res]
print(" ".join(res))