LeetCode 165. 比较版本号

约 5 分钟
文章信息 20 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 拼多多 小米 虾皮 哔哩哔哩
标签
字符串 双指针
目录

题目描述

✅ 165. 比较版本号

image-20230820001814093

image-20230820001807595

题意分析

给定两个由点号分隔的版本号字符串，要判断谁更新：version1 更大返回 1，更小返回 -1，相等返回 0。

题面明确了三件事，每一件都是实现上的约束信号。第一，比较的单位是「修订号」而不是字符：每一段要按十进制整数理解，所以 01 与 1 是同一个数，前导零没有意义。第二，比较是从左到右、逐段进行的，高位段一旦分出胜负，后面的段无论多大都不再参与——这是一个字典序式的比较，不是把整个版本号看成一个数。第三，两个版本号的段数可以不同，缺失的段按 0 补齐，因此 1.0 与 1 相等，1.0.1 却比 1 大。

数据范围也给了提示：字符串只含数字与点号，且每个修订号都能放进 32 位整数，这意味着可以边扫边用 int 累加数值，不必担心溢出或引入大整数。

需要留意的边界情形：某一段全是零（如 1.000）；一个版本是另一个的前缀（如 1 与 1.0.0）；两个版本段数不等且差异出现在补零的那一段（如 1.0.1 与 1）。

解法：双指针逐段解析

核心思路

用两个指针同步解析当前修订号，遇到点号结束一段。每段按整数比较，第一处不同立即返回；一方提前结束时，缺失的修订号自然按 0 处理。

解题步骤

  • 当任一字符串尚未读完时，分别解析两个版本号的当前段。
  • 用 num = num * 10 + digit 计算段值，前导零会自然被忽略。
  • 跳过点号并比较两个段值，不相等时立即返回结果。
  • 所有段都相等时返回 0。

代码实现

class Solution {
    public int compareVersion(String version1, String version2) {
        int i = 0;
        int j = 0;

        while (i < version1.length() || j < version2.length()) {
            int num1 = 0;
            while (i < version1.length() && version1.charAt(i) != '.') {
                num1 = num1 * 10 + version1.charAt(i) - '0';
                i++;
            }
            if (i < version1.length()) {
                i++;
            }

            int num2 = 0;
            while (j < version2.length() && version2.charAt(j) != '.') {
                num2 = num2 * 10 + version2.charAt(j) - '0';
                j++;
            }
            if (j < version2.length()) {
                j++;
            }

            if (num1 > num2) {
                return 1;
            }
            if (num1 < num2) {
                return -1;
            }
        }

        return 0;
    }
}

func compareVersion(version1 string, version2 string) int {
    i := 0
    j := 0

    for i < len(version1) || j < len(version2) {
        num1 := 0
        for i < len(version1) && version1[i] != '.' {
            num1 = num1*10 + int(version1[i]-'0')
            i++
        }
        if i < len(version1) {
            i++
        }

        num2 := 0
        for j < len(version2) && version2[j] != '.' {
            num2 = num2*10 + int(version2[j]-'0')
            j++
        }
        if j < len(version2) {
            j++
        }

        if num1 > num2 {
            return 1
        }
        if num1 < num2 {
            return -1
        }
    }

    return 0
}

复杂度分析

  • 时间复杂度：$O(m + n)$，每个字符只被扫描一次。
  • 空间复杂度：$O(1)$。

关键点总结

  • 修订号必须按整数比较，不能按字符或整串字典序比较。
  • 外层循环使用“或”，才能继续检查较长版本剩余的段。
  • 缺失段按 0 处理，末尾多出的零段不影响结果。

易错点总结

  • 直接比较字符串会把 1.10 错判为小于 1.2。
  • 外层循环使用“且”会漏掉较长版本的剩余段。
  • 忘记跳过点号会使指针停滞，形成死循环。
  • 不能按段数多少判断大小，1 与 1.0.0 相等。

相似题目

题目 难度 考察点
393. UTF-8 编码验证 中等 切分依据从分隔符变成首字节的位模式，且只做合法性判定、不比较大小
468. 验证IP地址 中等 同样按分隔符切段，但要校验段数、段长与前导零是否合法，而非比较数值