LeetCode 补充题 22. IP地址与整数的转换

约 5 分钟
文章信息 10 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 美团 快手 腾讯 高频面试题
标签
字符串
目录

题目描述

✅ 补充题 22. IP地址与整数的转换

题意分析

要实现一对互逆的函数：把点分十进制的 IPv4 字符串（形如 192.168.1.1）转成一个 32 位整数，再把这个整数还原回原字符串。两个方向都要写，且必须严格互逆——转过去再转回来必须一字不差。

约束信号全在 IPv4 的格式里：地址固定 4 段，段与段之间用 . 分隔，每段是 0 到 255 的十进制数。0 到 255 恰好是一个字节能表示的全部取值，4 个字节恰好是 32 位。也就是说，这个「转换」本质上不是计算，而是同一份 32 位数据的两种书写方式：字符串是把它按字节切开、每段写成十进制；整数是把这 4 个字节首尾相接读成一个数。最左边那段是最高字节，最右边那段是最低字节。

边界要留意三处。其一，255.255.255.255 对应 4294967295，超出了有符号 32 位整型的正数范围，在 Java 里用 int 存会变成 -1，所以要用 long（Go 里用 uint32 则天然无此问题）。其二，0.0.0.0 对应 0，还原时每段都必须输出 0，不能因为值为 0 就省略。其三，题目若额外要求校验合法性，还得判断段数是否为 4、每段是否越界、有没有前导零。

解法：按 8 位字节移位转换

核心思路

IPv4 由 4 段组成，每段范围是 0 到 255，恰好占 8 位。按网络序表示时，第一段位于最高 8 位，第四段位于最低 8 位。

IP 转整数：从左到右读取每段，先把已有结果左移 8 位，再把当前段放入低 8 位：

value = (value << 8) | part

循环不变量是：处理完前 i 段后，value 恰好是这 i 个字节按原顺序拼接的结果。因为 part <= 255，它只会占用刚腾出的低 8 位。

整数转 IP：依次右移 24、16、8、0 位，把目标字节移到最低位，再与 0xFF 相与，只保留低 8 位。四段用点号连接即可。

Java 没有无符号 int，所以用非负 long 保存 0 到 4294967295；Go 直接使用 uint32。主代码按题目约定接收合法、规范的 IPv4 输入，格式校验属于常见追问。

解题步骤

  1. 用 . 将 IP 拆成 4 段，从左到右解析。
  2. 每读一段，执行左移 8 位并按位或当前段。
  3. 反向转换时，让移位量依次取 24、16、8、0。
  4. 每次计算 (value >> shift) & 0xFF，得到对应段。
  5. 将四个十进制段用 . 连接。

192.168.1.1 的字节是 C0 A8 01 01，拼接后为十六进制 0xC0A80101，即十进制 3232235777。反向按 8 位拆分会依次取回 192、168、1、1，因此两种转换互逆。

代码实现

class Solution {
    public long ipToInt(String ip) {
        long value = 0;
        for (String part : ip.split("\\.")) {
            value = (value << 8) | Integer.parseInt(part);
        }
        return value;
    }

    public String intToIP(long value) {
        StringBuilder result = new StringBuilder();
        for (int shift = 24; shift >= 0; shift -= 8) {
            if (result.length() > 0) {
                result.append('.');
            }
            result.append((value >>> shift) & 0xFF);
        }
        return result.toString();
    }
}

import (
    "strconv"
    "strings"
)

func ipToInt(ip string) uint32 {
    var value uint32
    for _, part := range strings.Split(ip, ".") {
        num, _ := strconv.Atoi(part)
        value = value<<8 | uint32(num)
    }
    return value
}

func intToIP(value uint32) string {
    parts := make([]string, 0, 4)
    for shift := 24; shift >= 0; shift -= 8 {
        part := value >> shift & 0xFF
        parts = append(parts, strconv.Itoa(int(part)))
    }
    return strings.Join(parts, ".")
}

复杂度分析

  • 时间复杂度：$O(1)$。IPv4 固定为 4 段，字符串长度也有固定上限。
  • 空间复杂度：$O(1)$。切分数组和输出缓冲区都只保存固定数量的字符与分段。

关键点总结

  • 每段是一个字节；正向转换是按大端顺序拼接字节，反向转换是拆字节。
  • 左移 8 位等价于乘 256，& 0xFF 用于清除目标字节之外的高位。
  • Java 要用 long 表示无符号 32 位结果，避免最高位为 1 时得到负数。
  • split 中的点号是正则元字符，Java 必须写成 "\\."。
  • 面试时要能说明循环不变量，并主动给出 0.0.0.0 与 255.255.255.255 两个边界。
  • 若要求校验输入，再补充段数、纯数字、0 到 255 和前导零检查；不要把校验与位转换主逻辑混在一起讲。

易错点总结

  • 字节顺序反了：第一段应放在最高 8 位；从右向左累加会得到颠倒的地址。
  • Java 使用 int：255.255.255.255 会溢出成 -1，正确的无符号值是 4294967295。
  • Java 写成 split(".")：点号会按正则中的任意字符匹配，无法得到四段。
  • 反向只右移、不掩码：中间两段会混入更高字节，得到远大于 255 的数。
  • 移位漏掉 0：只处理 24、16、8 会缺少最后一段。
  • 忽略规范输入假设：若接口可能接收非法字符串，必须先验证再移位，不能依赖解析异常或静默截断。

相似题目

题目 难度 考察点
93. 复原 IP 地址 中等 回溯枚举四段切分
190. 颠倒二进制位 简单 逐位取出与移位重组
405. 数字转换为十六进制数 简单 每 4 位一组的进制输出
468. 验证IP地址 中等 IPv4 与 IPv6 的格式校验
751. IP 到 CIDR 中等 用最低位限制块大小的掩码构造
LCR 087. 复原 IP 地址 中等 剪枝条件下的分段搜索