【中等】力扣算法题解析LeetCode165：比较版本号

关注文末的名片达文汐，回复关键词“力扣源码”，即可获取完整源码！！详见：源码和核心代码的区别

题目详情

给你两个版本号字符串 version1 和 version2，请你比较它们。版本号由被点 \'.\' 分开的修订号组成。修订号的值是它转换为整数并忽略前导零。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。

返回规则如下：

• 如果 version1 < version2 返回 -1
• 如果 version1 > version2 返回 1
• 除此之外返回 0

示例 1：
输入：version1 = “1.2”, version2 = “1.10”
输出：-1
解释：version1 的第二个修订号为 “2”，version2 的第二个修订号为 “10”：2 < 10，所以 version1 < version2。

示例 2：
输入：version1 = “1.01”, version2 = “1.001”
输出：0
解释：忽略前导零，“01” 和 “001” 都代表相同的整数 “1”。

示例 3：
输入：version1 = “1.0”, version2 = “1.0.0.0”
输出：0
解释：version1 有更少的修订号，每个缺失的修订号按 “0” 处理。

提示：

• 1 <= version1.length, version2.length <= 500
• version1 和 version2 仅包含数字和 \'.\'
• version1 和 version2 都是有效版本号
• 所有修订号都可以存储在 32 位整数中

解题思路

核心思想：逐段比较版本号的修订号，忽略前导零，缺失部分视为 0。
关键优化：避免使用 split 分割字符串（节省内存），采用双指针遍历：

1. 同步遍历两个字符串：
   • 使用指针 i 遍历 version1，j 遍历 version2。
2. 提取当前修订号：
   • 遇到 \'.\' 或字符串末尾时停止，将字符段转换为整数（自动忽略前导零）。
3. 比较修订号：
   • 若当前段数值不等，直接返回结果。
   • 若一个字符串先结束，其后续修订号视为 0。
4. 移动指针：
   • 跳过 \'.\' 进入下一段比较。
5. 终止条件：
   • 当两个指针都到达末尾时结束循环。

优势：

• 时间复杂度：$O(n+m)$，其中 $n$ 和 $m$ 是字符串长度。
• 空间复杂度：$O(1)$，仅使用常数额外空间。

代码实现（Java版）

class Solution { public int compareVersion(String version1, String version2) { int i = 0, j = 0; int n1 = version1.length(), n2 = version2.length(); while (i < n1 || j < n2) { // 提取 version1 当前修订号 int num1 = 0; while (i < n1 && version1.charAt(i) != \'.\') { num1 = num1 * 10 + (version1.charAt(i) - \'0\'); i++; } // 提取 version2 当前修订号 int num2 = 0; while (j < n2 && version2.charAt(j) != \'.\') { num2 = num2 * 10 + (version2.charAt(j) - \'0\'); j++; } // 比较当前修订号 if (num1 < num2) { return -1; } else if (num1 > num2) { return 1; } // 跳过点，准备处理下一段 i++; j++; } return 0; }}

代码说明

1. 双指针遍历：
   • i 和 j 分别扫描 version1 和 version2。
2. 修订号转换：
   • 内层循环将字符段转为整数（如 \"001\" → 1），自动处理前导零。
3. 动态处理长度差异：
   • 若一个字符串先结束，其后续段在比较中视为 0（因 num1/num2 初始化为 0）。
4. 高效移动指针：
   • 外层循环末尾的 i++ 和 j++ 跳过 \'.\'，若已到末尾则自增不影响结果。

提交详情（执行用时、内存消耗）

我的名片👇👇👇👇👇👇👇👇👇👇👇