Thursday, June 25, 2015

Day 113, ##, Basic Calculator II, Summary Ranges

Basic Calculator II
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +-*/ operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.
--------------------------------------------------
look ahead,COME_BACK, 如果加入括号呢?
注意对i的处理
class Solution {
public:
    long long lookAhead(string &s, int &i) {
        long long num = 0;
        while (i < s.length()) {
            if (s[i] == ' ') {
                i++;
            }else if (isdigit(s[i])) {
                num = 10 * num + s[i] - '0'; 
                i++;
            }else
                break;
        }
        
        i--;
        return num;
    }

    int calculate(string s) {
        long long num = 0, rt = 0;
        long long sign = 1;
        
        for (int i = 0; i < s.length(); i++) {
            if (isdigit(s[i])) {
                num = lookAhead(s,i);
            }else if (s[i] == '+') {
                rt += sign * num;
                sign = 1;
                num = 0;
            }else if (s[i] == '-') {
                rt += sign * num;
                sign = -1;
                num = 0;
            }else if (s[i] == '*') {
                i++;
                num *= lookAhead(s,i);
            }else if (s[i] == '/') {
                i++;
                num /= lookAhead(s,i);
            }
        }
        
        if (num > 0) return rt + sign * num;
        return rt;
    }
};

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"].
----------------------------------------------------------
nums[i] == nums[i - 1] + 1 与 nums[i] - nums[i - 1] == 1 相比较,前者不会有溢出的问题
re-factory之后的代码
class Solution {
public:
    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之前的代码
class Solution {
public:
    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;
    }
};

No comments:

Post a Comment