Saturday, August 5, 2017

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"].
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> sol;
        if (nums.size() == 0) {
            return sol;
        }
        string ans;
        for (int i = 0; i < nums.size() - 1; i++) {
            if (ans.empty()) {
                ans += to_string(nums[i]);
            }
            if (nums[i + 1] - nums[i] != 1) {
                // Not consecutive.
                if (ans != to_string(nums[i])) {
                    ans +=  "->" + to_string(nums[i]);
                }
                sol.push_back(ans);
                ans = "";
            }
        }
        // Handle last element.
        if (!ans.empty()) {
            ans += "->" + to_string(nums[nums.size() - 1]);
        } else {
            ans = to_string(nums[nums.size() - 1]);
        }
        sol.push_back(ans);
        return sol;
    }
};

======== Another attempt (not elegant one) ======
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        if (nums.size() == 0) {
            return ans;
        }
        if (nums.size() == 1) {
            ans.push_back(to_string(nums[0]));
            return ans;
        }
       
        int start_it = 0, end_it = 0;
       
        while (start_it < nums.size() && end_it < nums.size()) {
            int st = start_it;
            end_it = start_it + 1;
            bool flag = false;
            while (end_it < nums.size() && nums[end_it] == nums[start_it] + 1) {
                flag = true;
                if (end_it == nums.size()) {
                    ans.push_back(getRange(nums, st, end_it));
                    return ans;
                }
                end_it++;
                start_it++;
            }
           
            if (!flag) {
                ans.push_back(to_string(nums[start_it]));
            } else {
                string sol = getRange(nums, st, start_it);
                ans.push_back(sol);
            }
            start_it = end_it;
            end_it = start_it;     
        }
        return ans;
    }
    string getRange(vector<int> nums, int st, int end_it) {
        string ans;
        if (end_it != st) {
                ans = to_string(nums[st]) + "->" + to_string(nums[end_it]);
        } else {
                ans = to_string(nums[st]);
        }
        return ans;
    }
};

No comments:

Post a Comment