Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.
Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 13.37
这道题的要求是比较两个版本号：如果version1大于version2，返回1；如果version2大于version1，返回-1。其中版本号字符串非空且仅包含数字和‘.’，‘.’用于分隔数字。
根据‘.’对版本号进行切割，然后逐个比较每组对应的版本号。由于版本号的数量可能不同（‘.’数目不同），因此需要先比较左面的部分直到某个字符串结束，接下来检测剩余的部分是否存在非0版本号即可。
时间复杂度：O(n)
空间复杂度：O(n)
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution
{
public:
int compareVersion(string version1, string version2)
{
vector<string> vs1 = split(version1, ".");
vector<string> vs2 = split(version2, ".");
// 左对齐，逐个比较对应版本号，直到一个字符串结束
int l = min(vs1.size(), vs2.size());
for(int i = 0; i < l; ++ i)
{
int a1 = atoi(vs1[i].c_str());
int a2 = atoi(vs2[i].c_str());
if(a1 > a2)
return 1;
if(a1 < a2)
return -1;
}
//如果第一个字符串有剩余非0版本号，返回1
for(int i = l; i < vs1.size(); ++ i)
if(atoi(vs1[i].c_str()) != 0)
return 1;
//如果第二个字符串有剩余非0版本号，返回-1
for(int i = l; i < vs2.size(); ++ i)
if(atoi(vs2[i].c_str()) != 0)
return -1;
return 0;
}
private:
// 以t为分隔符切割字符串s
vector<string> split(const string &s, const string &t)
{
vector<string> vs;
int b = 0, i = s.find_first_of(t, b);
while(i != -1)
{
vs.push_back(s.substr(b, i - b));
b = i + 1;
i = s.find_first_of(t, b);
}
if(b < s.length())
vs.push_back(s.substr(b));
return vs;
}
};
其实可以边切割字符串边生成版本号数字，这样代码会简短很多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
int compareVersion(string version1, string version2)
{
int n1 = version1.size(), n2 = version2.size(), num1 = 0, num2 = 0;
for(int i = 0, j = 0; i < n1 || j < n2; ++ i, ++ j)
{
while(i < n1 && version1[i] != '.')
num1 = num1 * 10 + (version1[i ++] - '0');
while(j < n2 && version2[j] != '.')
num2 = num2 * 10 + (version2[j ++] - '0');
if(num1 > num2)
return 1;
if(num1 < num2)
return -1;
num1 = num2 = 0;
}
return 0;
}
};