模拟法解题的思路与算法分享

我们先来看思路与算法：

使用变长数组对栈进行模拟。

• 如果操作是 +，那么访问数组的后两个得分，将两个得分之和加到总得分，并且将两个得分之和入栈。
• 如果操作是 D，那么访问数组的最后一个得分，将得分乘以 2 加到总得分，并且将得分乘以 2 入栈。
• 如果操作是 C，那么访问数组的最后一个得分，将总得分减去该得分，并且将该得分出栈。
• 如果操作是整数，那么将该整数加到总得分，并且将该整数入栈。

代码

Python3

class Solution:def calPoints(self, ops: List[str]) -> int:ans = 0points = []for op in ops:if op == '+':pt = points[-1] + points[-2]elif op == 'D':pt = points[-1] * 2elif op == 'C':ans -= points.pop()continueelse:pt = int(op)ans += ptpoints.append(pt)return ans

C++

class Solution {
public:int calPoints(vector<string>& ops) {int ret = 0;vector<int> points;for (auto &op : ops) {int n = points.size();switch (op[0]) {case '+':ret += points[n - 1] + points[n - 2];points.push_back(points[n - 1] + points[n - 2]);break;case 'D':ret += 2 * points[n - 1];points.push_back(2 * points[n - 1]);break;case 'C':ret -= points[n - 1];points.pop_back();break;default:ret += stoi(op);points.push_back(stoi(op));break;}}return ret;}
};

Java

class Solution {public int calPoints(String[] ops) {int ret = 0;List<Integer> points = new ArrayList<Integer>();for (String op : ops) {int n = points.size();switch (op.charAt(0)) {case '+':ret += points.get(n - 1) + points.get(n - 2);points.add(points.get(n - 1) + points.get(n - 2));break;case 'D':ret += 2 * points.get(n - 1);points.add(2 * points.get(n - 1));break;case 'C':ret -= points.get(n - 1);points.remove(n - 1);break;default:ret += Integer.parseInt(op);points.add(Integer.parseInt(op));break;}}return ret;}
}

复杂度分析

时间复杂度：O(n) ，其中 n 为数组 ops 的大小。遍历整个 ops 需要 O(n) 。
空间复杂度：O(n) 。变长数组最多保存 O(n) 个元素。

好了，今天的文章分享就到这里了，希望对大家的学习有帮助哦！