C++实现LeetCode 165.版本比较：四种核心解法详解

小岛来信

发布时间：2026-10-16| 3人浏览过

原创

在软件开发与系统管理中，版本号的规范化比较是一项常见需求。本文聚焦LeetCode 165题，深入剖析C++环境下如何实现高效的字符串版本号对比。我们将通过指针操作、算术累加、标准库流及底层C风格转换四种方式，逐一拆解如何处理分隔符缺失、高位无效零等边界情况。

问题背景与核心挑战

给定两个由 . 连接的数字序列字符串作为版本号（如 version1 = "0.1"），需按以下规则返回比较结果：

若 version1 > version2，返回 1；
若 version1 < version2，返回 -1；
若相等，返回 0。

核心挑战在于：版本号各段的数值可能因缺少前导零（如 1.0.1 与 1）或包含无意义尾随零（如 1.0 与 1）而产生混淆。算法必须逐段提取并转换为整数进行对齐比较，而非简单的字典序比较。

解法一：双指针同步遍历

最直观的方法是维护两个指针，分别指向当前正在处理的字符。每次循环中，从当前位置开始收集直到下一个 . 的所有字符，将其拼接为临时字符串，再使用 atoi 转为整型进行比较。若两数不等，直接返回结果；若相等，清空临时变量并跳过 . 继续下一轮。

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int n1 = version1.size(), n2 = version2.size();
        int i = 0, j = 0;
        string v1, v2; 
        while (i < n1 || j < n2) {
            // 收集 version1 的当前段
            while (i < n1 && version1[i] != '.') {
                v1.push_back(version1[i++]);
            }
            int d1 = atoi(v1.c_str());
            
            // 收集 version2 的当前段
            while (j < n2 && version2[j] != '.') {
                v2.push_back(version2[j++]);
            }
            int d2 = atoi(v2.c_str());
            
            if (d1 > d2) return 1;
            else if (d1 < d2) return -1;
            
            v1.clear(); 
            v2.clear();
            ++i; 
            ++j; // 跳过 '.' 或处理末尾
        }
        return 0;
    }
};

解法二：内存优化（手动累加）

上述方法需要额外的空间存储子串。可以通过一位一位读取字符并计算十进制值来节省内存。只要遇到非数字字符或字符串结束，当前段的数值计算即告完成。

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int n1 = version1.size(), n2 = version2.size();
        int i = 0, j = 0;
        int d1 = 0, d2 = 0;
        while (i < n1 || j < n2) {
            // 计算 version1 当前段数值
            while (i < n1 && version1[i] != '.') {
                d1 = d1 * 10 + (version1[i++] - '0');
            }
            // 计算 version2 当前段数值
            while (j < n2 && version2[j] != '.') {
                d2 = d2 * 10 + (version2[j++] - '0');
            }
            if (d1 > d2) return 1;
            else if (d1 < d2) return -1;
            
            d1 = 0; 
            d2 = 0;
            ++i; 
            ++j; 
        }
        return 0;
    }
};

解法三：利用 stringstream 简化逻辑

C++ 标准库中的 stringstream 可以轻松处理分隔符分割。通过在每个版本号后追加一个 .，确保即使最后一位没有小数点也能触发一次提取操作。这种写法代码最为简洁，但引入了少量的IO开销。

class Solution {
public:
    int compareVersion(string version1, string version2) {
        istringstream s1(version1 + "."), s2(version2 + ".");
        int d1 = 0, d2 = 0;
        char dot;
        // 只要任一输入流有效，就继续循环
        while (s1.good() || s2.good()) {
            if (s1.good()) s1 >> d1 >> dot;
            if (s2.good()) s2 >> d2 >> dot;
            if (d1 > d2) return 1;
            else if (d1 < d2) return -1;
            d1 = 0; 
            d2 = 0;
        }
        return 0;
    }
};

解法四：C风格指针与 strtol

对于追求极致性能的场景，可以使用 C 语言的指针操作配合 strtol 函数。strtol 会自动识别数字并将其后的指针更新到第一个非数字字符处，非常适合此类迭代场景。

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int res = 0;
        const char* v1 = version1.c_str();
        const char* v2 = version2.c_str();
        while (res == 0 && (*v1 != '\0' || *v2 != '\0')) {
            long d1 = *v1 == '\0' ? 0 : strtol(v1, const_cast(&v1), 10);
            long d2 = *v2 == '\0' ? 0 : strtol(v2, const_cast(&v2), 10);
            if (d1 > d2) return 1;
            else if (d1 < d2) return -1;
            else {
                if (*v1 != '\0') ++v1;
                if (*v2 != '\0') ++v2;
            }
        }
        return res;
    }
};