#165
中等
中频
split-and-compare比较版本号
这是一道围绕字符串展开的高频练习。建议先掌握「split-and-compare」这套写法,再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
字符串
题目分析
这道题表面上是在处理「比较版本号」,但先要想清楚题目到底让你返回什么,以及过程中哪些约束必须一直满足。从题型上看,它主要在考 字符串 这些能力。先别急着写代码,先把题目要求翻译成人话,明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话,后面的推荐代码才是在实现思路,而不是直接给答案。
接下来怎么看推荐代码: 带着这个理解再看推荐代码时,重点观察这条主线:先按点号切分两个版本号,再逐段按整数比较,缺失段默认看作 0。
推荐代码
推荐解法:split-and-compare
时间复杂度: O(m+n)
空间复杂度: O(m+n)
核心思路: 先按点号切分两个版本号,再逐段按整数比较,缺失段默认看作 0。
class Solution {
public int compareVersion(String version1, String version2) {
// 将版本号分割成数组
String[] v1 = version1.split("\.");
String[] v2 = version2.split("\.");
int i = 0;
int j = 0;
// 比较两个版本号的每一部分
while (i < v1.length || j < v2.length) {
// 将当前部分转换为整数,如果超出数组长度则视为0
int num1 = i < v1.length ? Integer.parseInt(v1[i]) : 0;
int num2 = j < v2.length ? Integer.parseInt(v2[j]) : 0;
// 比较当前部分
if (num1 < num2) {
return -1;
} else if (num1 > num2) {
return 1;
}
// 移动指针
i++;
j++;
}
// 所有部分都相等,返回0
return 0;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会把版本号按点切开,然后逐段按整数比较。
核心过程
- 先把两个版本号切成数组。
- 从左到右比较同一位置的段值。
- 如果某一侧没有这一段,就按 0 处理。
- 一旦某段不相等就返回,否则全部比较完返回相等。
复杂度总结
时间复杂度 O(m+n),空间复杂度 O(m+n)。
面试补一句:这题最容易错的是忘了“按整数比”和“缺失段看作 0”。
核心思路
版本号比较的关键是“按段比较而不是按整串比较”。每一段都要当整数处理,所以前导零不会影响大小关系。
步骤讲解
1
先按点号切分版本号
把两个版本号都拆成若干段,便于逐段对应比较。
为什么这样做:版本号语义天然按段组织,不适合直接字典序比较。
对应代码提示:String[] parts1 = version1.split("\.");
2
逐段转整数比较
从左到右比较同位置段值,遇到不相等时立刻返回结果。
为什么这样做:高位版本段优先级更高,先出现差异就已经决定大小。
对应代码提示:int a = i < parts1.length ? Integer.parseInt(parts1[i]) : 0;
3
缺失段按 0 处理
如果某一侧段数更少,就把超出的段视作 0 继续比较。
为什么这样做:像
1.0 和 1.0.0 在语义上应当相等。对应代码提示:int b = i < parts2.length ? Integer.parseInt(parts2[i]) : 0;
易错点
按字符串字典序比较
像 10 和 2 的字符串顺序与整数顺序不同。
正确理解:每段必须转整数比较。
把前导零当成有效差异
01 和 1 代表相同版本段值。
正确理解:按整数解析后再比,前导零自然被忽略。
少段的一边直接判小
尾部缺失段可能全是 0,此时两个版本应相等。
正确理解:缺失段要默认按 0 继续比较。
复杂度与适用判断
时间复杂度:O(m+n)
空间复杂度:O(m+n)
比其他方案更好在哪里:比手写字符扫描更直观,也足够满足题目规模。
适用判断:字符串分段后各段语义独立时,优先考虑 split 后逐段处理。
额外提醒
- 版本号比较的最小单位是“段”,不是单个字符。
动画演示
如果你还没完全看懂,可以展开动画演示。
split-and-compare动画演示
想看这段解法是怎么一步步运行的,可以展开动画继续观察。
split-and-compare动画演示
想看这段解法是怎么一步步运行的,可以展开动画继续观察。
比较版本号
版本号 1 分割结果
版本号 2 分割结果
比较过程
0
0
当前比较第 1 部分
操作日志
动画演示仅在桌面端提供,移动端请优先阅读推荐代码与结构化讲解。