Tuesday, August 4, 2015

Leetcode 228: 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"].

slow, fast 指针对连续的数进行操作,在判断里面加上fast + 1 < size(),这样fast就会在最后那个char那里停。

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        //sanity check
        vector<string> rst;
        if (nums.size() == 0) return rst;
        int slow = 0;
        int fast = 0;
        for (; fast < nums.size(); fast++) {
            if (fast + 1 < nums.size() && nums[fast] + 1 == nums[fast+1]) {
                continue;
            } else {
                if (slow == fast) {
                    rst.push_back(to_string(nums[slow]));
                } else {
                    string buf = "";
                    buf += to_string(nums[slow]);
                    buf += "->";
                    buf += to_string(nums[fast]);
                    rst.push_back(buf);
                }
                slow = fast+1;
            }
        }
      
        return rst;
    }
};

updated:
下面的代码是重写的,整体上看起来更加整洁,逻辑更加清晰。
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> rst;
        int left = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i+1 < nums.size() && nums[i+1] == nums[i]+1) {
                continue;
            } else {
                if (left < i) {
                    string tmp = to_string(nums[left]) + "->" + to_string(nums[i]);
                    rst.push_back(tmp);
                } else {
                    rst.push_back(to_string(nums[left]));
                }
                left = i + 1;
            }
        }
        return rst;
    }
};

No comments:

Post a Comment