2015年6月27日星期六

leetcode228 @summary ranges

Analysis:
Recursive call until pointer to the end of the array.
Time complexity: O(n).

public class Solution {
    private final String CONSTLINK = "->";
    public List<String> summaryRanges(int[] nums) {
        List<String> res= new ArrayList<>();
        if(nums.length==0)
            return res;
        StringBuilder sb=new StringBuilder();
        sb.append(nums[0]);
        getRange(nums, 0, 0, sb, res);
        return res;
    }
 
    private void getRange(int[] nums, int start, int pointer,  StringBuilder tmp, List< String > res){
        if(pointer >= nums.length)
            return;
        if(pointer == nums.length -1){
            if( start == pointer)
                res.add(tmp.toString());
              else{
                  tmp.append(CONSTLINK);
                  tmp.append( nums[pointer]);
                  res.add(tmp.toString());
              }
              return;
        }
        else {
            if( pointer +1 < nums.length && nums[pointer +1] == nums[ pointer] +1)
                getRange( nums, start, pointer +1, tmp, res );
            else{
             
              if( start == pointer)
                res.add(tmp.toString());
              else{
                  tmp.append(CONSTLINK);
                  tmp.append( nums[pointer]);
                  res.add(tmp.toString());
              }
                StringBuilder sb= new StringBuilder();
                sb.append(nums[pointer+1]);
                getRange(nums, pointer+1, pointer+1, sb, res);
            }    
        }
    }
}

没有评论:

发表评论