ETH官方钱包

前往
大廳
主題

LeetCode - 165. Compare Version Numbers 解題心得

Not In My Back Yard | 2022-10-06 12:00:01 | 巴幣 0 | 人氣 235

題目連結:


題目意譯:
給定兩個版本號 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.length, version2.length ≦ 500
version1 和 version2 只由數字和 '.' 所組成。
version1 和 version2 為合法的版本號。
所有 version1 和 version2 中給定的修訂號都可以儲存進一個 32 位元整數(譯注:這裡是有號整數,所以最大只會到 2147483647)。



範例測資:
範例 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。


解題思維:
先把 version1 和 version2 各自的修訂號分離出來(根據「.」來分離各個數字,並假設前者為 x 個、後者為 y 個)。

如果 x 不等於 y,則將較小的那個在結尾補 0 補到修訂號的數量一樣。

接著就跟比較字串的字典序類似——先比較兩者的 0 號修訂;一樣再比較 1 號修訂;又一樣則再比較 2 號修訂……以此類推。如果通通都一樣則回傳 0,則過程中有不同,則看是 version1 的比較大還是 version2 的修訂號比較大。如果是前者則回傳 1;後者則回傳 -1。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作