题目
Compare Version Numbers 比较版本号
给你两个版本号 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 <= 500version1和version2仅包含数字和'.'version1和version2都是有效版本号version1和version2的所有修订号都可以存储在 32 位整数中
题解
字符串分割
该方法非常简单，就是利用了 split() 方法，以 '.' 分割成数组，逐一比较两个数组位于同一下标中的整数值，如果当前下标超过数组的长度（即另一数组的长度已超过当前数组），则自动补 0，如此反复，直至得出结果或循环结束。
class Solution {
fun compareVersion(version1: String, version2: String): Int {
val arr1 = version1.split("\\.".toRegex()).toTypedArray()
val arr2 = version2.split("\\.".toRegex()).toTypedArray()
for (n in 0 until max(arr1.size, arr2.size)) {
val i = if (n < arr1.size) arr1[n].toInt() else 0
val j = if (n < arr2.size) arr2[n].toInt() else 0
if (i < j) {
return -1
} else if (i > j) {
return 1
}
}
return 0
}
}
- 时间复杂度：
O(n+m)（或O(max(n,m))，这是等价的），其中n是字符串version1的长度，m是字符串version2的长度。 - 空间复杂度：
O(n+m)，我们需要O(n+m)的空间存储分割后的修订号列表。
双指针
字符串分割方法需要存储分割后的修订号，为了优化空间复杂度，我们可以在分割版本号的同时解析出修订号进行比较。
class Solution {
fun compareVersion(version1: String, version2: String): Int {
var index1 = 0
var index2 = 0
while (index1 < version1.length || index2 < version2.length) {
var curr1 = 0
while (index1 < version1.length && version1[index1] != '.') {
curr1 = curr1 * 10 + (version1[index1++] - '0')
}
index1++
var curr2 = 0
while (index2 < version2.length && version2[index2] != '.') {
curr2 = curr2 * 10 + (version2[index2++] - '0')
}
index2++
if (curr1 != curr2) {
return if (curr1 < curr2) -1 else 1
}
}
return 0
}
}
该方法相比字符串分割的方法看起来相对繁琐一点，但性能会更优。我们不再使用 split() 方法分割数组，而是遍历字符串中每一个字符来计算。
index1 和 index2 为当前处理的字符位于字符串 version1 和 version2 中的下标，遍历两个字符串，curr1 和 curr2 用来记录 '.' 分割的每一段的版本号，因为循环是从左往右读取，所以当超过 1 位数字的情况下对前一个结果乘 10 再相加，以此计算出该段的结果。
这里用了 version[index++] - '0' 这个写法可能不太好理解，实际上就是取当前字符的 ASCII 值进行运算，这算是一个取巧的设计，因为在 ASCII 中，0 到 9 也是连续的，所以只要当前字符与 '0' 相减，就可以得出该值的整型结果，而无需做 Char.digitToInt() 的转换。另外需要注意 index 是在该运算结束之后才执行自增操作。
当该小循环结束，也就意味着以 '.' 分割的该小段计算结束，index 再执行一次自增以跳过 '.' 字符等待下个大循环的计算。两个字符串都以此方式计算每一小段的结果，直至能够比较出结果为止。
- 时间复杂度：
O(n+m)，其中n是字符串version1的长度，m是字符串version2的长度。 - 空间复杂度：
O(1)，我们只需要常数的空间保存若干变量。
