LeetCode 165. 比較版本號 - 優雅Java解決方案

題目描述

給你兩個 版本號字符串 version1 和 version2 ，請你比較它們。版本號由被點 ‘.’ 分開的修訂號組成。修訂號的值是它轉換為整數并忽略前導零。

比較版本號時，請按從左到右的順序依次比較它們的修訂號。如果其中一個版本字符串的修訂號較少，則將缺失的修訂號視為 0。

返回規則：

• 如果 version1 < version2 返回 -1
• 如果 version1 > version2 返回 1
• 除此之外返回 0

示例分析

示例 1

輸入：version1 = "1.2", version2 = "1.10"
輸出：-1
解釋：version1 的第二個修訂號為 "2"，version2 的第二個修訂號為 "10"：2 < 10，所以 version1 < version2

示例 2

輸入：version1 = "1.01", version2 = "1.001"
輸出：0
解釋：忽略前導零，"01" 和 "001" 都代表相同的整數 "1"

示例 3

輸入：version1 = "1.0", version2 = "1.0.0.0"
輸出：0
解釋：version1 有更少的修訂號，每個缺失的修訂號按 "0" 處理

算法思路

1. 分割版本號：使用點號分割版本號字符串
2. 雙指針遍歷：使用兩個指針分別遍歷兩個版本號的修訂號數組
3. 逐個比較：從左到右比較對應位置的修訂號
4. 處理邊界：當某個版本號的修訂號用完時，將其視為0
5. 返回結果：根據比較結果返回相應值

Java實現方案

方案一：雙指針法（推薦）

public class Solution {public int compareVersion(String version1, String version2) {String[] v1 = version1.split("\\.");String[] v2 = version2.split("\\.");int maxLength = Math.max(v1.length, v2.length);for (int i = 0; i < maxLength; i++) {int num1 = i < v1.length ? Integer.parseInt(v1[i]) : 0;int num2 = i < v2.length ? Integer.parseInt(v2[i]) : 0;if (num1 < num2) {return -1;} else if (num1 > num2) {return 1;}}return 0;}
}

方案二：優化的單次遍歷法

public class Solution {public int compareVersion(String version1, String version2) {int i = 0, j = 0;int n1 = version1.length(), n2 = version2.length();while (i < n1 || j < n2) {int num1 = 0, num2 = 0;// 解析version1的當前修訂號while (i < n1 && version1.charAt(i) != '.') {num1 = num1 * 10 + (version1.charAt(i) - '0');i++;}i++; // 跳過點號// 解析version2的當前修訂號while (j < n2 && version2.charAt(j) != '.') {num2 = num2 * 10 + (version2.charAt(j) - '0');j++;}j++; // 跳過點號if (num1 < num2) {return -1;} else if (num1 > num2) {return 1;}}return 0;}
}

可視化執行過程

讓我們通過示例來可視化算法的執行過程：

示例：compareVersion(“1.2”, “1.10”)

初始狀態:
version1 = "1.2"    →  ["1", "2"]
version2 = "1.10"   →  ["1", "10"]第1輪比較:
位置 i=0: num1=1, num2=1
1 == 1  →  繼續第2輪比較:
位置 i=1: num1=2, num2=10  
2 < 10  →  返回 -1結果: -1 (version1 < version2)

示例：compareVersion(“1.01”, “1.001”)

初始狀態:
version1 = "1.01"   →  ["1", "01"]   →  [1, 1]
version2 = "1.001"  →  ["1", "001"]  →  [1, 1]第1輪比較:
位置 i=0: num1=1, num2=1
1 == 1  →  繼續第2輪比較:
位置 i=1: num1=1, num2=1 (忽略前導零)
1 == 1  →  繼續所有修訂號都相等
結果: 0 (version1 == version2)

示例：compareVersion(“1.0”, “1.0.0.0”)

初始狀態:
version1 = "1.0"      →  ["1", "0"]
version2 = "1.0.0.0"  →  ["1", "0", "0", "0"]第1輪比較:
位置 i=0: num1=1, num2=1
1 == 1  →  繼續第2輪比較:
位置 i=1: num1=0, num2=0
0 == 0  →  繼續第3輪比較:
位置 i=2: num1=0(缺失視為0), num2=0
0 == 0  →  繼續第4輪比較:
位置 i=3: num1=0(缺失視為0), num2=0
0 == 0  →  繼續所有修訂號都相等
結果: 0 (version1 == version2)

算法復雜度分析

時間復雜度：O(max(m, n))

• m 和 n 分別是兩個版本號的修訂號個數
• 需要遍歷較長版本號的所有修訂號

空間復雜度：

• 方案一：O(m + n) - 需要存儲分割后的數組
• 方案二：O(1) - 只使用常數額外空間

測試用例

public class TestCompareVersion {public static void main(String[] args) {Solution solution = new Solution();// 測試用例1System.out.println(solution.compareVersion("1.2", "1.10"));      // -1// 測試用例2  System.out.println(solution.compareVersion("1.01", "1.001"));    // 0// 測試用例3System.out.println(solution.compareVersion("1.0", "1.0.0.0"));   // 0// 邊界測試System.out.println(solution.compareVersion("0.1", "1.1"));       // -1System.out.println(solution.compareVersion("1.0.1", "1"));       // 1System.out.println(solution.compareVersion("7.5.2.4", "7.5.3")); // -1}
}

關鍵要點總結

1. 忽略前導零：使用 Integer.parseInt() 自動處理
2. 處理不同長度：缺失的修訂號視為0
3. 效率優化：方案二避免了字符串分割的開銷
4. 邊界處理：正確處理版本號末尾的點號和空修訂號

這個解決方案具有良好的可讀性和效率，能夠正確處理所有邊界情況。