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:

1
0.1 < 1.1 < 1.2 < 13.37

分治法

思路就是先获取.前面的一部分, 比较, 如果相同, 再把.后面的子字符串做为一个子问题, 递归处理.

有此特殊情况需要考虑:

  1. 字符串为空, 解析为0
  2. p1和p2用来指向第一个出现的., 所以version.substring(0, p)就为第一部分, version.substring(p + 1, version.length())就为后面的部分. 如果version中不含有.的话, 那么p的默认值为version.length(). 这在取第一部分的时候没有问题, 但是后面的部分的范围应改为version.substring(p, version.length())
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
public int compareVersion(String version1, String version2) {
    if (version1.equals(version2))
        return 0;
    int p1 = version1.length(), p2 = version2.length();
    for (int i = 0; i < version1.length(); i++) {
        if (version1.charAt(i) == '.') {
            p1 = i;
            break;
        }
    }
    for (int i = 0; i < version2.length(); i++) {
        if (version2.charAt(i) == '.') {
            p2 = i;
            break;
        }
    }
    int v1 = p1 == 0 ? 0 : Integer.parseInt(version1.substring(0, p1));
    int v2 = p2 == 0 ? 0 : Integer.parseInt(version2.substring(0, p2));
    if (v1 > v2)
        return 1;
    else if (v1 < v2)
        return -1;
    else {
        if (p1 != version1.length()) {
            p1++;
        }
        if (p2 != version2.length()) {
            p2++;
        }
        return compareVersion(version1.substring(p1, version1.length()), version2.substring(p2, version2.length()));
    }
}

先把version拆解成由数字组成的数组, 再一一比较

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;
}