150. Evaluate Reverse Polish Notation

Analyis

em，首先得知道，Reverse Polish Notation 就是后缀表达式，也就是说，这是个后缀表达式求值的问题。一般而言，后缀表达式的问题是用栈来求解的。

Code

直接用栈做。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int size = tokens.size();
        for(int i = 0; i < size; i++) {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int a, b, res;
                a = st.top(); st.pop();
                b = st.top(); st.pop();
                if(tokens[i] == "+") res = a + b;
                else if(tokens[i] == "-") res = b - a;
                else if(tokens[i] == "*") res = a * b;
                else if(tokens[i] == "/") res = b / a;
                st.push(res);
            } else {
                int tmp = 0, len = tokens[i].length();
                int index = 0, flag = true;
                if(tokens[i][index] == '-') {
                    flag = false;
                    index++;
                }
                while(index < len) {
                    tmp = tmp * 10 + tokens[i][index] - '0';
                    index++;
                }
                if(!flag) tmp = -tmp;
                st.push(tmp);
            }
        }
        return st.top();
    }
};

需要注意的地方就是减（除）法时，分清楚减（除）数与被减（除）数。
em，借用一下库函数，再精简一下：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int size = tokens.size();
        for(int i = 0; i < size; i++) {
            if(isdigit(tokens[i][0]) || isdigit(tokens[i][1])) {
                st.push(atoi(tokens[i].c_str()));
            } else {
                int a, b;
                a = st.top(); st.pop();
                b = st.top(); st.pop();
                if(tokens[i] == "+") st.push(a + b);
                else if(tokens[i] == "-") st.push(b - a);
                else if(tokens[i] == "*") st.push(a * b);
                else st.push(b / a);
            }
        }
        return st.top();
    }
};

用 isdigit 函数判断是否是数字时，不要直接判断第二个字符，这样可能会越界。因为 Leetcode 给的一定是合法的后缀表达式，所以可以写的这么“肆无忌惮”😜。

66. Plus One

Analysis

不算大数加法的大数加法题。

Code

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int size = digits.size(), i = 0;
        reverse(digits.begin(), digits.end());
        int carry = 1;
        while(i < size) {
            digits[i] += carry;
            if(digits[i] >= 10) {
                digits[i] -= 10;
                carry = 1;
            } else carry = 0;
            i++;
        }
        if(carry) digits.push_back(carry);
        reverse(digits.begin(), digits.end());
        return digits;
    }
};

先逆置的原因是，如果存在进位，可以直接在数组末尾添加，重新逆置后就是结果了。
剪一下枝：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int size = digits.size(), i = 0;
        if(digits[size - 1] + 1 < 10) {
            digits[size - 1] += 1;
            return digits;
        }
        reverse(digits.begin(), digits.end());
        int carry = 1;
        while(i < size) {
            digits[i] += carry;
            if(digits[i] >= 10) {
                digits[i] -= 10;
                carry = 1;
            } else {
                carry = 0;
                break;
            }
            i++;
        }
        if(carry) digits.push_back(carry);
        reverse(digits.begin(), digits.end());
        return digits;
    }
};

看了别人的做法，这个题可以从判断每一位计算后是不是 0 来思考，如果是 0 那么说明有进位，继续计算，如果没有，就可以退出循环了：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int size = digits.size();
        int i = size - 1;
        while(i >= 0) {
            digits[i]++;
            if(digits[i] == 10) digits[i] = 0;
            else break;
            i--;
        }
        if(digits[0] == 0) {
            digits.push_back(0);
            digits[0] = 1;
        }
        return digits;
    }
};

不得不说，这个思路确实比较好。

Summary

钓鱼回来有点累，还好问题轻松解决，可以早点睡觉了😂。