抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

一:题目描述:

给你两个版本号 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:

1
2
3
输入:version1 = "1.01", version2 = "1.001"
输出:0
解释:忽略前导零,"01" 和 "001" 都表示相同的整数 "1"

示例 2:

1
2
3
输入:version1 = "1.0", version2 = "1.0.0"
输出:0
解释:version1 没有指定下标为 2 的修订号,即视为 "0"

示例 3:

1
2
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 位整数

三:思路

split分割

  • 利用split方法分割字符串为数组,[‘1’, ‘001’]
  • 通过两个数组对应下标进行数值对比
  • 通过paresInt将字符转换成数值,自然使得’001’和’01’数值上相同
  • 但两个verison长度不同,可能version1的下标在version2中不存在,parseInt(undefined)为NAN
  • 因此当取不出来对应值时,赋值为0

双指针

  • 直接比较数字部分,不拆分字符串

  • 当遇到.的时候,逻辑上把它们点之间的部分拆分

  • 循环一遍,但当遇到点的时候,sum更新为0

    • 这两个循环的结合使得我们能够在不拆分版本号字符串的情况下,直接在字符串上操作并比较数字部分。当两个版本号的相应部分都提取完毕并转换为数字后,就可以进行比较操作。
  • 从头对应对比sum1和sum2值大小

四:代码 + 复杂度分析

split分割

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* @param {string} version1
* @param {string} version2
* @return {number}
*/
var compareVersion = function(version1, version2) {
//split分割字符串为数组
let arr1 = version1.split('.')
let arr2 = version2.split('.')
//然后将对应下标的数值进行对比大小
//有‘01’和‘001’ 转换成数值对比
let max = Math.max(arr1.length, arr2.length)
for(let i = 0; i < max; i++) {
//如果不存在对应的数值
// parseInt(undefined)是NAN 就默认取值为0
let number1 = parseInt(arr1[i]) || 0
let number2 = parseInt(arr2[i]) || 0
console.log(number1, number2)
if(number1 > number2) {
return 1
}else if(number2 > number1){
return -1
}
}
return 0
};
  • 时间复杂度:

    • O(max(m, n))
  • 空间复杂度:O(n)

    • 创建了两个额外的数组arr1和arr2来存储拆分结果

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* @param {string} version1
* @param {string} version2
* @return {number}
*/
var compareVersion = function(version1, version2) {
//双指针
//直接跳过.提取数值比大小
let i = 0
let j = 0
//外层循环用于 逻辑上分割.之间的部分
while(i < version1.length || j < version2.length) {
let sum1 = 0
let sum2 = 0
//内层循环用于将点之间的数值提取出来 加和直接进行相互比大小
while(i < version1.length && version1[i] !== '.') {
sum1 = sum1 * 10 + parseInt(version1[i])
//指针右移
i++
}
while(j < version2.length && version2[j] !== '.') {
sum2 = sum2 * 10 + parseInt(version2[j])
j++
}
if(sum1 > sum2) {
return 1
}else if(sum1 < sum2) {
return -1
}
//跳过点号
i++
j++
}
return 0
};
  • 时间复杂度:O(max(n + m))
  • 空间复杂度:O(1)

评论