LeetCode_Array_228. Summary Ranges 彙總區間（C++/Java）

目錄

​​1，題目描述​​

​​英文描述​​

​​中文描述​​

​​2，解題思路​​

​​3，AC代碼​​

​​C++​​

​​Java​​

​​4，解題過程​​

​​第一博​​

1，題目描述

原題連結​​228. 彙總區間​​

英文描述

You are given a sorted unique integer array nums.

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

"a->b" if a != b

"a" if a == b

Example 1:

Input: nums = [0,1,2,4,5,7]

Output: ["0->2","4->5","7"]

Explanation: The ranges are:

[0,2] --> "0->2"

[4,5] --> "4->5"

[7,7] --> "7"

Example 2:

Input: nums = [0,2,3,4,6,8,9]

Output: ["0","2->4","6","8->9"]

Explanation: The ranges are:

[0,0] --> "0"

[2,4] --> "2->4"

[6,6] --> "6"

[8,9] --> "8->9"

Example 3:

Input: nums = []

Output: []

Example 4:

Input: nums = [-1]

Output: ["-1"]

Example 5:

Input: nums = [0]

Output: ["0"]

Constraints:

0 <= nums.length <= 20

-231 <= nums[i] <= 231 - 1

All the values of nums are unique.

中文描述

給定一個無重複元素的有序整數數組 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"

示例 3：

輸入：nums = []

輸出：[]

示例 4：

輸入：nums = [-1]

輸出：["-1"]

示例 5：

輸入：nums = [0]

輸出：["0"]

提示：

0 <= nums.length <= 20

-231 <= nums[i] <= 231 - 1

nums 中的所有值都 互不相同

連結：https://leetcode-cn.com/problems/summary-ranges

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2，解題思路

直接周遊，找到一段連續的整數，将區間兩端轉換為字元串進行拼接。（這居然是中等難度。。。）

3，AC代碼

C++

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        for(int index = 0; index < nums.size(); index++) {
            int start = nums[index];
            while(index + 1 < nums.size() && nums[index] + 1 == nums[index + 1]) {
                index++;
            }
            if(start != nums[index]) 
                ans.push_back(to_string(start) + "->" + to_string(nums[index]));
            else 
                ans.push_back(to_string(start));
        }
        return ans;
    }
};      

Java

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ans = new ArrayList<>();
        for(int index = 0; index < nums.length; index++) {
            int start = nums[index];
            while(index + 1 < nums.length && nums[index] + 1 == nums[index + 1]) {
                index++;
            }
            if(start != nums[index])
                ans.add(start + "->" + nums[index]);
            else
                ans.add(start + "");
        }
        return ans;

    }
}      

貼一個100%的Java代碼，暫時沒看懂，以後再研究吧

class Solution {
    public List<String> summaryRanges(int[] nums) {

        if (nums == null || nums.length == 0) {
            return new ArrayList();
        }
        List<String> strs = new ArrayList(nums.length);
        int startPosition = 0;
        int i = 1;
        StringBuilder builder=new StringBuilder();
        for (; i < nums.length; i++) {
            if (nums[i] != nums[i - 1] + 1) {
                if (startPosition == i - 1) {
                    strs.add(String.valueOf(nums[startPosition]));
                } else {
                    builder.append(nums[startPosition]);
                    builder.append("->");
                    builder.append(nums[i - 1]);
                    strs.add(builder.toString());
                    builder.delete(0,builder.length());
                }
                startPosition = i;
            }
        }
        if (startPosition == i - 1) {
            strs.add(String.valueOf(nums[startPosition]));
        } else {
            builder.append(nums[startPosition]);
            builder.append("->");
            builder.append(nums[i - 1]);
            strs.add(builder.toString());
            builder.delete(0,builder.length());
        }

        return strs;
    }
}      

4，解題過程

第一博

for循環周遊，拼接相鄰的區間