leetcode 228: Summary Ranges

Summary Ranges | LeetCode OJ
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"].

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

        List<String> res = new ArrayList<String>();

        if (nums.length == 0) {

            return res;

        }

        int start = 0;

        for (int i = 1; i < nums.length; i++) {

            if (nums[i] == nums[i-1] + 1) {

                continue;

            }

            if (i - 1 == start) {

                res.add(String.valueOf(nums[start]));

            } else {

                res.add(nums[start] + "->" + nums[i-1]);

            }

            start = i;

        }

        if (nums.length - 1 == start) {

            res.add(String.valueOf(nums[start]));

        } else {

            res.add(nums[start] + "->" + nums[nums.length - 1]);

        }

        return res;

    }

https://github.com/DeanWen/leetCodeInterview/blob/master/LeetCode/228-Summary%20Ranges.java

	public List<String> summaryRanges(int[] nums) {
	List<String> res = new ArrayList<>();
	if (nums == null || nums.length == 0) {
	return res;
	}
	StringBuilder sb = new StringBuilder();
	int min = nums[0];
	int max = nums[0];
	for (int i = 1; i < nums.length; i++) {
	if (nums[i - 1] + 1 == nums[i]) {
	continue;
	}
	max = nums[i - 1];
	if (max != min) {
	sb.append(min).append("->").append(max);
	}else {
	sb.append(max);
	}
	res.add(sb.toString());
	min = nums[i];
	sb.setLength(0);
	}
	if (min != nums[nums.length - 1]) {
	sb.append(min).append("->").append(nums[nums.length - 1]);
	}else {
	sb.append(nums[nums.length - 1]);
	}
	res.add(sb.toString());
	return res;
	}

http://shibaili.blogspot.com/2015/06/day-113-basic-calculator-ii.html
nums[i] == nums[i - 1] + 1 与 nums[i] - nums[i - 1] == 1 相比较，前者不会有溢出的问题 
re-factory之后的代码

    vector<string> summaryRanges(vector<int>& nums) {

        int start = 0;

        vector<string> rt;

        if (nums.size() == 0) return rt;

         

        for (int i = 1; i <= nums.size(); i++) {

            if (i == nums.size() || nums[i] != nums[i - 1] + 1) {

                if (i - start == 1) {

                    rt.push_back(to_string(nums[start]));

                }else {

                    rt.push_back(to_string(nums[start]) + "->" + to_string(nums[i - 1]));

                }

                start = i;

            }

        }

         

        return rt;

    }

re-factory之前的代码 

    vector<string> summaryRanges(vector<int>& nums) {

        int start = 0;

        vector<string> rt;

        if (nums.size() == 0) return rt;

         

        for (int i = 1; i < nums.size(); i++) {

            if ((long long)nums[i] - (long long)nums[i - 1] == 1) {

                continue;

            }

            if (i - start == 1) {

                string s = to_string(nums[start]);

                rt.push_back(s);

                start = i;

            }else {

                string s = to_string(nums[start]) + "->" + to_string(nums[i - 1]);

                rt.push_back(s);

                start = i;

            }

        }

         

        if (start == nums.size() - 1) {

            string s = to_string(nums[start]);

            rt.push_back(s);

        }else {

            string s = to_string(nums[start]) + "->" + to_string(nums.back());

            rt.push_back(s);

        }

         

        return rt;

    }

http://bookshadow.com/weblog/2015/06/26/leetcode-summary-ranges/
http://blog.csdn.net/xudli/article/details/46645087

http://buttercola.blogspot.com/2016/01/indeed-summary-ranges.html

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

        List<String> result = new ArrayList<>();

        if (nums == null || nums.length == 0) {

            return result;

        }

         

        if (nums.length == 1) {

            String curr = nums[0] + "";

            result.add(curr);

            return result;

        }

         

        // General case

        int j = 0;

        for (int i = 1; i < nums.length; i++) {

            if (nums[i] - nums[i - 1] != 1) {

                String curr = generateRange(nums, j, i - 1);

                result.add(curr);

                j = i;

            }

        }

         

        // Final case

        String curr = generateRange(nums, j, nums.length - 1);

        result.add(curr);

         

        return result;

    }

     

    private String generateRange(int[] nums, int start, int end) {

        if (start > end) {

            return "";

        }

         

        if (start == end) {

            String curr = nums[start] + "";

            return curr;

        }

         

        String curr = nums[start] + "->" + nums[end];

        return curr;

    }

Follow-up: What if the input contains duplicate numbers?
e.g. [1,2,2,3] -> "1->3"
[1,2,2,5] -> "1->2", "5"


For the input containing duplicates, we only need to slightly modify the code that only skips the duplicated numbers as well.

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

        List<String> result = new ArrayList<>();

        if (nums == null || nums.length == 0) {

            return result;

        }

         

        if (nums.length == 1) {

            String curr = nums[0] + "";

            result.add(curr);

            return result;

        }

         

       

        //General case

        int j = 0;

        for (int i = 1; i < nums.length; i++) {

            if ((nums[i] - nums[i - 1] == 1) || (nums[i] == nums[i - 1])) {

                continue;

            }

                 

            String curr = generateRange(nums, j, i - 1);

            result.add(curr);

            j = i;

        }

                 

        // Final case

        String curr = generateRange(nums, j, nums.length - 1);

        result.add(curr);

         

        return result;

    }

Read full article from Summary Ranges | LeetCode OJ