165. Compare Version Numbers

  • 20.1%

https://leetcode.com/problems/compare-version-numbers/

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.

1
2
3
Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

方法一:

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int compareVersion(string version1, string version2) {
int i = 0, j = 0;
int num1 = 0, num2 = 0;
int n1 = version1.size(), n2 = version2.size();
while(i<n1 || j<n2){
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;
else if(num1<num2)
return -1;
num1 = 0;
num2 = 0;
i++; j++;
}
return 0;
}
};

按照最简单的逻辑去做就行了。

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
int compareVersion(string version1, string version2) {
int i = 0;
int j = 0;
int n1 = version1.size();
int n2 = version2.size();

int num1 = 0;
int num2 = 0;
while(i<n1 || j<n2) // 此处用 ||,考虑1.0.1与1的情况
{
while(i<n1 && version1[i]!='.'){
num1 = num1*10+(version1[i]-'0');
i++;
}

while(j<n2 && version2[j]!='.'){
num2 = num2*10+(version2[j]-'0');;
j++;
}

if(num1>num2) return 1;
else if(num1 < num2) return -1;

num1 = 0;
num2 = 0;
i++;
j++;
}

return 0;
}

cpp

https://discuss.leetcode.com/topic/11410/my-2ms-easy-solution-with-c-c

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
int compareVersion(string version1, string version2) {
int i = 0;
int j = 0;
int n1 = version1.size();
int n2 = version2.size();

int num1 = 0;
int num2 = 0;
while(i<n1 || j<n2)
{
while(i<n1 && version1[i]!='.'){
num1 = num1*10+(version1[i]-'0');
i++;
}

while(j<n2 && version2[j]!='.'){
num2 = num2*10+(version2[j]-'0');;
j++;
}

if(num1>num2) return 1;
else if(num1 < num2) return -1;

num1 = 0;
num2 = 0;
i++;
j++;
}

return 0;
}

https://discuss.leetcode.com/topic/6266/my-solutions-in-3-languages

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int compareVersion(string version1, string version2) {
for (; version1 != version2; version1 = nextSubstr(version1), version2 = nextSubstr(version2)) {
int gap = stoi(version1) - stoi(version2);
if (gap != 0) {
return gap > 0 ? 1 : -1;
}
}
return 0;
}

string nextSubstr(string str) {
for (int i = 0; i < str.size(); i++) {
if (str.at(i) == '.') {
return str.substr(i + 1);
}
}
return "0";
}
};

https://discuss.leetcode.com/topic/8257/10-line-concise-solution-c

This is a concise solution using stringstream to format string into int.

1
2
3
4
5
6
7
8
9
10
11
12
13
int compareVersion(string version1, string version2) {
for(auto& w : version1) if (w == '.') w=' ';
for(auto& w : version2) if (w == '.') w=' ';
istringstream s1(version1), s2(version2);
while(1) {
int n1,n2;
if (not(s1 >> n1) ) n1 = 0;
if (not(s2 >> n2) ) n2 = 0;
if (not s1 and not s2) return 0;
if (n1<n2) return -1;
if (n1>n2) return 1;
}
}

python

https://discuss.leetcode.com/topic/6266/my-solutions-in-3-languages

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def compareVersion(self, version1, version2):
"""
:type version1: str
:type version2: str
:rtype: int
"""
v1 = version1.split('.')
v2 = version2.split('.')
for i in range(max(len(v1), len(v2))):
gap = (int(v1[i]) if i < len(v1) else 0) - (int(v2[i]) if i < len(v2) else 0)
if gap != 0:
return 1 if gap > 0 else -1
return 0

https://discuss.leetcode.com/topic/18543/2-4-lines-python-3-different-ways

Solution 1: Pad with izip_longest with fillvalue=0

1
2
3
def compareVersion(self, version1, version2):
splits = (map(int, v.split('.')) for v in (version1, version2))
return cmp(*zip(*itertools.izip_longest(*splits, fillvalue=0)))

Solution 2: Pad with [0] * lengthDifference

1
2
3
4
def compareVersion(self, version1, version2):
v1, v2 = (map(int, v.split('.')) for v in (version1, version2))
d = len(v2) - len(v1)
return cmp(v1 + [0]*d, v2 + [0]*-d)

Solution 3: Recursive, add zeros on the fly

1
2
3
4
5
def compareVersion(self, version1, version2):
main1, _, rest1 = ('0' + version1).partition('.')
main2, _, rest2 = ('0' + version2).partition('.')
return cmp(int(main1), int(main2)) or \
len(rest1+rest2) and self.compareVersion(rest1, rest2)

java

https://discuss.leetcode.com/topic/6238/accepted-small-java-solution

This code assumes that next level is zero if no mo levels in shorter version number. And than compare levels.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int compareVersion(String version1, String version2) {
String[] levels1 = version1.split("\\.");
String[] levels2 = version2.split("\\.");

int length = Math.max(levels1.length, levels2.length);
for (int i=0; i<length; i++) {
Integer v1 = i < levels1.length ? Integer.parseInt(levels1[i]) : 0;
Integer v2 = i < levels2.length ? Integer.parseInt(levels2[i]) : 0;
int compare = v1.compareTo(v2);
if (compare != 0) {
return compare;
}
}

return 0;
}

https://discuss.leetcode.com/topic/6266/my-solutions-in-3-languages

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public int compareVersion(String version1, String version2) {
String[] v1 = version1.split("\\.");
String[] v2 = version2.split("\\.");
for(int i=0; i<Math.max(v1.length, v2.length); i++){
int gap = (i < v1.length ? Integer.parseInt(v1[i]) : 0) - (i < v2.length ? Integer.parseInt(v2[i]) : 0);
if(gap != 0)
return gap > 0 ? 1 : -1;
}
return 0;
}
}

谢谢你,可爱的朋友。