047 · Baseball Game

algorithm

Published

June 29, 2026

My First Thoughts

这题一共有 4 种操作：

普通整数：记录一轮新的分数
"C"：取消上一轮有效分数
"D"：记录上一轮有效分数的两倍
"+"：记录前两轮有效分数之和

我一开始想，既然最后要求总分，而且 "D" 和 "+" 都只看最近的一两轮有效分数，也许只需要维护 3 个变量：

总分值
当前轮子前 1 轮有效分值
当前轮子前 2 轮有效分值

比如这个例子：

operations = ["5", "2", "C", "D", "+"]

我先想到的是：

scores = 0
pre1 = 0
pre2 = 0

遇到普通整数时，把它加入总分，并更新最近的有效分数：

for char in operations:
    if char in 字符整数:
        scores += int(char)

        pre1 = int(char)
        pre2 = pre1

    elif char == "C":
        pre1 = pre2
        pre2 = ?

这里就卡住了。

"C" 会取消上一轮有效分数。取消以后，新的 pre1 可以变成原来的 pre2，但新的 pre2 应该是谁？它可能是更早之前的某一轮分数。可是如果我只保存 pre1 和 pre2，更早的历史已经丢掉了。

所以这题不能只记录最近一两轮。更稳的状态应该是：记录所有当前仍然有效的分数，最后再求和。

也就是换成：

legal_score = []

这样 "C" 就很好处理：上一轮有效分数就是列表最后一个元素，取消它就是删掉最后一个元素。

继续按操作更新这个列表：

for char in operations:
    if char in 字符整数:
        legal_score.append(int(char))

    elif char == "C":
        legal_score.pop()

    elif char == "D":
        score = 2 * legal_score[-1]
        legal_score.append(score)

    elif char == "+":
        score = legal_score[-1] + legal_score[-2]
        legal_score.append(score)

return sum(legal_score)

这里还有一个实现细节：我原来写 char in 字符整数，意思是想判断这个字符串是不是整数。但 Python 里没有一个可以直接这样使用的“整数集”或“自然数集”。

而且题目里可能有负数，比如 "-2"。它确实表示一个整数，但不是单个数字字符。

所以更简单的写法是先判断三个特殊操作："C"、"D"、"+"。如果都不是，那它就一定是一个表示整数的字符串，最后直接 int(char) 就行。

到这里，这个思路就完整了：用列表保存有效分数，操作都作用在列表末尾，最后返回列表总和。

Why That Is Not Enough

上面的 legal_score 解法本身已经是正确方向。

它需要注意的不是算法方向，而是两个实现细节。

第一个细节是 "C" 应该删除最后一个有效得分。Python 里可以用：

legal_score.pop()

也可以写：

del legal_score[-1]

这题里 pop() 更自然一些，因为它表达的就是从列表末尾移除一个元素。

第二个细节是整数判断。不要用类似：

if char in "0123456789":

因为这样无法自然处理 "-2" 这样的负数字符串。

这道题已经保证每个操作只会是 "C"、"D"、"+" 或者一个整数格式字符串。所以最简单的写法就是：

if char == "C":
    ...
elif char == "D":
    ...
elif char == "+":
    ...
else:
    legal_score.append(int(char))

把三个特殊操作排除以后，剩下的就直接当整数处理。

Final Idea

维护一个列表 legal_score，让它始终表示“目前还有效的每一轮得分”。

每次遇到一个操作，就更新这个列表：

普通整数：新增一个有效得分
"C"：移除最后一个有效得分
"D"：根据最后一个有效得分生成一个新得分
"+"：根据最后两个有效得分生成一个新得分

最后答案就是：

sum(legal_score)

这其实就是把比赛记录从左到右重新执行一遍。legal_score 不是原始输入，而是我们根据规则维护出来的“当前有效记分板”。

Why It Works

题目中的每个操作只会影响当前有效得分列表的末尾。

普通整数会增加一条新的有效记录：

legal_score.append(int(char))

"C" 会取消前一轮有效得分。前一轮有效得分正好就是列表最后一个元素，所以：

legal_score.pop()

"D" 需要前一轮有效得分，也就是：

legal_score[-1]

"+" 需要前两轮有效得分，也就是：

legal_score[-1]
legal_score[-2]

因为我们每一步都让 legal_score 和题目定义的有效得分保持一致，所以遍历结束后，legal_score 里保存的就是所有最终有效得分。

把它们加起来，就是最终总分。

Code

def calPoints(operations):
    legal_score = []

    for char in operations:
        if char == "C":
            legal_score.pop()
        elif char == "D":
            legal_score.append(2 * legal_score[-1])
        elif char == "+":
            legal_score.append(legal_score[-1] + legal_score[-2])
        else:
            legal_score.append(int(char))

    return sum(legal_score)

Complexity

Time	\(O(n)\) - `n` 是 `operations` 的长度；每个操作处理一次，最后求和也最多遍历所有有效得分
Space	\(O(n)\) - 最坏情况下所有操作都是普通整数，`legal_score` 会保存所有得分

Takeaway

当题目规则会“取消最近一次有效操作”时，只记录一两个变量通常不够。更自然的做法是维护一个列表，让列表末尾始终代表最近的有效记录；新增就 append，取消就 pop。

← Quiz