go語言題解LeetCode228匯總區間示例詳解
題目描述
原題鏈接 :
228. 匯總區間
給定一個 無重復元素 的 有序 整數數組 nums
。
返回 恰好覆蓋數組中所有數字 的 最小有序 區間范圍列表 。也就是說,nums 的每個元素都恰好被某個區間范圍所覆蓋,並且不存在屬於某個范圍但不屬於 nums
的數字 x
。
列表中的每個區間范圍 [a,b]
應該按如下格式輸出:
- "a->b" ,如果 a != b
- "a" ,如果 a == b
示例 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"
提示:
0 <= nums.length <= 20
-2^31 <= nums[i] <= 2^31 – 1
- nums 中的所有值都 互不相同
- nums 按升序排列
思路分析
本題思路比較明晰,設立雙指針,一前一後遍歷數組,當遇到結果不是有序遞增,即nums[j]+1 != nums[j+1]時,中斷數組,從i,到j進行條件判斷插入字符串,插入完之後,將i移動到j後面那個位置,即i = j + 1。
本題難點在於邊界處理,因為涉及到j+1,遍歷時隻能遍歷到n-1,最後一位需要依照相同的思路重新判斷一遍,如果數組為空或者隻有一個元素,循環語句也不好判斷,因為無法與第二個元素相比較。有評論使用逃課方法,即在數組後額外安插一個整型最大值,但這樣的方法如果數組原本最後一個元素是最大值-1時,會導致結果錯誤不能使用。
AC 代碼
vector<string> summaryRanges(vector<int> &nums) { vector<string> s; if (nums.size() == 0) return s; if (nums.size() == 1) { s.push_back(to_string(nums[0])); return s; } int i = 0, j = 0, n = nums.size(); string t; for (; j < n - 1; j++) { if (nums[j] + 1 != nums[j + 1]) { if (i == j) s.push_back(to_string(nums[i])); else s.push_back(to_string(nums[i]) + "->" + to_string(nums[j])); i = j + 1; } } if (i == j) s.push_back(to_string(nums[i])); else s.push_back(to_string(nums[i]) + "->" + to_string(nums[j])); return s; }
以上就是go語言題解LeetCode228匯總區間示例詳解的詳細內容,更多關於go語言匯總區間的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- C++中vector<vector<int> >的基本使用方法
- C++實現LeetCode(312.打氣球遊戲)
- C++實現LeetCode(228.總結區間)
- C++實現LeetCode(三數之和)
- C++實現LeetCode(347.前K個高頻元素)