leetcode Question: Summary Ranges

Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

Analysis:


This is an easy question. Since the ranges are all continuous integers, we just need scan the whole array, compare each element with its previous one, if they are not continuous numbers, the current number must belong a new range. In my code, the start and end of the current range is kept in each iteration, don't forget the case that only one number can become a range and the output format is slight different required in this question.

Code(C++):

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

Code(Python):

class Solution(object):
    def summaryRanges(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        if len(nums) == 0:
            return []
            
        res = []
        
        st = nums[0]
        ed = nums[0]
        
        for num in nums[1::]:
            if ed + 1 != num:
                if st == ed:
                    res.append(str(st))
                else:
                    res.append(str(st) + "->" + str(ed))
                st = num
                ed = num
            else:
                ed = num
        if st == ed:
            res.append(str(st))
        else:
            res.append(str(st) + "->" + str(ed))
            
        return res

1 comment:

  1. I tried similar y no work

    const arr = [0,1,2,4,5,7,8,9,10,11,13]

    function summarize(A) {
    let list = []
    let st = A[0]
    let ed = A[0]

    for(let i = 1 ; i < A.length; i++) {
    let num = A[i]
    if(ed + 1 !== num){
    if(st === ed){
    list.push(String(st))
    } else {
    list.push(`${String(st)}->${String(ed)}`)
    }
    st = num
    ed = num
    } else {
    ed = num
    }

    if(st === ed) {
    list.push(String(st))
    } else {
    list.push(String(st)+'->'+String(ed))
    }
    }
    return list
    }

    console.log(summarize(arr))

    ReplyDelete