LeetCode - Easy - 228. Summary Ranges

小灰灰 2023-01-02 06:22 121阅读 0赞

## Topic ##

*  Array
 *  Two Pointers

## Description ##

[https://leetcode.com/problems/summary-ranges/][https_leetcode.com_problems_summary-ranges]

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
 *  \-2³¹ <= nums\[i\] <= 2³¹ - 1
 *  All the values of `nums` are unique.
 *  `nums` is sorted in ascending order.

## Analysis ##

略

## Submission ##

public class SummaryRanges { 
    	
    	//方法一：我写的
    	public List<String> summaryRanges1(int[] nums) { 
    		List<String> result = new ArrayList<>();
    		if (nums == null || nums.length == 0)
    			return result;
    
    		int left = nums[0], right = nums[0];
    
    		for (int i = 1; i < nums.length; i++) { 
    			if (right + 1 == nums[i]) { 
    				right++;
    			} else { 
    				result.add(left == right ? left + "" : left + "->" + right);
    				left = right = nums[i];
    			}
    		}
    		result.add(left == right ? left + "" : left + "->" + right);
    		return result;
    	}
    
    	//方法二：别人写的，双指针
    	public List<String> summaryRanges2(int[] nums) { 
    		List<String> list = new ArrayList<>();
    		for (int i = 0; i < nums.length; i++) { 
    			int a = nums[i];
    			while (i + 1 < nums.length && nums[i + 1] - nums[i] == 1) 
    				i++;
    			list.add(a == nums[i] ? a + "" : a + "->" + nums[i]);
    		}
    		return list;
    	}
    }

## Test ##

import static org.junit.Assert.*;
    
    import org.hamcrest.collection.IsEmptyCollection;
    
    import static org.hamcrest.MatcherAssert.assertThat;
    import static org.hamcrest.collection.IsIterableContainingInOrder.contains;
    
    import org.junit.Test;
    
    public class SummaryRangesTest { 
    
    	@Test
    	public void test() { 
    		SummaryRanges obj = new SummaryRanges();
    
    		assertThat(obj.summaryRanges1(new int[] { 0, 1, 2, 4, 5, 7}), //
    				contains("0->2", "4->5", "7"));
    		assertThat(obj.summaryRanges1(new int[] { 0, 2, 3, 4, 6, 8, 9}), // 
    				contains("0","2->4","6","8->9"));
    		assertThat(obj.summaryRanges1(new int[] { }), IsEmptyCollection.empty());
    		
    		assertThat(obj.summaryRanges1(new int[] { -1}), contains("-1"));
    		assertThat(obj.summaryRanges1(new int[] { 0}), contains("0"));
    		
    		
    		assertThat(obj.summaryRanges2(new int[] { 0, 1, 2, 4, 5, 7}), //
    				contains("0->2", "4->5", "7"));
    		assertThat(obj.summaryRanges2(new int[] { 0, 2, 3, 4, 6, 8, 9}), // 
    				contains("0","2->4","6","8->9"));
    		assertThat(obj.summaryRanges2(new int[] { }), IsEmptyCollection.empty());
    		
    		assertThat(obj.summaryRanges2(new int[] { -1}), contains("-1"));
    		assertThat(obj.summaryRanges2(new int[] { 0}), contains("0"));
    		
    	}
    }

[https_leetcode.com_problems_summary-ranges]: https://leetcode.com/problems/summary-ranges/