LeetCode题练习与总结：比较版本号--165

一、题目描述

给你两个 版本号字符串 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 都是 有效版本号
• version1 和 version2 的所有修订号都可以存储在 32 位整数 中

二、解题思路

1. 将两个版本号字符串按照点号 ‘.’ 分割成修订号数组。

2. 比较两个数组对应位置的修订号：

• 转换修订号为整数时，忽略前导零。
• 如果某个版本号的数组较短，将缺失的修订号视为 0。

3. 按从左到右的顺序比较修订号：

• 如果当前修订号 version1 < version2，返回 -1。
• 如果当前修订号 version1 > version2，返回 1。
• 如果所有修订号都相等，返回 0。

三、具体代码

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        
        for (int i = 0; i < Math.max(v1.length, v2.length); i++) {
            int num1 = i < v1.length ? Integer.parseInt(v1[i]) : 0;
            int num2 = i < v2.length ? Integer.parseInt(v2[i]) : 0;
            
            if (num1 < num2) {
                return -1;
            } else if (num1 > num2) {
                return 1;
            }
        }
        
        return 0;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• split("\\.") 方法将每个版本号字符串分割成数组，这个操作的时间复杂度是 O(n + m)，其中 n 是 version1 的长度，m 是 version2 的长度。因为每个字符都会被扫描一次来确定 ‘.’ 的位置。
• Math.max(v1.length, v2.length) 的时间复杂度是 O(1)，因为这是常数时间操作。
• 循环中的操作（包括 Integer.parseInt 和比较操作）会执行 Math.max(v1.length, v2.length) 次，因此这部分的时间复杂度是 O(max(n, m))。

综上所述，总的时间复杂度是 O(n + m)，其中 n 是 version1 的长度，m 是 version2 的长度。

2. 空间复杂度

• split("\\.") 方法为每个版本号创建一个新的数组，每个数组的大小取决于 ‘.’ 的数量。在最坏的情况下，每个版本号可能只有一个数字，没有 ‘.’，这将导致数组大小与版本号长度相同。因此，空间复杂度是 O(n + m)，其中 n 是 version1 的长度，m 是 version2 的长度。

综上所述，总的空间复杂度是 O(n + m)，其中 n 是 version1 的长度，m 是 version2 的长度。

注意：这里的 n 和 m 是指版本号字符串的长度，而不是分割后数组的大小。在实际应用中，版本号通常不会非常长，因此这些操作的时间复杂度和空间复杂度都是可以接受的。

五、总结知识点

1. 字符串分割：使用 split("\\.") 方法将版本号字符串按照点号 ‘.’ 分割成数组。这里的 \\ 是因为 ‘.’ 在正则表达式中是一个特殊字符，表示任意字符，所以需要使用反斜杠进行转义。

2. 数组操作：通过循环和数组索引来访问数组的元素。在本代码中，使用了 split 方法生成的数组，并通过索引 i 来获取对应的修订号。

3. 整数转换：使用 Integer.parseInt 方法将字符串转换为整数。这个方法会忽略字符串前导的零。

4. 条件语句：使用了三元操作符 ?: 来进行条件判断，简化了代码。如果条件为真，返回冒号前的值，否则返回冒号后的值。

5. 循环控制：使用 for 循环来遍历数组，直到达到两个数组中较长者的长度。

6. 数学运算：使用 Math.max 方法来获取两个长度的最大值，以确定循环的次数。

7. 返回值：根据比较结果返回整数 -1、0 或 1，这符合题目要求的返回规则。

8. 函数定义：整个代码定义了一个名为 compareVersion 的公共方法，这是解决问题的关键部分，它接受两个字符串参数并返回一个整数值。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。