nowcoder-HJ-18

HJ-19.

发布日期: 2022-06-19

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

1 题目描述

题目链接：HJ18 识别有效的IP地址和掩码并进行分类统计

请解析IP地址和对应的掩码，进行分类识别。要求按照A/B/C/D/E类地址归类，不合法的地址和掩码单独归类。

所有的IP地址划分为 A,B,C,D,E五类

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。（例如：255.255.255.32就是一个非法的掩码）
（注意二进制下全是1或者全是0均为非法子网掩码）

注意：

类似于【0.*.*.*】和【127.*.*.*】的IP地址不属于上述输入的任意一类，也不属于不合法ip地址，计数时请忽略
私有IP地址和A,B,C,D,E类地址是不冲突的

输入描述：

多行字符串。每行一个IP地址和掩码，用~隔开。

输入描述：

统计A、B、C、D、E、错误IP地址或错误掩码、私有IP的个数，之间以空格隔开。

示例1：

输入: 10.70.44.68~255.254.255.0
1.0.0.1~255.0.0.0
192.168.0.2~255.255.255.0
19..0.~255.255.255.0
输出: 1 0 1 0 0 2 1
说明: 10.70.44.68~255.254.255.0的子网掩码非法，19..0.~255.255.255.0的IP地址非法，所以错误IP地址或错误掩码的计数为2；
1.0.0.1~255.0.0.0是无误的A类地址；
192.168.0.2~255.255.255.0是无误的C类地址且是私有IP；
所以最终的结果为1 0 1 0 0 2 1

示例2：

输入: 0.201.56.50~255.255.111.255
127.201.56.50~255.255.111.255
输出: 0 0 0 0 0 0 0
说明: 类似于【0.*.*.*】和【127.*.*.*】的IP地址不属于上述输入的任意一类，也不属于不合法ip地址，计数时请忽略

2 思路

题目不难，但是有一些细节需要注意。首先读取输入字符串，然后分别裁剪出ip和mask并转换为vector类型(str2vec函数)，并对转换结果进行判断，看ip和mask是否有效(这里的有效与否只看是否越界或者位数不够的情况，不对mask进行额外的判断)，然后将转换后的ip进行判断，看是否属于特殊ip地址，若是则忽略继续读取下一个字符串；否则判断mask地址是否有效(连续1+连续0, 对应isValidMask函数),最后判断ip属于哪一种类别即可(对应getClass函数).

#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 获取ip所属类型
// 1-7分别对应ABCDE、非法、私有，但由于私有与ABC三种重合，因而用十位数表征
// 如返回11说明该ip为私人、A类
int getClass(vector<int> ip){
    int ans = 0;
    if(ip[0] == 10||(ip[0]==172&&ip[1]>=16&&ip[1]<=31)||(ip[0]==192&&ip[1]==168)){
        ans += 10;
    }
    if(ip[0] >= 1 && ip[0] <= 126){
        ans += 1;
    }else if(ip[0] >= 128 && ip[0] <= 191){
        ans += 2;
    }else if(ip[0] >= 192 && ip[0] <= 223){
        ans += 3;
    }else if(ip[0] >= 224 && ip[0] <= 239){
        ans += 4;
    }else if(ip[0] >= 240 && ip[0] <= 255){
        ans += 5;
    }
    return ans;
}

// 判断mask是否有效，即连续1加连续0且不全为1和不全为0
bool isValidMask(vector<int> mask){
    bool flag = false;
    for(int i = 3; i >= 0; --i){
        for(int j = 0; j < 8; ++j){
            if(!flag && (mask[i]>>j)&1 == 0){
                continue;
            }else if((mask[i]>>j)&1 == 1){
                flag = true;
            }else if(flag){
                return false;
            }
        }
    }
    if(mask[3] == 255 || mask[0] == 0)    return false;
    return true;
}

// 将string类型的ip和mask转换为vector类型
bool str2vec(vector<int>& tmp, string str){
    int cnt = 0, len = str.length(), index = 0;
    for(int i = 0; i < len; ++i){
        if(str[i] == '.'){
            if(i == 0 || str[i-1] == '.'){
                return false;
            }
            tmp[index++] = cnt;
            cnt = 0;
        }else if(str[i] >= '0' && str[i] <= '9'){
            cnt *= 10;
            cnt += str[i] - '0';
        }else{
            return false;
        }
    }
    tmp[index++] = cnt;
    return index == 4;
}

// 更新答案数组
void update(vector<int>& cnt, string ip, string mask){
    vector<int> tmp1(4, 0), tmp2(4, 0);
    // ip、mask位数不足或越界
    if(!str2vec(tmp1, ip) || !str2vec(tmp2, mask)){
        cnt[5]++;
        return;
    }
    // 为特有ip，不用计入计数
    // 注意：ip为特有ip时不需要mask有效
    if(tmp1[0] == 0 || tmp1[0] == 127){
        return;
    }
    // 判断mask是否有效
    if(!isValidMask(tmp2)){ 
        cnt[5]++;
        return;
    }
    // 获取ip所述类别
    int type = getClass(tmp1);
    if(type > 10){      // 大于10说明为私人类别
        type %= 10;     // 取出个位，用于判断属于前五种的哪一类
        cnt[6]++;       
    }
    cnt[type-1]++;
}

int main(void){
    string str;
    vector<int> cnt(7, 0);
    while(cin >> str){
        int pos = str.find('~');
        // 截取ip和mask
        string ip = str.substr(0, pos); 
        string mask = str.substr(pos+1);
        update(cnt, ip, mask);
    }
    for(int i = 0; i < 7; ++i){
        cout << cnt[i] << " ";
    }
    return 0;
}