☆打卡演算法☆LeetCode 165. 比較版本號 演算法解析

---

theme: arknights

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第25天，點選檢視活動詳情

推薦閱讀

• CSDN主頁
• GitHub開源地址
• Unity3D外掛分享
• 簡書地址
• 我的個人部落格
• QQ群：1040082875

大家好，我是小魔龍，Unity3D軟體工程師，VR、AR，虛擬模擬方向，不定時更新軟體開發技巧，生活感悟，覺得有用記得一鍵三連哦。

一、題目

1、演算法題目

“給定兩個版本號，進行比較。”

題目連結：

來源：力扣（LeetCode）

連結： 165. 比較版本號

2、題目描述

給你兩個版本號 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 = "0.1", version2 = "1.1" 輸出：-1 解釋：version1 中下標為 0 的修訂號是 "0"，version2 中下標為 0 的修訂號是 "1" 。0 < 1，所以 version1 < version2

二、解題

1、思路分析

這道題可以將版本號根據點號分割成修訂號，然後從左到右去比較版本號相同下標的修訂號。

在比較修訂號的時候，需要將字串轉換成整數進行比較。

如果版本號不存在某個下標處的修訂號，說明該修訂號為0.

2、程式碼實現

程式碼參考： csharp 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; } }

3、時間複雜度

時間複雜度：O(n + m)

其中n是版本號1的長度，m是版本號2的長度。

空間複雜度：O(n + m)

其中n是版本號1的長度，m是版本號2的長度，需要空間儲存分割後的修訂號列表。

三、總結

這道題還可以使用雙指標進行解題。

兩個指標分別指向兩個版本號下標的修訂號。

然後進行對比。