长大后想做什么？做回小孩！

0%

LeetCode——比较版本号

发表于 分类于 Valine：
本文字数： 271

NO.165 比较版本号 中等

YnrluT.png

YnrMvV.png

思路一：分割转换 按照 “.” 将两个版本号分割，将每段分别 atoi 之后比较。

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
public int compareVersion(String version1, String version2) {
    //分割,注意转义字符
    String[] strs1 = version1.split("\\.");
    String[] strs2 = version2.split("\\.");
    int len1 = strs1.length, len2 = strs2.length;
    int len = Math.max(len1, len2);
    //每段数字分别 atoi 之后比较
    for (int i = 0; i < len; i++) {
        int x = i < len1 ? Integer.parseInt(strs1[i]) : 0;
        int y = i < len2 ? Integer.parseInt(strs2[i]) : 0;
        int res = compare(x, y);
        if (res != 0) return res;
    }
    return 0;
}

private int compare(int x, int y) {
    if (x == y) {
        return 0;
    } else if (x > y) {
        return 1;
    } else {
        return -1;
    }
}

时间复杂度：O(n+m+Max(n,m)) n和m分别是输入字符串的长度。

空间复杂度：O(n+m)

思路二：改进思路一 思路一使用 parseInt() 进行 atoi 的转换，可能会出现整形溢出的情况。每个子串手动从高位向低位比较即可。

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
public int compareVersion(String version1, String version2) {
    String[] strs1 = version1.split("\\.");
    String[] strs2 = version2.split("\\.");
    int len1 = strs1.length, len2 = strs2.length;
    int len = Math.max(len1, len2);
    for (int i = 0; i < len; i++) {
        String x = i < len1 ? strs1[i] : "0";
        String y = i < len2 ? strs2[i] : "0";
        int res = compare(x, y);
        if (res != 0) return res;
    }
    return 0;
}

private int compare(String x, String y) {
    //删去高位 0
    x = removeHead0(x);
    y = removeHead0(y);
    //比较位数
    if (x.length() > y.length()) {
        return 1;
    } else if (x.length() < y.length()) {
        return -1;
    } else {
        //位数相等,从高位开始比较
        for (int i = 0; i < x.length(); i++) {
            int sub = x.charAt(i) - y.charAt(i);
            if (sub > 0) {
                return 1;
            } else if (sub < 0) {
                return -1;
            }
        }
        return 0;
    }
}

private String removeHead0(String s) {
    int i = 0;
    while (i < s.length()) {
        if (s.charAt(i) == '0') {
            i++;
        } else {
            break;
        }
    }
    return s.substring(i);
}

时间复杂度：O(n+m+Max(n,m)) n和m分别是输入字符串的长度。

空间复杂度：O(n+m)

如果不想使用额外的空间，只要自行判断 “.” 进行分割处理就行了。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github