一:题目描述:
给你两个版本号 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:
1 | 输入:version1 = "1.01", version2 = "1.001" |
示例 2:
1 | 输入:version1 = "1.0", version2 = "1.0.0" |
示例 3:
1 | 输入:version1 = "0.1", version2 = "1.1" |
提示:
1 <= version1.length, version2.length <= 500
version1
和version2
仅包含数字和'.'
version1
和version2
都是 有效版本号version1
和version2
的所有修订号都可以存储在 32 位整数 中
三:思路
split分割
- 利用split方法分割字符串为数组,[‘1’, ‘001’]
- 通过两个数组对应下标进行数值对比
- 通过paresInt将字符转换成数值,自然使得’001’和’01’数值上相同
- 但两个verison长度不同,可能version1的下标在version2中不存在,parseInt(undefined)为NAN
- 因此当取不出来对应值时,赋值为0
双指针
直接比较数字部分,不拆分字符串
当遇到.的时候,逻辑上把它们点之间的部分拆分
循环一遍,但当遇到点的时候,sum更新为0
- 这两个循环的结合使得我们能够在不拆分版本号字符串的情况下,直接在字符串上操作并比较数字部分。当两个版本号的相应部分都提取完毕并转换为数字后,就可以进行比较操作。
从头对应对比sum1和sum2值大小
四:代码 + 复杂度分析
split分割
1 | /** |
时间复杂度:
- O(max(m, n))
空间复杂度:O(n)
- 创建了两个额外的数组arr1和arr2来存储拆分结果
双指针
1 | /** |
- 时间复杂度:O(max(n + m))
- 空间复杂度:O(1)