Baseball Game
你要为一种特殊的游戏记分。按从左到右的顺序读取 operations，每一项都会更改记分记录。像 "7" 或 "-2" 这样的整数会添加对应分数。"+" 会添加最近两次得分的总和，"D" 会添加最近一次得分的两倍，"C" 会永久移除最近一次得分。
编写一个名为 calPoints 的函数，返回最后一次操作后记分记录中剩余分数的总和。空记录的总和为 0。
函数
- operationsstring-array
- 按顺序执行的操作：以文本形式表示的整数，或“+”、“D”、“C”
- 返回值integer
- 结束时仍保留在记录中的分数总和
约束条件
1 ≤ operations.length ≤ 5000- 每个条目都是
"+"、"D"、"C"，或用十进制表示且满足-3 × 104 ≤ value ≤ 3 × 104的整数。 - 每个操作都有效：只有当记录中至少有两个分数时，才会出现
"+"；只有当记录中至少有一个分数时，才会出现"D"和"C"。 - 记录中的每个分数和最终总和都可以用 32 位有符号整数表示。
示例
- 输入
- operations = ["4", "-2", "D", "+", "C", "7"]
- 输出
- 5
- 解释
- 记录增长为
[4, -2]，"D"添加-4，"+"将-2 + -4 = -6相加，"C"移除这个-6，最后加入7。记录[4, -2, -4, 7]的总和为5。
- 输入
- operations = ["6", "D", "C", "C"]
- 输出
- 0
- 解释
"D"会在6后添加12，然后两个"C"条目会分别移除12和6。最后什么都不剩，所以答案是0。
- 输入
- operations = ["1", "2", "+", "+", "D"]
- 输出
- 21
- 解释
- 两个
"+"条目分别计算1 + 2 = 3，然后计算2 + 3 = 5"D"会加上10。记录[1, 2, 3, 5, 10]的总和是21。
进阶
如何添加一种操作，以撤销最近一次 "C"，并恢复被取消的分数，且时间复杂度为 O(1)？
提示
逐个打开提示，每个都会多透露一点。
每条规则都讨论最新的分数或最近两个分数。当
"C"移除最新分数时，应该怎么处理？取消一个分数后，被移除分数之前的那个分数会重新成为最新分数。分数按照与添加顺序相反的顺序移除，这就是栈的行为方式。
将每个新分数都压入栈中：分数本身，遇到
"D"时取栈顶分数的两倍，遇到"+"时取栈顶两个分数的和。遇到"C"时弹出栈顶分数。最后，返回栈中剩余分数的总和，也可以在压栈和弹栈时随时更新总和。
题解
每次操作都会读取最新的分数，而 "C" 可以一次移除一个分数，这样较早的分数就会再次成为最新分数。这就是后进先出：每个新分数都入栈，遇到 "C" 就出栈，并读取栈顶的一个或两个分数来处理 "D" 和 "+"。
在栈上构建记录，并在最后求和
思路
把记录保存为列表，并将最新分数放在末尾，这样每次操作只会处理末尾。执行 "C" 后，次新的分数会变成最新分数，之后的 "D" 或 "+" 必须读取它；弹出末尾元素后，它就会显现出来。在第一个示例中，"C" 会弹出 -6，并留下 [4, -2, -4]。
所有操作执行完后，列表中正好保存着计入总分的分数，所以把它们加起来：时间复杂度为 O(n)，空间复杂度为 O(n)。
算法
- 从空栈
record开始。 - 遇到
"+"，将栈顶两个条目的和压入栈中。遇到"D"，将栈顶条目的两倍压入栈中。 - 遇到
"C"，弹出栈顶条目。 - 否则，该条目是一个数字：将文本转换为整数并压入栈中。
- 返回栈中剩余所有条目的和。
def calPoints(operations):
record = [] # the scores that still count, newest last
for op in operations:
if op == "+":
record.append(record[-1] + record[-2])
elif op == "D":
record.append(2 * record[-1])
elif op == "C":
record.pop()
else:
record.append(int(op))
return sum(record)使用累计总和的栈
思路
让 total 始终等于栈中分数的总和：每次压入都会加上新分数，每次遇到 "C" 都会减去弹出的分数。栈必须保留，因为取消操作需要知道要减去哪个分数。在第一个示例中，总分依次变为 4, 2, -2, -8，取消操作会减去 -6，使总分变为 -2，然后 7 会让总分变为 5。
这样只需遍历一次，时间复杂度为 O(n)，处理完任意前缀的操作后都能得到答案。空间复杂度为 O(n)，因为每个操作都可能是一个会保留在栈中的数字。
算法
- 从空栈
record开始，并设置total = 0。 - 遇到
"C"时，弹出栈顶分数，并从total中减去它。 - 否则，算出新的分数：遇到
"+"时，取栈顶两个分数的和；遇到"D"时，取栈顶分数的两倍；否则取该整数本身。 - 将新分数压入栈中，并将它加到
total。 - 返回
total。
def calPoints(operations):
record = [] # the scores that still count, newest last
total = 0 # always the sum of record
for op in operations:
if op == "C":
total -= record.pop() # the cancelled score leaves the total too
continue
if op == "+":
score = record[-1] + record[-2]
elif op == "D":
score = 2 * record[-1]
else:
score = int(op)
record.append(score)
total += score
return total
易错点和边界情况
- 只保留累计总分和最近两次得分。在
["1", "2", "3", "C", "+"]中，"+"需要1和2，而只保留最近两次得分会丢掉1。 - 没有从累计总分中减去已取消的得分。在第二个示例中，这会导致结果是
18，而不是0。 - 通过检查是否包含数字来判断某项是不是数字。
"-2"以减号开头；应与这三个符号进行比较，并使用语言的整数解析器解析其余所有内容。 - 假设答案一定是正数。
["-3", "D"]的总和是-9。
常见问题3
棒球比赛的时间复杂度是多少？
每次操作在栈顶执行的工作量都是常数，因此 n 次操作需要 O(n) 时间。当大多数操作都会添加分数时，栈需要 O(n) 空间。
为什么栈是棒球比赛中合适的数据结构？
每条规则都会读取或移除最近的分数，撤销操作会显示它之前的分数。这就是后进先出，栈可以通过 O(1) 时间复杂度完成压入、弹出和查看。只在数组末尾操作的数组可以作为栈使用。
棒球比赛题能否用 O(1) 的额外空间解决？
一般来说不行。一串数字后面跟着一串 "C" 条目，会按相反的顺序抵消这些数字，因此你必须记住每个数字，直到确定它是否会被抵消。最坏情况下，这需要 O(n) 的内存。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def calPoints(operations):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
operations = ["4", "-2", "D", "+", "C", "7"]
预期输出
5