leetcode-165-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.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

分析

解决方案1(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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    int compareVersion(string version1, string version2) {
        vector<int> result1 = getInt(version1);
		vector<int> result2 = getInt(version2);
		int len1 = result1.size();
		int len2 = result2.size();
		// cout << "len1:" << len1 << endl;
		// cout << "len2:" << len2 << endl;

		if(len2 < len1) {
			return -1 * compareVersion(version2, version1);
		}
		// version2的长度不比version1的长度短
		int i = 0;
		for( ; i < len1 && result1[i] == result2[i]; i++);
		if(i == len1) {   // 如果str2后面的len2-len1都为0，一样，如果不是，str2大，返回-1
			int j = len2-1;
			while(j >= len1) {
				if(result2[j--] != 0) {
					return -1;
				}
			}
			return 0;
		}else {
			if(result1[i] < result2[i]) {
				return -1;
			}else {
				return 1;
			}
		}
    }
private:
	vector<int> getInt(string version) {
		vector<int> result;
		int len = version.size();
		int numHead = 0;
		for(int i = 0; i < len; i++) {
			if(version[i] == '.') { 
				string str(version.begin()+numHead, version.begin()+i);    // 左开右闭区间
				result.push_back(stoi(str));
				numHead = i + 1;
			}
		}
		string str(version.begin()+numHead, version.end());
		result.push_back(stoi(str));
		// cout << stoi(str) << endl;
		return result;
	}

};

解决方案2(Golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func compareVersion(version1 string, version2 string) int {
    v1Slice := strings.Split(version1, ".")
    v2Slice := strings.Split(version2, ".")
    
    for i := 0; i < len(v1Slice) || i < len(v2Slice); i++ {
        x, y := 0, 0
        if i < len(v1Slice) {
            x, _ = strconv.Atoi(v1Slice[i])
        }
        if i < len(v2Slice) {
            y, _ = strconv.Atoi(v2Slice[i])
        }
        if x > y {
            return 1
        }
        if x < y {
            return -1
        }
    }
    
    return 0
}

题目来源