50-棒球比赛

自己的做法

算法思想

超简单。

使用栈。point初始为0.

一共有四种情况：

1. 整数x，直接入栈。需要进行字符串到int类型的转换。使用C++ atoi函数
2. +：获得栈中前两个元素的值，加到point上。同时将结果入栈
3. D：point加上栈顶元素的二倍，同时该值入栈
4. C：point减去栈顶元素，同时栈顶元素出栈

遍历数组结束后，直接返回point即可。

当然也可以遍历数组时只对栈操作，不进行分数加减。第二遍栈依次出栈，加到point上。

算法实现

class Solution {
public:
    int calPoints(vector<string>& ops) {
        int point = 0;
        stack<int> s;

        for(int i = 0; i < ops.size(); i++) {
            if(ops[i].compare("+")) {
                int point1 = s.top();
                s.pop();
                int point2 = s.top();
                s.push(point1);
                s.push(point1 + point2);
                point = point + point1 + point2;
            } else if(ops[i].compare("D")) {
                point = point + s.top() * 2;
                s.push(s.top() * 2);
            } else if(ops[i].compare("C")) {
                point = point - s.top();
                s.pop();
            } else {
                int x = atoi(ops[i].c_str());
                s.push(x);
                point = point + x;
            }
        }
        return point;
    }
};

compare用==也可以。

性能分析

时间复杂度：$O(n)$，n为数字长度。

空间复杂度：$O(n)$。

参考答案做法相同。