栈题目：棒球比赛

文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
  • • 要求
    • 示例
    • 数据范围
• 解法
• • 思路和算法
  • 代码
  • 复杂度分析

题目

标题和出处

标题：棒球比赛

出处：682. 棒球比赛

难度

3 级

题目描述

要求

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

比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 $\text{ops}$，其中 $\text{ops[i]}$ 是你需要记录的第 $\text{i}$ 项操作，$\text{ops}$ 遵循下述规则：

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

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

示例

示例 1：

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

示例 2：

输入：$\text{ops = ["5","-2","4","C","D","9","+","+"]}$
输出：$\text{27}$
解释：
$\text{"5"}$ - 记录加 $\text{5}$，记录现在是 $\text{[5]}$
$\text{"-2"}$ - 记录加 $\text{-2}$，记录现在是 $\text{[5, -2]}$
$\text{"4"}$ - 记录加 $\text{4}$，记录现在是 $\text{[5, -2, 4]}$
$\text{"C"}$ - 使前一次得分的记录无效并将其移除，记录现在是 $\text{[5, -2]}$
$\text{"D"}$ - 记录加 $\text{2}\times \text{(-2)}=\text{-4}$，记录现在是 $\text{[5, -2, -4]}$
$\text{"9"}$ - 记录加 $\text{9}$，记录现在是 $\text{[5, -2, -4, 9]}$
$\text{"+"}$ - 记录加 $\text{(-4)}+\text{9}=\text{5}$，记录现在是 $\text{[5, -2, -4, 9, 5]}$
$\text{"+"}$ - 记录加 $\text{9}+\text{5}=\text{14}$，记录现在是 $\text{[5, -2, -4, 9, 5, 14]}$
所有得分的总和 $\text{5}+\text{(-2)}+\text{(-4)}+\text{9}+\text{5}+\text{14}=\text{27}$

示例 3：

输入：$\text{ops = ["1"]}$
输出：$\text{1}$

数据范围

• $\text{1}\le \text{ops.length}\le \text{1000}$
• $\text{ops[i]}$ 为 $\text{"C"}$、$\text{"D"}$、$\text{"+"}$，或者一个表示整数的字符串，整数范围是 [-3 × 10 4 , 3 × 10 4 ] \texttt{[-3} \times \texttt{10}^\texttt{4}\texttt{, 3} \times \texttt{10}^\texttt{4}\texttt{]} [-3×104, 3×104]
• 对于 $\text{"+"}$ 操作，题目数据保证记录此操作时前面总是存在两个有效的分数
• 对于 $\text{"C"}$ 和 $\text{"D"}$ 操作，题目数据保证记录此操作时前面总是存在一个有效的分数

解法

思路和算法

这道题需要根据记录操作的字符串列表得到每次得分的记录，并计算所有得分的总和。字符串列表中的内容有四种类型，其中有三种类型都和最后一次或最后两次得分有关，因此可以使用栈存储每次得分。

初始时栈为空。遍历记录操作的字符串列表 $\text{ops}$，根据字符串列表中的内容，分别进行相应的操作：

• 整数 $x$ 表示本回合新获得的得分是 $x$，将整数 $x$ 入栈；

• $\text{“+"}$ 表示本回合新获得的得分是前两次得分的总和，从栈内获得前两次得分，将栈顶元素 score 2 \textit{score}_2 score2​ 出栈，新栈顶元素为 score 1 \textit{score}_1 score1​，得到 score 1 \textit{score}_1 score1​ 之后将 score 2 \textit{score}_2 score2​ 入栈，则 score 1 \textit{score}_1 score1​ 和 score 2 \textit{score}_2 score2​ 为前两次得分，本回合新获得的得分是 score 1 + score 2 \textit{score}_1 + \textit{score}_2 score1​+score2​，将新获得的得分入栈；

• $\text{“D"}$ 表示本回合新获得的得分是前一次得分的两倍，栈顶元素的两倍为本回合新获得的得分，将新获得的得分入栈；

• $\text{“C"}$ 表示前一次得分无效，将其从记录中移除，将栈顶元素出栈。

遍历结束 $\text{ops}$ 之后，栈内元素即为每回合的得分。将栈内元素依次出栈并加到总和中，即可得到记录中所有得分的总和。

计算记录中所有得分的总和还有另一种做法，不需要在最后将栈内元素出栈。使用 $\text{sum}$ 表示记录中所有得分的总和，初始时 $\text{sum}=0$，在遍历 $\text{ops}$ 的过程中维护 $\text{sum}$ 的值，当 $\text{ops}$ 中的元素是整数、$\text{“+"}$ 或 $\text{“D"}$ 时将新获得的得分加到 $\text{sum}$，当 $\text{ops}$ 中的元素是 $\text{“C"}$ 时将 $\text{sum}$ 减去出栈的元素，遍历结束 $\text{ops}$ 之后，$\text{sum}$ 即为记录中所有得分的总和。

代码

class Solution {public int calPoints(String[] ops) {int sum = 0;Deque<Integer> stack = new ArrayDeque<Integer>();int length = ops.length;for (int i = 0; i < length; i++) {String op = ops[i];if ("+".equals(op)) {int score2 = stack.pop();int score1 = stack.peek();stack.push(score2);int score = score1 + score2;stack.push(score);sum += score;} else if ("D".equals(op)) {int score = stack.peek() * 2;stack.push(score);sum += score;} else if ("C".equals(op)) {sum -= stack.pop();} else {int score = Integer.parseInt(op);stack.push(score);sum += score;}}return sum;}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{ops}$ 的长度。需要遍历数组 $\text{ops}$ 一次，数组中每个元素的操作时间都是 $O(1)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\text{ops}$ 的长度。空间复杂度主要取决于栈空间，栈内的元素个数为 $O(n)$。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！