首页 > 其他 > 详细

LeetCode -- Summary Ranges

时间:2015-10-04 19:40:43      阅读:248      评论:0      收藏:0      [点我收藏+]
题目描述:


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"].


Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.


就是给定一个已排序的数组,返回一个字符串数组,每个字符串表示为元素区间的合并。


本题是典型的two pointer 问题。


思路:
一次遍历,使用two pointer方法,from 表示区间的起始元素,to表示区间的结束元素。
如果相邻元素nums[i]和nums[i-1]差值为1,区间范围+1:to = nums[i] ,注意最后元素的处理。


否则:
如果from不等于to:
将range = [from,to]添加到解集中,并更新from的位置。
如果from和to相等:
将range=from(或to)添加到解集
注意末尾元素的判断(如果已打末尾,添加末尾元素)


实现代码:




public class Solution {
    public IList<string> SummaryRanges(int[] nums) {
        if(nums.Length == 0){
	    	return new List<string>();
    	}
    	
    	if(nums.Length == 1){
    		return new List<string>(){nums[0].ToString()};
    	}
    	
    	var from = nums[0];
    	var to = nums[0];
    	var ret = new List<string>();
    	for(var i = 1 ;i < nums.Length; i++){
    		if(nums[i] - nums[i-1] == 1){
    			to = nums[i];
    			if(i == nums.Length - 1){
    				ret.Add(string.Format("{0}->{1}", from , to));	
    			}
    		}
    		else{
    			if(from != to){
    				ret.Add(string.Format("{0}->{1}", from , to));	
    				if(i == nums.Length - 1 && to != nums[nums.Length - 1]){
    					ret.Add(nums[i].ToString());
    				}
    			}
    			else{
    				ret.Add(from.ToString());
    				if(i == nums.Length - 1){
    					ret.Add(nums[i].ToString());
    				}
    			}
    			from = nums[i];
    			to = nums[i];
    		}
    	}
    	
    	return ret;
    }
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

LeetCode -- Summary Ranges

原文:http://blog.csdn.net/lan_liang/article/details/48897071

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!