题目来源
题目描述
题目分析
比较两个版本号大小,版本号由修订号组成,中间使用’.'分隔,越靠近字符串前边,修订号的优先级越大。当v1 > v2时返回 1,当v1 < v2时返回 -1,相等时返回 0。
双指针
如样例所示,v1= 1.02.3, v2 = 1.02.2,前两个修订号都相等,v1的第三个修订号大于v2的第三个修订号,因此v1 > v2,返回1。下面来讲解双指针的做法。
我们使用两个指针i
和j
分别指向两个字符串的开头,然后向后遍历,当遇到小数点.
时停下来,并将每个小数点.
分隔开的修订号解析成数字进行比较,越靠近前边,修订后的优先级越大。根据修订号大小关系,返回相应的数值。
具体过程如下:
- 定义两个指针
i
和j
,初始化i = 0
,j = 0
- 两个指针分别遍历两个字符串,将每个小数点
.
分隔开的修订号解析成数字,并进行大小比较
- 如果 num1 > num2,返回 1;
- 如果 num1 < num2,返回 -1;
- i++,j++,两个指针都后移一步,进行下一轮的修订号解析比较。
- 如果遍历完两个字符串都没有返回相应结果,说明两个字符串相等,返回0。
时间复杂度分析: 两个字符串各遍历一遍,因此时间复杂度为 O(n + m)O(n+m) ,n和m分别是两个字符串的长度。
class Solution {
public:
int compareVersion(string version1, string version2) {
int len1 = version1.size(), len2 = version2.size();
int i = 0, j = 0;
while (i < len1 || j < len2){
int num1 = 0, num2 = 0;
while (i < len1 && version1[i] != '.'){
num1 = num1 * 10 + (version1[i++] - '0');
}
while (j < len2 && version2[j] != '.'){
num2 = num2 * 10 + (version2[j++] - '0');
}
if(num1 > num2){
return 1;
}else if(num1 < num2){
return -1;
}
i++;
j++;
}
return 0;
}
};
类似题目