Easy

题目描述

你正在记录一场有着特殊规则的棒球比赛的得分。比赛开始时，记录是空的。

你将得到一个字符串列表 operations，其中 operations[i] 是你必须应用到记录上的第 i 个操作，操作内容如下：

  • 整数 x：记录一个新得分 x
  • ‘+’：记录一个新得分，该得分是前两个得分的总和
  • ‘D’：记录一个新得分，该得分是前一个得分的两倍
  • ‘C’：取消前一个得分，将其从记录中移除

在应用所有操作后，返回记录中所有得分的总和。

测试用例保证答案和所有中间计算都适合 32 位整数，并且所有操作都是有效的。

示例 1：

输入：ops = ["5","2","C","D","+"]
输出：30
解释：
"5" - 记录加 5 ，记录现在是 [5]
"2" - 记录加 2 ，记录现在是 [5, 2]
"C" - 使前一个得分无效并将其移除，记录现在是 [5]
"D" - 记录加 2 * 5 = 10 ，记录现在是 [5, 10]
"+" - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15]
所有得分的总和 5 + 10 + 15 = 30

示例 2：

输入：ops = ["5","-2","4","C","D","9","+","+"]
输出：27

示例 3：

输入：ops = ["1","C"]
输出：0

约束条件：

  • 1 <= operations.length <= 1000
  • operations[i] 是 “C”、“D”、"+" 或者一个表示范围 [-3 * 10^4, 3 * 10^4] 内整数的字符串
  • 对于操作 “+"，记录中总是存在至少两个分数
  • 对于操作 “C” 和 “D”，记录中总是存在至少一个分数

解题思路

这道题是一个典型的栈模拟问题。我们需要维护一个记录栈来存储有效的得分，然后根据不同的操作类型进行相应处理。

解题思路：

  1. 栈数据结构：使用栈来存储当前有效的得分记录，栈顶元素是最新的得分
  2. 操作处理：
    • 数字：直接将数字转换为整数后入栈
    • ‘C’：移除栈顶元素（取消上一次得分）
    • ‘D’：将栈顶元素翻倍后入栈
    • ‘+’：将栈顶两个元素相加后入栈
  3. 结果计算：遍历完所有操作后，将栈中所有元素求和

关键点：

  • 栈的后进先出特性完美符合题目中"前一个得分"和"前两个得分"的概念
  • 题目保证操作的有效性，无需额外的边界检查
  • 时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是操作数量

这是一道很好的栈应用题，通过模拟操作过程来解决问题。

代码实现

class Solution {
public:
    int calPoints(vector<string>& operations) {
        vector<int> record;
        
        for (const string& op : operations) {
            if (op == "C") {
                record.pop_back();
            } else if (op == "D") {
                record.push_back(record.back() * 2);
            } else if (op == "+") {
                int size = record.size();
                record.push_back(record[size - 1] + record[size - 2]);
            } else {
                record.push_back(stoi(op));
            }
        }
        
        int sum = 0;
        for (int score : record) {
            sum += score;
        }
        return sum;
    }
};

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        record = []
        
        for op in operations:
            if op == "C":
                record.pop()
            elif op == "D":
                record.append(record[-1] * 2)
            elif op == "+":
                record.append(record[-1] + record[-2])
            else:
                record.append(int(op))
        
        return sum(record)

public class Solution {
    public int CalPoints(string[] operations) {
        List<int> record = new List<int>();
        
        foreach (string op in operations) {
            if (op == "C") {
                record.RemoveAt(record.Count - 1);
            } else if (op == "D") {
                record.Add(record[record.Count - 1] * 2);
            } else if (op == "+") {
                int size = record.Count;
                record.Add(record[size - 1] + record[size - 2]);
            } else {
                record.Add(int.Parse(op));
            }
        }
        
        int sum = 0;
        foreach (int score in record) {
            sum += score;
        }
        return sum;
    }
}

/**
 * @param {string[]} operations
 * @return {number}
 */
var calPoints = function(operations) {
    const record = [];
    
    for (const op of operations) {
        if (op === 'C') {
            record.pop();
        } else if (op === 'D') {
            record.push(record[record.length - 1] * 2);
        } else if (op === '+') {
            record.push(record[record.length - 1] + record[record.length - 2]);
        } else {
            record.push(parseInt(op));
        }
    }
    
    return record.reduce((sum, score) => sum + score, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有操作，每个操作的处理时间为常数
空间复杂度O(n)最坏情况下需要存储所有得分记录

相关题目