题目的主要信息：
-
给出多行字符串，每行都是"IP地址~掩码"的形式，统计A类地址、B类地址、C类地址、D类地址、E类地址、错误IP地址或错误掩码、私有IP的个数，之间以空格隔开
-
IP地址类型如下：
A类地址1.0.0.0~126.255.255.255;
B类地址128.0.0.0~191.255.255.255;
C类地址192.0.0.0~223.255.255.255;
D类地址224.0.0.0~239.255.255.255；
E类地址240.0.0.0~255.255.255.255；
-
私网IP地址如下：
10.0.0.0-10.255.255.255
172.16.0.0-172.31.255.255
192.168.0.0-192.168.255.255
-
子网掩码为二进制下前面是连续的1，然后全是0，后半部分出现1就是非法，二进制下全是1或者全是0均为非法
-
类似于【0...】和【127...】的IP地址不属于上述输入的任意一类，也不属于不合法ip地址，计数时请忽略
-
IP地址中不能出现非数字，数字不会大于255
方法一：遍历检查
具体做法：
本来这是一个七分类的问题，但是我们先转化成二分类问题，首先检查IP地址及掩码是否合法，再去讨论究竟是ABCDE还是私有。
- 遍历字符串，以点或者~为界限分割数字，如果在分割过程中数字部分出现了非数字字符，则不合法；
- 如果分割，计算出来的数字大于255，则不合法；
- 分割出来的数字，我们存储在数组中，理论上应该是8个数字，如果少于这个数字则不合法；
- 检查分割出来的第一个数字是否是0或者127，这两个数字开头的IP地址合法，但是题目要求忽略；
- 然后检查掩码，从数组第4位开始（下标0开始），掩码前面应该是全1，后面是全0，因此找到第一个不是255的数，如果所有的数都是255，说明掩码全1，不合法；
- 掩码第一个不是255的数如果刚好是11111110（254）、11111100（252）、11111000（248）、11110000（240）、1110000（224）、11000000（191）、10000000（128），也是可以的，我们进入下一位，后面的数必须是全0，否则也是不合法的。
经过上面的步骤我们排除了所有IP地址及掩码不合法的形式，对于这些也不用继续讨论了，统计完不合法跳过就行了。
然后我们检查数组中的前四个数字，是否在ABCDE对应的范围之内，以及是否在私有地址范围之内，几个判断语句就可以搞定。
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
vector<int> arr(7, 0); //分别对应题目的7个类别
string s;
while(getline(cin, s)){
int n = s.length();
vector<int> ips; //记录ip地址的数字
bool bad = false;
bool isnum = false;
int num = 0;
for(int i = 0; i < n; i++){ //遍历该ip字符串
if(s[i] == '.' || s[i] == '~'){ //以.或者~分割
if(isnum){
if(num > 255){
bad = true; //错误ip，数字不能超过255
break;
}
ips.push_back(num);
isnum = false;
num = 0;
}else{
arr[5]++; //错误地址
bad = true;
break;
}
}else if(s[i] >= '0' && s[i] <= '9'){
isnum = true;
num = num * 10 + s[i] - '0'; //计算数字
}else{
arr[5]++;
isnum = false; //错误地址，数字部分还有非数字
bad = true;
break;
}
}
if(isnum)
ips.push_back(num); //最后一个数字
if(ips[0] == 0 || ips[0] == 127 || bad)
continue; //忽略0或者127开头的地址，错误ip已经统计了过了，可以忽略
int mask = 4; //查看掩码的数字
while(mask < 8 && ips[mask] == 255)
mask++; //找到掩码第一个不全为1的数
if(mask == 8){ //掩码全1也是不合法
arr[5]++;
continue;
}else if(ips[mask] == 254 || ips[mask] == 252 || ips[mask] == 248 || ips[mask] == 240 || ips[mask] == 224 || ips[mask] == 191 || ips[mask] == 128)
mask++; //各类掩码含1的最后一位
while(mask < 8 && ips[mask] == 0)
mask++;
if(mask != 8){ //掩码后半部分不能有1
arr[5]++;
continue;
}
if(ips[0] >= 1 && ips[0] <= 126)
arr[0]++; //A类地址
else if(ips[0] >= 128 && ips[0] <= 191)
arr[1]++; //B类地址
else if(ips[0] >= 192 && ips[0] <= 223)
arr[2]++; //C类地址
else if(ips[0] >= 224 && ips[0] <= 239)
arr[3]++; //D类地址
else if(ips[0] >= 240 && ips[0] <= 255)
arr[4]++; //E类地址
if(ips[0] == 10)
arr[6]++; //私有地址10开头的
else if(ips[0] == 172 && (ips[1] >= 16 && ips[1] <= 31))
arr[6]++; //私有地址172.16.0.0-172.31.255.255
else if(ips[0] == 192 && ips[1] == 168)
arr[6]++; //私有地址192.168.0.0-192.168.255.255
}
for(int i = 0; i < 7; i++){ //输出
cout << arr[i];
if(i != 6)
cout << " ";
}
cout << endl;
return 0;
}
复杂度分析：
- 时间复杂度：，为字符串长度，遍历整个字符串，后续的循环都是常数时间
- 空间复杂度：，记录数字的数组长度为8，常数空间，记录答案的数组长度为7，常数空间
方法二：正则表达式
具体做法：
我们也可以根据题目所给信息写出掩码的正确形式的正则表达式、ABCDE类地址的正则表达式，私有地址的正则表达式。每次将输入的字符串从~处分割成两份，优先判断IP地址开头是否是127或者0，这两种直接忽略，然后验证掩码部分是否合法，再验证私有地址，最后验证五类IP地址，如果不属于5种IP地址，也是不符合。
import re
#各类的地址的正则表达式
error_pattern = re.compile(r'1+0+')
A_pattern = re.compile(r'((12[0-6]|1[0-1]\d|[1-9]\d|[1-9])\.)((1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.){2}(1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)')
B_pattern = re.compile(r'(12[8-9]|1[3-8]\d|19[0-1])\.((1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.){2}(1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)')
C_pattern = re.compile(r'(19[2-9]|2[0-1]\d|22[0-3])\.((1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.){2}(1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)')
D_pattern = re.compile(r'(22[4-9]|23\d)\.((1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.){2}(1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)')
E_pattern = re.compile(r'(24\d|25[0-5])\.((1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.){2}(1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)')
self_pattern = re.compile(r'((10\.((1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.){2}(1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d))|(172\.(1[6-9]|2\d|3[0-1])\.(1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.(1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d))|(192\.168\.(1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.(1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)))')
escape = re.compile(r'((0|127)\.((1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.){2}(1\d\d|2[0-4]\d|25[0-5]|[1-9]\d|\d))')
def judge_mask(line):
if line == '255.255.255.255' or line == '0.0.0.0': #全0全1
return 0
judge = line.split('.') #按照点分割数字
res = ''
for j in judge:
res += '{:0>8b}'.format(int(j))
res = re.fullmatch(error_pattern, res)
if res == None:
return 0
else:
return 1
def judge(pattern, line): #匹配函数
if re.fullmatch(pattern, line) != None:
return 1
else:
return 0
arr = [0]*7
while True:
try:
line = input().split('~') #从~分割IP地址和掩码
if line[0][0:4] == "127." or line[0][0:2] == "0.": #优先判断127或者0开头的
continue
if judge_mask(line[1]): #先判断掩码是否正确
#正则比较各个IP地址
if judge(self_pattern, line[0]): #私有与其他的不冲突，优先单独匹配
arr[6] += 1
if judge(A_pattern, line[0]):
arr[0] += 1
elif judge(B_pattern, line[0]):
arr[1] += 1
elif judge(C_pattern, line[0]):
arr[2] += 1
elif judge(D_pattern, line[0]):
arr[3] += 1
elif judge(E_pattern, line[0]):
arr[4] += 1
elif judge(escape, line[0]):
continue
else:
arr[5] += 1 #IP地址错误
else: #掩码错误
arr[5] += 1
except:
print(' '.join([str(i) for i in arr])) #输出
break
复杂度分析：
- 时间复杂度：，正则匹配的复杂度
- 空间复杂度：，各个临时变量都是常数级
京公网安备 11010502036488号