刷题笔记合集🔗

IPv4地址转换成整数

问题描述

有一种虚拟 IPv4 地址，由 4 个小节组成，每节的范围为 ，以 # 号间隔。这种虚拟 IPv4 地址可以转换为一个 32 位的整数。例如：

• 128#0#255#255 转换为 32 位整数的结果为 2147549183（0x8000FFFF）
• 1#0#0#0 转换为 32 位整数的结果为 16777216（0x01000000）

现给出一个以字符串形式表示的虚拟 IPv4 地址，要求将其转换为对应的整数。转换时需要注意以下限制：

1. 第 1 小节的范围为 。
2. 其他小节的范围为 。
3. 每个 IPv4 地址只能对应到唯一的整数上。

如果输入的 IPv4 地址非法，则返回 "invalid IP"。

输入格式

输入一行，为虚拟 IPv4 地址格式的字符串。

输出格式

输出一行，为转换后的整数或 "invalid IP"（如果输入非法）。

样例输入1

100#101#1#5

样例输出1

1684340997

样例输入2

1#2#3

样例输出2

invalid IP

样例输入3

01#01#01#01

样例输出3

invalid IP

样例解释

数据范围

• 输入字符串的长度不超过 20。
• 合法 IPv4 地址中，第一个小节的范围为 ，其他小节的范围为 。

题解

模拟

这道题目要求将虚拟 IPv4 地址转换为整数，同时需要处理各种非法输入的情况。解决这个问题的关键在于正确地解析输入字符串并进行有效性检查。以下是解题思路：

1. 首先，使用 '#' 分割输入字符串，得到 4 个小节。如果分割后的小节数不是 4，则直接返回 "invalid IP"。

2. 对每个小节进行以下检查：

   • 检查是否为空字符串
   • 检查是否包含非数字字符
   • 检查是否有前导零（除非该小节就是 '0'）
   • 将字符串转换为整数，并检查是否在有效范围内
     • 第一个小节：1 ~ 128
     • 其他小节：0 ~ 255

3. 如果所有检查都通过，则将 4 个小节转换为一个 32 位整数：

   • 使用位运算，将每个小节左移适当的位数并相加
   • 注意要使用长整型（如 Java 中的 long）来避免溢出

4. 最后，返回计算得到的整数结果

这个解法的时间复杂度是 O(n)，其中 n 是输入字符串的长度。因为我们只需要遍历一次输入字符串，并对每个字符进行常数时间的操作。

空间复杂度是 O(1)，因为我们只使用了固定大小的额外空间来存储临时变量和结果。

参考代码

• Python

def ip_to_int(ip):
    # 分割 IP 地址字符串
    parts = ip.split('#')
    
    # 检查是否正好有 4 个部分
    if len(parts) != 4:
        return "invalid IP"
    
    result = 0
    for i, part in enumerate(parts):
        # 检查每个部分是否为空
        if not part:
            return "invalid IP"
        
        # 检查是否有前导零
        if len(part) > 1 and part[0] == '0':
            return "invalid IP"
        
        try:
            num = int(part)
            # 检查范围
            if i == 0:
                if num < 1 or num > 128:
                    return "invalid IP"
            else:
                if num < 0 or num > 255:
                    return "invalid IP"
            
            # 将当前部分加到结果中
            result = (result << 8) + num
        except ValueError:
            # 如果无法转换为整数，则为非法输入
            return "invalid IP"
    
    return str(result)

# 读取输入
ip = input().strip()

# 输出结果
print(ip_to_int(ip))

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_IP_LEN 20

// 将 IP 地址转换为整数
char* ip_to_int(char* ip) {
    char* parts[4];
    int count = 0;
    char* token = strtok(ip, "#");
    
    // 分割 IP 地址字符串
    while (token != NULL && count < 4) {
        parts[count++] = token;
        token = strtok(NULL, "#");
    }
    
    // 检查是否正好有 4 个部分
    if (count != 4) {
        return "invalid IP";
    }
    
    unsigned long result = 0;
    for (int i = 0; i < 4; i++) {
        // 检查每个部分是否为空
        if (strlen(parts[i]) == 0) {
            return "invalid IP";
        }
        
        // 检查是否有前导零
        if (strlen(parts[i]) > 1 && parts[i][0] == '0') {
            return "invalid IP";
        }
        
        char* endptr;
        long num = strtol(parts[i], &endptr, 10);
        
        // 检查是否成功转换为整数
        if (*endptr != '\0') {
            return "invalid IP";
        }
        
        // 检查范围
        if (i == 0) {
            if (num < 1 || num > 128) {
                return "invalid IP";
            }
        } else {
            if (num < 0 || num > 255)