主題

LeetCode - 228. Summary Ranges 解題心得

Not In My Back Yard | 2021-03-08 00:00:03 | 巴幣 0 | 人氣 18

題目連結:


題目意譯:
給定你一個已排序相異整數之陣列 nums。

回傳一個已排序數字範圍之列表,其恰好覆蓋了陣列裡的所有數字。也就是說,nums 的每個數字只會被一個範圍覆蓋到,且不存在一整數 x 滿足 x 在其中一個數字範圍中但不在 nums 中。

每個範圍 [a,b] 於列表中應表為:
"a->b",如果 a != b
"a",如果 a == b

限制:
0 ≦ nums.length ≦ 20
-2 ^ 31 ≦ nums[i] ≦ 2 ^ 31 - 1
nums 中的所有值皆相異。
nums 按照升序排列。



範例測資:
範例 1:
輸入: nums = [0,1,2,4,5,7]
輸出: ["0->2","4->5","7"]
解釋: 範圍如下:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

範例 2:
輸入: nums = [0,2,3,4,6,8,9]
輸出: ["0","2->4","6","8->9"]
解釋: 範圍如下:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

範例 3:
輸入: nums = []
輸出: []

範例 4:
輸入: nums = [-1]
輸出: ["-1"]

範例 5:
輸入: nums = [0]
輸出: ["0"]


解題思維:
掃過 nums 的每個數字 nums[i] ,然後看 nums[i] 與 nums[i - 1] 之關係。如果 nums[i] - nums[i - 1] > 1 (注意數字大小的範圍,運算可能會超過 C++ 的 int 所能容納的大小),則代表 nums[i] 與 nums[i - 1] 兩者處在不同的範圍中。

而我們在掃數字的過程中可以用一個變數 last 紀錄一個範圍的左端點(也就是開頭),當遇到上面的 nums[i] - nums[i - 1] > 1 時,代表我們找到了一個範圍 [last, nums[i - 1]]。

因此我們再去判斷 last 是否等於 nums[i - 1] ,如果是則變為 "last";反之,則變為 "last->nums[i - 1]" (如同題目要求)。

判斷完後更新 last 變為 nums[i],然後繼續尋找下一個範圍。

而最後因為 nums 的最後一個數字 M 沒有後繼者,所以不會觸發 nums[i] - M > 1 ,進而將 M 納入某一範圍中。但是該範圍必為 [last, M],所以按照上面的範圍轉換再做最後一次,然後將先前的所有範圍全部串起來即可得到所求。




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

創作回應

更多創作