go語言題解LeetCode228彙總區間範例詳解

2022-12-31 14:01:39

題目描述

原題連結 :

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語言彙總區間的資料請關注it145.com其它相關文章！

go語言題解LeetCode228彙總區間範例詳解

目錄

題目描述

思路分析

AC 程式碼

熱門文章