LeetCode 165. 比较版本号

约 6 分钟
文章信息 21 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 100-200 腾讯 字节 阿里 微软 美团 拼多多 京东 小米 百度 网易 快手 滴滴 B站 虾皮 猿辅导
标签
字符串 双指针

题目描述

✅ 165. 比较版本号

image-20260928190048232

image-20260928190048233

题意分析

版本号由点号分隔的若干修订号组成，比较时从左到右，逐段比较数值。前面的段都相等时，第一对数值不同的段决定结果：第一个版本更大返回 1，更小返回 -1，全部相等返回 0。

每段的前导零不影响数值；如果一个版本提前结束，它缺少的后续段全部视为 0。因此字符串长度、修订号的位数以及段数都不能直接决定大小，也不能把整个版本号当作小数比较。

题目保证输入是有效版本号，每段数值都能放入 32 位整数，所以可以逐段用整数解析，无需额外处理非法点号或超范围数字。

解法：双指针逐段解析

核心思路

[!blue]

比较顺序由修订号的位置决定，后面的段不能推翻前面已经出现的大小关系。因此不必先拆分并保存所有段，只需要用 i、j 指向两个版本中下一段的开头，每轮完整读出对应的一段，比较后再决定是否继续。

读取一段时，把段值从 0 开始累积。每读入一个数字，就用 num = num * 10 + digit 把原值左移一个十进制位，再加入当前数字；读到点号或字符串结尾时，这一段结束。前导零在累积过程中不会改变数值，因此自然被忽略。题目保证最终段值不超过整数范围，这里的逐位累积也是安全的。

每轮必须重新把两个段值置为 0。如果一方已经读完，它的解析循环不会执行，段值就保持为 0，正好代表缺失段；另一方仍然继续读取。外层循环因此使用“至少一方未结束”的条件，直到两个版本都处理完。

每轮开始时，之前比较过的所有对应段都相等。本轮若不同，就可以立即返回大小关系；本轮仍相等，就从已越过点号的位置继续下一轮。若循环正常结束，说明所有实际段及补出的零段都相等，返回 0。指针只向右移动，不需要切分数组或创建子串。

解题步骤

  1. 将两个指针 i、j 初始化为 0；只要任一指针尚未到达字符串末尾，就开始一轮比较。
  2. 将 num1 置为 0，从 version1[i] 开始累积数字，直到点号或末尾；若停在点号上，再将 i 前移一次。
  3. 同样读取 version2 的当前段到 num2。已结束的一方不移动，段值保持 0。
  4. 若 num1 > num2 返回 1，若 num1 < num2 返回 -1；相等则继续读取后续段。
  5. 两个版本都读完仍未发现不同，返回 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)$，m、n 分别是两个版本字符串的长度；每个字符最多被指针扫描一次，提前发现不同可以立即结束。
  • 空间复杂度：$O(1)$，只保存两个指针和当前两段的整数值，不创建分段数组。

关键点总结

[!green]

  • 比较单位是对应位置修订号的数值，而不是整个字符串的字典序。
  • 每轮重新置零，同时解决前导零与缺失尾段的处理。
  • 前面各段相等是继续比较的前提，第一处不同就决定完整版本号的大小。
  • “或”保证较长版本的尾段仍会被检查，末尾多出的全零段则不影响相等结论。

易错点总结

[!yellow]

  • 直接按字符比较，会把数字位数和前导零误当成修订号的大小关系。
  • 外层循环写成“且”，会在较短版本结束时提前停止，漏掉另一方可能非零的尾段。
  • 不在每轮重置段值，会把上一段的数值累积进下一段。
  • 读完数字后忘记越过点号，指针会停在原处，无法结束循环。
  • 根据段数直接判断大小，会忽略缺失段按零处理的规则；必须继续比较剩余段的实际值。

相似题目

题目 难度 关联与区别
8. 字符串转换整数 (atoi) 中等 同样解析十进制数字，本题每段分别比较且忽略前导零，不把完整版本号当一个整数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/01343908
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！