棒球比赛得分计算：使用栈高效解决特殊赛制

你是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。

比赛开始时，记录是空白的。你会得到一个记录操作的数组 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：

• 整数 x - 表示本回合新获得分数 x* 'D' - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。* 'C' - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。

请你返回记录中所有得分的总和。

输入

第一行为 ops 的长度 n

第二行为 ops

注: 0 <= 分数 <= 100

输出

所有得分的总和

思路：

使用栈来记录每一次得分，遇到整数入栈，遇到 'D' 则将前一次得分翻倍入栈，遇到 'C' 则弹出栈顶元素。最后将栈中所有得分相加即可。

时间复杂度： O(n)，其中 n 为 ops 的长度。

**Python3 代码：**pythondef calPoints(ops): stack = [] for op in ops: if op.isdigit() or op[0] == '-' and op[1:].isdigit(): # 处理整数 stack.append(int(op)) elif op == 'D': stack.append(stack[-1] * 2) elif op == 'C': stack.pop() return sum(stack)

示例ops = ['5', '2', 'C', 'D', '+']result = calPoints(ops)print(result) # 输出 30

解释：

• calPoints(ops) 函数接收操作数组 ops 作为参数。* 使用一个栈 stack 来存储每次的得分。* 循环遍历 ops 中的每一个操作 op。* 如果 op 是整数，则将其转换为整数并入栈。* 如果 op 是 'D'，则将栈顶元素乘以 2 并入栈。* 如果 op 是 'C'，则弹出栈顶元素。* 最后返回栈中所有元素的总和。

使用示例：

对于输入的示例 ops = ['5', '2', 'C', 'D', '+']，代码执行过程如下：

1. 入栈 5，栈为 [5]2. 入栈 2，栈为 [5, 2]3. 弹出栈顶元素 2，栈为 [5]4. 将栈顶元素 5 乘以 2 入栈，栈为 [5, 10]5. 将栈顶元素 10 与倒数第二个元素 5 相加，入栈，栈为 [5, 10, 15]

最后返回栈中所有元素的总和 3