描述

题目描述

输入描述：

多组输入，一组3行，第1行是输入子网掩码、第2，3行是输入两个ip地址

输出描述：

若IP地址或子网掩码格式非法则输出1，若IP1与IP2属于同一子网络输出0，若IP1与IP2不属于同一子网络输出2

知识点：模拟，字符串，递推

难度：⭐⭐⭐

题解

图解：

方法一：模拟

解题思路：

将子网掩码 mask 和 两个字符串 ip 转为字符串数组后，二进制形式的每8位作为一部分，进行遍历判断

算法流程：

• 若IP地址或子网掩码格式非法则输出1，如果mask或ip有一个为false，取反为true，即有一个不符合格式，则能进入if
  • 判断是否为子网掩码：根据子网掩码的结构特性，要求左边的8位要大于等于右边八位
  • 判断是否为符合 ip：每8位的十进制在[0...255]之间
• 若IP1与IP2属于同一子网络输出0
  • IP地址与子网掩码的AND运算后，我们可以看到它运算结果是一样的
• 若IP1与IP2不属于同一子网络输出2

Java 版本代码如下：

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
        	String[] mask = scanner.nextLine().split("\\.");
            String[] ip1 = scanner.nextLine().split("\\.");
            String[] ip2 = scanner.nextLine().split("\\.");
            solution(mask, ip1, ip2);
        }
    }

    private static void solution(String[] mask, String[] ip1, String[] ip2) {
        int res = -1;
        // 若IP地址或子网掩码格式非法则输出1
        // 如果mask或ip有一个为false，取反为true，即有一个不符合格式，则能进入if
        if(!isMask(mask) || !isIp(ip1) || !isIp(ip2)) {
            res = 1; 
        } else if(belongSame(mask, ip1, ip2)) {
            // 若IP1与IP2属于同一子网络输出0
            res = 0;
        } else {
            // 若IP1与IP2不属于同一子网络输出2。
            res = 2;
        }
        System.out.println(res);
    }

    private static boolean belongSame(String[] mask, String[] ip1, String[] ip2) {
        for(int i = 0; i < mask.length; i++) {
            int maskInt = Integer.parseInt(mask[i]);
            int ip1Int = Integer.parseInt(ip1[i]);
            int ip2Int = Integer.parseInt(ip2[i]);
            // IP地址与子网掩码的AND运算后，我们可以看到它运算结果是一样的
            if((maskInt & ip1Int) != (maskInt & ip2Int)) {
                return false;
            }
        }
        return true;
    }

    // 符合返回true，不符合返回false
    private static boolean isMask(String[] mask) {
        for(int i = 1; i < mask.length; i++) {
            int pre = Integer.parseInt(mask[i-1]);
            int cur = Integer.parseInt(mask[i]);
            // 根据子网掩码的结构特性，要求左边的8位要大于等于右边八位
            if(!(pre >= 0 && pre <= 255 && cur >= 0 && cur <= 255 && pre >= cur)) {
                // 不满足。返回false
                return false;
            }
        }
        return true;
    }

    // 符合返回true，不符合返回false
    private static boolean isIp(String[] ip) {
        for(String ipStr : ip) {
            int ipInt = Integer.parseInt(ipStr);
            // 每8位的十进制在[0...255]之间
            if(ipInt < 0 || ipInt > 255) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析：

时间复杂度：$O(1)O(1)$，算法里每个for循环最多遍历4次，因此是常量级复杂度

空间复杂度：$O(1)O(1)$，算法里只用到长度为4的常量级字符串数组，因此是常量级复杂度

方法二：正则表达式

解题思路：

通过字符串流输入输出，来获取数字，只需要在流输出的时候用一个char型变量接收那个点即可。

接着遍历得到的每个数字，依次检查是否合法范围内，再将其转化成整数。

而对于掩码可以用正则表达式直接匹配

C++代码如下：

#include<iostream>
#include<string>
#include<sstream>
#include<regex>
using namespace std;

//检查掩码或者IP地址的数字部分是否合法，并将合法的转换为长整数
bool isLegal(string s, unsigned int& binum){ 
	//统计点的个数
    int point = 0; 
    unsigned int num[4] = {0, 0, 0, 0}; //记录四个数字
    stringstream ss;
    ss << s;
    char c;
    //直接用字符串流输出数字中间的点用字符变量接受
    ss >> num[0] >> c >> num[1] >> c >> num[2] >> c >> num[3]; 
    //检查数字是否合法
    for(int i = 0; i < 4; i++){
        if(num[i] < 0 || num[i] > 255)
            return false;
    }
    //位运算组装
    binum = num[0] << 24 | num[1] << 16 | num[2] << 8 | num[3]; 
    return true;
}

//单独检查掩码是否是先1后0
bool isMask(string mask){ 
     //全0全1不合法
    if(mask == "0.0.0.0" || mask == "255.255.255.255")
        return false;
    string re = "^((0|128|192|224|240|248|252|254)\.0\.0\.0|255\.(0|128|192|224|240|248|252|254)\.0\.0|255\.255\.(0|128|192|224|240|248|252|254)\.0|255\.255\.255\.(0|128|192|224|240|248|252|254|255))$";
    regex pattern(re);
    //正则表达式匹配正确的掩码
    if(regex_match(mask, pattern)) 
        return true;
    else
        return false;
}
int main(){
    string mask, ip1, ip2;
    while(cin >> mask >> ip1 >> ip2){
        unsigned int bi_mask = 0;
        unsigned int bi_ip1 = 0;
        unsigned int bi_ip2 = 0;
        //判断是否合法
        if(!isLegal(mask, bi_mask) || !isLegal(ip1, bi_ip1) || !isLegal(ip2, bi_ip2) || !isMask(mask)){
            cout << 1 << endl;
            continue;
        }
        //比较是否同一个子网
        if((bi_mask & bi_ip1) == (bi_mask & bi_ip2)) 
            cout << 0 << endl;
        else
            cout << 2 << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度：$O(1)O(1)$，通过流输入输出+正则表达式，常数时间

空间复杂度：$O(1)O(1)$，只使用了常数空间