Go Java演演算法之比較版本號方法詳解

2022-08-10 22:00:48

比較版本號

給你兩個版本號 version1 和 version2 ，請你比較它們。

版本號由一個或多個修訂號組成，各修訂號由一個 '.' 連線。每個修訂號由多位數位組成，可能包含前導零。每個版本號至少包含一個字元。
修訂號從左到右編號，下標從 0 開始，最左邊的修訂號下標為 0 ，下一個修訂號下標為 1 ，以此類推。例如，2.5.33 和 0.1 都是有效的版本號。
比較版本號時，請按從左到右的順序依次比較它們的修訂號。比較修訂號時，只需比較忽略任何前導零後的整數值。也就是說，修訂號 1 和修訂號 001 相等。
如果版本號沒有指定某個下標處的修訂號，則該修訂號視為 0 。例如，版本 1.0 小於版本 1.1 ，因為它們下標為 0 的修訂號相同，而下標為 1 的修訂號分別為 0 和 1 ，0 < 1 。

返回規則如下：

如果 version1 > version2 返回 1，

如果 version1 < version2 返回 -1，

除此之外返回 0。

範例 1：

輸入：version1 = "1.01", version2 = "1.001"

輸出：0

解釋：忽略前導零，"01" 和 "001" 都表示相同的整數 "1"

範例 2：

輸入：version1 = "1.0", version2 = "1.0.0"

輸出：0

解釋：version1 沒有指定下標為 2 的修訂號，即視為 "0"

範例 3：

輸入：version1 = "0.1", version2 = "1.1"

輸出：-1

解釋：version1 中下標為 0 的修訂號是 "0"，version2 中下標為 0 的修訂號是 "1" 。0 < 1，所以 version1 < version2

提示：

1 <= version1.length, version2.length <= 500

version1 和 version2 僅包含數位和 '.'

version1 和 version2 都是有效版本號

version1 和 version2 的所有修訂號都可以儲存在 32 位整數

方法一：字串切割（Java）

我們可以將版本號按照點號分割成修訂號，然後從左到右比較兩個版本號的相同下標的修訂號。在比較修訂號時，需要將字串轉換成整數進行比較。

通過呼叫Java的標準庫即可實現字串切割

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\.");
        String[] v2 = version2.split("\.");
        for (int i = 0; i < v1.length || i < v2.length; ++i) {
            int x = 0, y = 0;
            if (i < v1.length) {
                x = Integer.parseInt(v1[i]);
            }
            if (i < v2.length) {
                y = Integer.parseInt(v2[i]);
            }
            if (x > y) {
                return 1;
            }
            if (x < y) {
                return -1;
            }
        }
        return 0;
    }
}

時間複雜度：O（m+n）

空間複雜度：O（m+n）

方法二：雙指標（Go）

方法一需要儲存分割後的修訂號，為了優化空間複雜度，我們可以在分割版本號的同時解析出修訂號進行比較。

比較兩個版本號大小，版本號由修訂號組成，中間使用'.'分隔，越靠近字串前邊，修訂號的優先順序越大。當v1 > v2時返回 1，當v1 < v2時返回 -1，相等時返回 0。

我們使用兩個指標i和j分別指向兩個字串的開頭，然後向後遍歷，當遇到小數點'.'時停下來，並將每個小數點'.'分隔開的修訂號解析成數位進行比較，越靠近前邊，修訂號的優先順序越大。根據修訂號大小關係，返回相應的數值。

演演算法具體流程：

1、定義兩個指標 i和j，初始化i = 0，j = 0。
2、兩個指標分別遍歷兩個字串，將每個小數點'.'分隔開的修訂號解析成數位，並進行大小比較：
- 如果 num1 > num2，返回 1；
- 如果 num1 < num2，返回 -1；
3、i++，j++，兩個指標都後移一步，進行下一輪的修訂號解析比較。
4、如果遍歷完兩個字串都沒有返回相應結果，說明兩個字串相等，返回0。

func compareVersion(version1, version2 string) int {
    n, m := len(version1), len(version2)
    i, j := 0, 0
    for i < n || j < m {
        x := 0
        for ; i < n && version1[i] != '.'; i++ {
            x = x*10 + int(version1[i]-'0')
        }
        i++ // 跳過點號
        y := 0
        for ; j < m && version2[j] != '.'; j++ {
            y = y*10 + int(version2[j]-'0')
        }
        j++ // 跳過點號
        if x > y {
            return 1
        }
        if x < y {
            return -1
        }
    }
    return 0
}

時間複雜度：O（m+n）

空間複雜度：O（1）

以上就是Go Java演演算法之比較版本號方法詳解的詳細內容，更多關於Go Java演演算法比較版本號的資料請關注it145.com其它相關文章！

Go Java演演算法之比較版本號方法詳解

目錄

比較版本號

方法一：字串切割（Java）

方法二：雙指標（Go）

熱門文章