Go Java算法之比較版本號方法詳解
比較版本號
給你兩個版本號 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算法比較版本號的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- C++實現LeetCode165.版本比較)
- C++實現LeetCode(93.復原IP地址)
- Go Java算法之字符串中第一個唯一字符詳解
- Go&java算法之最大數示例詳解
- Java數據結構之線段樹中的懶操作詳解