比较版本号
难度:
标签:
题目描述
给你两个版本号 version1
和 version2
,请你比较它们。
版本号由一个或多个修订号组成,各修订号由一个 '.'
连接。每个修订号由 多位数字 组成,可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推。例如,2.5.33
和 0.1
都是有效的版本号。
比较版本号时,请按从左到右的顺序依次比较它们的修订号。比较修订号时,只需比较 忽略任何前导零后的整数值 。也就是说,修订号 1
和修订号 001
相等 。如果版本号没有指定某个下标处的修订号,则该修订号视为 0
。例如,版本 1.0
小于版本 1.1
,因为它们下标为 0
的修订号相同,而下标为 1
的修订号分别为 0
和 1
,0 < 1
。
返回规则如下:
- 如果
version1 > version2
返回1
, - 如果
version1 < version2
返回-1
, - 除此之外返回
0
。
示例 1:
输入:version1 = "1.01", version2 = "1.001" 输出:0 解释:忽略前导零,"01" 和 "001" 都表示相同的整数 "1"
示例 2:
输入:version1 = "1.0", version2 = "1.0.0" 输出:0 解释:version1 没有指定下标为 2 的修订号,即视为 "0"
示例 3:
输入:version1 = "0.1", version2 = "1.1" 输出:-1 解释:version1 中下标为 0 的修订号是 "0",version2 中下标为 0 的修订号是 "1" 。0 < 1,所以 version1 < version2
提示:
1 <= version1.length, version2.length <= 500
version1
和version2
仅包含数字和'.'
version1
和version2
都是 有效版本号version1
和version2
的所有修订号都可以存储在 32 位整数 中
代码结果
运行时间: 20 ms, 内存: 0.0 MB
/*
* Solution approach using Java Streams:
* 1. Split both version strings by '.' to get individual revision numbers.
* 2. Convert these revision numbers to integers, treating missing numbers as 0.
* 3. Use IntStream to compare the revisions from both versions.
* 4. Return the appropriate result based on the comparison.
*/
import java.util.stream.IntStream;
public class CompareVersionNumbersStream {
public int compareVersion(String version1, String version2) {
int[] levels1 = Stream.of(version1.split("\\.")).mapToInt(Integer::parseInt).toArray();
int[] levels2 = Stream.of(version2.split("\\.")).mapToInt(Integer::parseInt).toArray();
int length = Math.max(levels1.length, levels2.length);
return IntStream.range(0, length).map(i -> Integer.compare(
i < levels1.length ? levels1[i] : 0,
i < levels2.length ? levels2[i] : 0
)).filter(result -> result != 0).findFirst().orElse(0);
}
}
解释
方法:
该题解的思路是将两个版本号字符串按照 '.' 分割成两个列表,然后从左到右逐个比较对应位置的修订号大小。具体步骤如下:
1. 计算两个列表的最小长度 minL
2. 在 minL 范围内,逐个比较两个列表对应位置的修订号大小:
- 如果相等,继续比较下一位
- 如果 version1 的修订号更大,返回 1
- 如果 version2 的修订号更大,返回 -1
3. 如果在 minL 内没有得出结果且两个列表长度相等,说明版本号相等,返回 0
4. 如果 version1 的列表更长,检查剩余位置是否存在非0修订号:
- 如果存在非0修订号,返回 1
- 如果都是0,返回 0
5. 如果 version2 的列表更长,检查剩余位置是否存在非0修订号:
- 如果存在非0修订号,返回 -1
- 如果都是0,返回 0
时间复杂度:
O(max(m,n))
空间复杂度:
O(m+n)
代码细节讲解
🦆
在比较修订号时,为什么选择直接转换为整数进行比较,而不是比较字符串形式?
▷🦆
解题思路中提到在比较结束后检查剩余位置的修订号,这个步骤是否可以通过提前终止循环来优化,以避免不必要的比较?
▷🦆
题解中提到如果两个版本号的修订号长度不同,会检查长版本号中剩余的修订号是否全为0。请问这一步是否可以并行处理以提高效率?
▷🦆
当版本号中存在多个连续的0时(如'1.0.0.0.0'),题解中的算法是否进行了优化以跳过这些不必要的比较?
▷