比較版本號(hào)

給你兩個(gè)版本號(hào) version1 和 version2 ，請(qǐng)你比較它們。

• 版本號(hào)由一個(gè)或多個(gè)修訂號(hào)組成，各修訂號(hào)由一個(gè) '.' 連接。每個(gè)修訂號(hào)由 多位數(shù)字 組成，可能包含 前導(dǎo)零 。每個(gè)版本號(hào)至少包含一個(gè)字符。
• 修訂號(hào)從左到右編號(hào)，下標(biāo)從 0 開始，最左邊的修訂號(hào)下標(biāo)為 0 ，下一個(gè)修訂號(hào)下標(biāo)為 1 ，以此類推。例如，2.5.33 和 0.1 都是有效的版本號(hào)。
• 比較版本號(hào)時(shí)，請(qǐng)按從左到右的順序依次比較它們的修訂號(hào)。比較修訂號(hào)時(shí)，只需比較 忽略任何前導(dǎo)零后的整數(shù)值 。也就是說(shuō)，修訂號(hào) 1 和修訂號(hào) 001 相等 。
• 如果版本號(hào)沒有指定某個(gè)下標(biāo)處的修訂號(hào)，則該修訂號(hào)視為 0 。例如，版本 1.0 小于版本 1.1 ，因?yàn)樗鼈兿聵?biāo)為 0 的修訂號(hào)相同，而下標(biāo)為 1 的修訂號(hào)分別為 0 和 1 ，0 < 1 。

返回規(guī)則如下：

如果 version1 > version2 返回 1，

如果 version1 < version2 返回 -1，

除此之外返回 0。  

• 示例 1：

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

輸出：0

解釋：忽略前導(dǎo)零，"01" 和 "001" 都表示相同的整數(shù) "1"

• 示例 2：

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

輸出：0

解釋：version1 沒有指定下標(biāo)為 2 的修訂號(hào)，即視為 "0"

• 示例 3：

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

輸出：-1

解釋：version1 中下標(biāo)為 0 的修訂號(hào)是 "0"，version2 中下標(biāo)為 0 的修訂號(hào)是 "1" 。0 < 1，所以 version1 < version2  

提示：

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

version1 和 version2 僅包含數(shù)字和 '.'

version1 和 version2 都是 有效版本號(hào)

version1 和 version2 的所有修訂號(hào)都可以存儲(chǔ)在 32 位整數(shù)

方法一：字符串切割（Java）

我們可以將版本號(hào)按照點(diǎn)號(hào)分割成修訂號(hào)，然后從左到右比較兩個(gè)版本號(hào)的相同下標(biāo)的修訂號(hào)。在比較修訂號(hào)時(shí)，需要將字符串轉(zhuǎn)換成整數(shù)進(jìn)行比較。

通過(guò)調(diào)用Java的標(biāo)準(zhǔn)庫(kù)即可實(shí)現(xiàn)字符串切割

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

時(shí)間復(fù)雜度：O（m+n）

空間復(fù)雜度：O（m+n）

方法二：雙指針（Go）

方法一需要存儲(chǔ)分割后的修訂號(hào)，為了優(yōu)化空間復(fù)雜度，我們可以在分割版本號(hào)的同時(shí)解析出修訂號(hào)進(jìn)行比較。

比較兩個(gè)版本號(hào)大小，版本號(hào)由修訂號(hào)組成，中間使用'.'分隔，越靠近字符串前邊，修訂號(hào)的優(yōu)先級(jí)越大。當(dāng)v1 > v2時(shí)返回 1，當(dāng)v1 < v2時(shí)返回 -1，相等時(shí)返回 0。

我們使用兩個(gè)指針i和j分別指向兩個(gè)字符串的開頭，然后向后遍歷，當(dāng)遇到小數(shù)點(diǎn)'.'時(shí)停下來(lái)，并將每個(gè)小數(shù)點(diǎn)'.'分隔開的修訂號(hào)解析成數(shù)字進(jìn)行比較，越靠近前邊，修訂號(hào)的優(yōu)先級(jí)越大。根據(jù)修訂號(hào)大小關(guān)系，返回相應(yīng)的數(shù)值。

算法具體流程：

• 1、定義兩個(gè)指針 i和j，初始化i = 0，j = 0。
• 2、兩個(gè)指針?lè)謩e遍歷兩個(gè)字符串，將每個(gè)小數(shù)點(diǎn)'.'分隔開的修訂號(hào)解析成數(shù)字，并進(jìn)行大小比較：
  • 如果 num1 > num2，返回 1；
  • 如果 num1 < num2，返回 -1；
• 3、i++，j++，兩個(gè)指針都后移一步，進(jìn)行下一輪的修訂號(hào)解析比較。
• 4、如果遍歷完兩個(gè)字符串都沒有返回相應(yīng)結(jié)果，說(shuō)明兩個(gè)字符串相等，返回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++ // 跳過(guò)點(diǎn)號(hào)
        y := 0
        for ; j < m && version2[j] != '.'; j++ {
            y = y*10 + int(version2[j]-'0')
        }
        j++ // 跳過(guò)點(diǎn)號(hào)
        if x > y {
            return 1
        }
        if x < y {
            return -1
        }
    }
    return 0
}

時(shí)間復(fù)雜度：O（m+n）

空間復(fù)雜度：O（1）

以上就是Go Java算法之比較版本號(hào)方法詳解的詳細(xì)內(nèi)容，更多關(guān)于Go Java算法比較版本號(hào)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論