leetcode
leetcode 151 ~ 200
比较版本号

比较版本号

难度:

标签:

题目描述

给你两个版本号 version1version2 ,请你比较它们。

版本号由一个或多个修订号组成,各修订号由一个 '.' 连接。每个修订号由 多位数字 组成,可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推。例如,2.5.330.1 都是有效的版本号。

比较版本号时,请按从左到右的顺序依次比较它们的修订号。比较修订号时,只需比较 忽略任何前导零后的整数值 。也就是说,修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号,则该修订号视为 0 。例如,版本 1.0 小于版本 1.1 ,因为它们下标为 0 的修订号相同,而下标为 1 的修订号分别为 010 < 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
  • version1version2 仅包含数字和 '.'
  • version1version2 都是 有效版本号
  • version1version2 的所有修订号都可以存储在 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)

代码细节讲解

🦆
在比较修订号时,为什么选择直接转换为整数进行比较,而不是比较字符串形式?
当比较修订号时,直接转换为整数进行比较而不使用字符串形式的主要原因是数字中的前导零和数字的位数。例如,修订号 '001' 和 '1' 在字符串比较下会被视为不同,但实际上它们代表相同的数值。转换为整数后,这两个修订号都会变为1,从而正确反映出它们的等价性。此外,整数比较可以直接利用数值大小,是处理版本号比较的自然和直观方法。
🦆
解题思路中提到在比较结束后检查剩余位置的修订号,这个步骤是否可以通过提前终止循环来优化,以避免不必要的比较?
在当前算法中,如果在最小长度范围内没有得出比较结果,我们检查剩余的修订号是否全为0来决定结果。这一步骤实际上是必需的,因为只有遍历完这些剩余的修订号后,才能确保它们是否对最终的比较结果有影响。例如,如果剩余的所有修订号均为0,则它们不会改变版本号的相对大小。因此,这一步骤虽然看似增加了比较次数,但为了保证正确性,是不能省略的。
🦆
题解中提到如果两个版本号的修订号长度不同,会检查长版本号中剩余的修订号是否全为0。请问这一步是否可以并行处理以提高效率?
尽管并行处理可以在某些情况下加速计算,但在这种情况下,实际增益可能非常有限。考虑到版本号通常长度不会非常长,单线程处理这种类型的简单检查已经相当快速且高效。并行处理可能引入额外的复杂度和开销,如线程管理和同步,这可能并不划算。因此,对于这个特定问题,简单的顺序检查通常是更实用的解决方案。
🦆
当版本号中存在多个连续的0时(如'1.0.0.0.0'),题解中的算法是否进行了优化以跳过这些不必要的比较?
在当前的题解算法中,对于多个连续的0,虽然每个0都会被检查,但如果它们位于比较的最小长度之外,只会在最后的剩余部分检查中处理。如果这些0位于重要的比较区段内,例如在两个版本号的最小长度范围内,它们必须被逐个比较以保证精确性。因此,算法没有特别针对连续0进行优化,而是处理所有位数以确保比较的正确性。

相关问题