Go语言LeetCode 682. 棒球比赛题解

题目描述

你需要扮演一名棒球比赛的记录员。比赛由若干回合组成，过去的得分可能会影响后续回合的得分。初始记录为空。给定一个操作字符串列表 ops，其中包含以下四种规则：

• 整数 x：表示本回合获得新分数 x，直接记录。
• "+"：表示本回合新获得的得分是前两次得分的总和。题目保证执行此操作时至少已有两个有效分数。
• "D"：表示本回合新获得的得分是前一次得分的两倍。题目保证执行此操作时至少已有一个有效分数。
• "C"：表示前一次得分无效，需从记录中移除。题目保证执行此操作时至少已有一个有效分数。

请返回所有有效得分的总和。

第1步：理解示例逻辑

以输入 ops = ["5", "2", "C", "D", "+"] 为例，逐步演示栈的变化过程：

1. "5"：记录加 5，当前记录为 [5]。
2. "2"：记录加 2，当前记录为 [5, 2]。
3. "C"：使最后一次得分（2）无效并移除，当前记录为 [5]。
4. "D"：新得分是上一次（5）的两倍，即 10。记录变为 [5, 10]。
5. "+"：新得分是前两次（5 和 10）的和，即 15。记录变为 [5, 10, 15]。

最终总和为 $5 + 10 + 15 = 30$。

第2步：分析操作约束

• 长度限制：ops 的长度在 1 到 1000 之间。
• 数值范围：整型分数在 $[-3 \times 10^4, 3 \times 10^4]$ 之间。
• 前置条件：对于 "D" 和 "C" 操作，栈内至少有1个元素；对于 "+" 操作，栈内至少有2个元素。

解题思路

由于每次操作都依赖于历史记录的最新状态（如最近一次、最近两次得分），且涉及插入、删除末尾元素等操作，**栈（Stack）** 是最符合直觉的数据结构。我们可以使用一个切片来模拟栈的行为：

1. 初始化栈：创建一个空的整型切片 stack，用于存储历史得分。
2. 遍历操作数组：逐个读取 ops 中的字符串。
3. 分类处理：
   • 若为 "C"：执行出栈操作（丢弃最后一个元素）。
   • 若为 "D"：读取栈顶元素，乘以2后入栈。
   • 若为 "+"：读取栈顶元素和次栈顶元素，求和后作为新元素入栈。
   • 其他情况（数字）：转换为整数后直接入栈。
4. 计算总和：遍历结束后，累加栈中所有元素的值即为结果。

Go 语言 AC 代码

以下是基于上述逻辑的 Go 语言实现。使用标准库的切片模拟栈，配合 slices.Sort 或手动遍历求和均可，此处采用最直观的遍历求和方式。

package main

import (
	"strconv"
)

func calPoints(ops []string) int {
	// 使用切片模拟栈
	stack := []int{}

	for _, op := range ops {
		switch op {
		case "C":
			// 移除最后一条记录
			if len(stack) > 0 {
				stack = stack[:len(stack)-1]
			}
		case "D":
			// 新得分为上次得分的两倍
			lastScore := stack[len(stack)-1]
			stack = append(stack, lastScore*2)
		case "+":
			// 新得分为前两次得分之和
			// 因为保证了至少有两个元素，所以安全访问
			top := stack[len(stack)-1]
			secondTop := stack[len(stack)-2]
			stack = append(stack, top+secondTop)
		default:
			// 普通整数分数
			val, err := strconv.Atoi(op)
			if err == nil {
				stack = append(stack, val)
			}
		}
	}

	// 计算总和
	sum := 0
	for _, score := range stack {
		sum += score
	}
	return sum
}

复杂度分析

• 时间复杂度：O(N)，其中 N 是 ops 的长度。我们只需遍历数组一次，切片操作和加法运算均为 O(1)。
• 空间复杂度：O(N)，栈的大小最多为 N，用于存储每次操作后的得分状态。

关键点总结

• 数据结构选择：LIFO（后进先出）特性完美契合“撤销”和“参考最近记录”的需求。
• 边界检查：虽然题目保证数据合法性，但在实际开发中，访问 stack[len-1] 前应确保 len > 0。
• 类型转换：输入的分数为字符串，使用 strconv.Atoi 安全转换，非数字字符默认为错误但题目限定只有特定命令。

以上就是Go语言LeetCode 682. 棒球比赛题解的详细内容，更多关于Go语言算法题解的资料请关注本站其它相关文章！