LeetCode 题解工作台
比较版本号
给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。 修订号的值 是它 转换为整数 并忽略前导零。 比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0 。 返回规则…
2
题型
7
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
同时遍历两个字符串，用两个指针 和 分别指向两个字符串的当前位置，初始时 $i = j = 0$。 每次取出两个字符串中对应的修订号，记为 和 ，比较 和 的大小，如果 $a \lt b$，则返回 ；如果 $a \gt b$，则返回 ；如果 $a = b$，则继续比较下一对修订号。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你两个 版本号字符串 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 <= 500version1和version2仅包含数字和'.'version1和version2都是 有效版本号version1和version2的所有修订号都可以存储在 32 位整数 中
解题思路
方法一：双指针
同时遍历两个字符串，用两个指针 和 分别指向两个字符串的当前位置，初始时 。
每次取出两个字符串中对应的修订号，记为 和 ，比较 和 的大小，如果 ，则返回 ；如果 ，则返回 ；如果 ，则继续比较下一对修订号。
时间复杂度 ，空间复杂度 。其中 和 分别是两个字符串的长度。
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
m, n = len(version1), len(version2)
i = j = 0
while i < m or j < n:
a = b = 0
while i < m and version1[i] != '.':
a = a * 10 + int(version1[i])
i += 1
while j < n and version2[j] != '.':
b = b * 10 + int(version2[j])
j += 1
if a != b:
return -1 if a < b else 1
i, j = i + 1, j + 1
return 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests the candidate's ability to handle string manipulation and parsing with an efficient solution.
- question_mark
Assesses understanding of two-pointer technique and how to manage different-length sequences.
- question_mark
Checks if the candidate can account for edge cases like missing version revisions or leading zeros.
常见陷阱
外企场景- error
Forgetting to handle cases where one version has more revisions than the other.
- error
Incorrectly handling leading zeros in revision values.
- error
Not comparing all segments in order, which could lead to incorrect results.
进阶变体
外企场景- arrow_right_alt
Handle versions with leading zeros and unequal segment lengths.
- arrow_right_alt
Compare version strings that might contain a mix of long and short revision segments.
- arrow_right_alt
Extend the solution to compare version strings with a very large number of revisions.