BM22　比较版本号¶

中等通过率 27.92%python3核心代码模式样例通过牛客 AC字符串双指针

牛客原题　源码

讲解章节：字符串处理

一句话

双指针逐段取出修订号转成整数比较，短的一方缺位按 0 补。

解题思路¶

这题考什么¶

把「版本号比大小」归约成「逐段取整数、按段比较」。题面的三条规则里，两条棘手的都被这个归约自然消化掉：

前导零：把每段转成整数即可，int("01") 与 int("1") 都是 1，所以 "1.01" 与 "1.1" 相等；
段数不等：缺失的段视为 0，"1.1" 相当于 "1.1.0"，小于 "1.1.1"。

实现用双指针边扫边取，不调用 split，因此额外空间是 O(1)：

i、j 分别指向 version1、version2 的当前扫描位置
每轮各自从当前位置吃掉连续数字，遇到 '.' 或串尾停下，得到 num1、num2
某一侧已经扫完，它的 num 保持初值 0，这就是「缺位补 0」的实现
num1 与 num2 不等，立刻定胜负返回 1 或 -1
相等则跳过分隔符继续下一段，全部比完仍相等返回 0

数据规模与复杂度¶

1 <= 两串长度 <= 1000，修订号不超过 32 位整数范围，时限其他语言 2 秒。每个字符只被扫过一次，时间 O(n+m)，最多 2000 步；双指针不建中间列表，空间 O(1)。两项都是题面进阶要求的指标。先 split 再逐段 int 也能过，但会多出一份与输入等长的列表，空间退化到 O(n+m)。

坑在哪¶

循环条件必须是「i 或 j 还没走完」，写成「都没走完」就错。示例 3 的 "1.1" 与 "1.1.1"：用「与」时两段比完就退出并返回 0，而正确答案是 -1。用「或」时短的一方 num 停在初值 0，第三段比 0 与 1 得出 -1。
必须转成整数比，不能按字符串比。"0.226" 与 "0.36" 的第二段，按字符串比首字符 '2' 小于 '3' 会得出小于，整数 226 大于 36 结论正好相反。
num 的初值 0 是「缺位补 0」的全部实现，每轮开头都要重新置 0；若挪到循环外只初始化一次，上一段的数值会漏到下一段，结论全错。
跳过分隔符的加一不需要判越界。串尾没有 '.' 时指针会停在 n 的位置，加一后变成 n + 1，内层的 i < n 与外层的循环条件都能兜住，不会越界取字符。
32 位溢出是 C/Java 的坑，不是 Python 的。串长可到 1000，那些语言里边累加边可能溢出，得改成「先比长度再逐位比」或边扫边比； Python 整数没有位宽上限，直接累加即可。
返回值是 1、-1、0 三种整数，不是布尔值。

样例复核¶

"1.1" 与 "1.01"（示例 2）：

段 0：1 == 1
段 1：1 == int("01") = 1
两个指针都已越过串尾，循环结束，返回 0，与样例一致。

参考实现¶

solutions/nowcoder/BM22/sol.py
from typing import List, Optional


class Solution:
    def compare(self, version1: str, version2: str) -> int:
        # 只取长度，不做 split：双指针边扫边取修订号，额外空间保持 O(1)
        n, m = len(version1), len(version2)
        i = j = 0                       # 两串各自的扫描位置
        while i < n or j < m:           # 是「或」不是「与」：缺位的一方按 0 参与比较
            # 每轮都要重新置 0：既是本段的累加起点，也是「缺位视为 0」的实现
            num1 = 0
            while i < n and version1[i] != '.':
                num1 = num1 * 10 + int(version1[i])     # 逐位累加，前导零自动消掉
                i += 1
            i += 1                      # 跳过 '.'；串尾时指针越过末位，下一轮由循环条件兜住

            num2 = 0
            while j < m and version2[j] != '.':
                num2 = num2 * 10 + int(version2[j])
                j += 1
            j += 1                      # 同上，跳过 version2 这一段后的分隔符

            # 高位段一旦分出大小就是最终结论，无须再看后面的段
            if num1 > num2:
                return 1
            if num1 < num2:
                return -1
        return 0                        # 逐段比完（含补 0 的段）全部相等

BM22 比较版本号¶