题目描述与示例
题目描述
你现在是一场采用特殊赛制投篮大赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
- 整数
x表示本回合新获得分数x +表示本回合新获得的得分是前两次得分的总和。D表示本回合新获得的得分是前一次得分的两倍。C表示本回合没有分数，并且前一次得分无效，将其从记录中移除。
请你返回记录中所有得分的总和。
输入
输入为一个字符串数组
输出描述
输出为一个整形数字
备注
1 ≤ ops.length ≤ 1000ops[i]为C、D、+，或者一个表示整数的字符串。整数范围是[−3×10^4,3×10^4]- 需要考虑异常的存在，如有异常情况，请返回
-1： - 对于
+操作，题目数据不保证记录此操作时前面总是存在两个有效的分数 - 对于
C和D操作，题目数据不保证记录此操作时前面存在一个有效的分数 - 题目输出范围不会超过整型的最大范围
示例一
输入
5 2 C D +
输出
30
说明
5 记录加 5 ，记录现在是 [5] 2 记录加 2 ，记录现在是 [5, 2] C 使前一次得分的记录无效并将其移除，记录现在是 [5]. D 记录加 2 * 5 = 10 ，记录现在是 [5, 10]. + 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15]. 所有得分的总和 5 + 10 + 15 = 30
示例二
输入
5 -2 4 C D 9 + +
输出
27
说明
5 记录加 5 ，记录现在是 [5] -2 记录加 -2 ，记录现在是 [5, -2] 4 记录加 4 ，记录现在是 [5, -2, 4] C 使前一次得分的记录无效并将其移除，记录现在是 [5, -2] D 记录加 2 * -2 = -4 ，记录现在是 [5, -2, -4] 9 记录加 9 ，记录现在是 [5, -2, -4, 9] + 记录加 -4 + 9 = 5 ，记录现在是 [5, -2, -4, 9, 5] + 记录加 9 + 5 = 14 ，记录现在是 [5, -2, -4, 9, 5, 14] 所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27
示例三
输入
1
输出
1
示例四
输入
+
输出
-1
解题思路
注意，本题和LC682. 棒球比赛几乎完全一致。唯一的区别在于，本题需要考虑异常的存在，稍微增加了难度。
对于所有的输入，我们可以分为两类：
- 数字
- 操作符，包括
"C"，"D"，"+"
这三种操作符，都是对最近的一次或两次得分进行操作。看到最近二字，我们应该马上想到使用后进先出LIFO的栈来解题，本质上也是一道表达式求值/化简类型的栈题。
我们首先构建一个空栈stack，然后遍历ops数组中的字符串record，对不同类型的record进行不同操作：
- 遇到数字型字符串：直接数字入栈，要注意将字符串类型
str转化为整数类型int。
if record.isdigit():
stack.append(int(record))
- 遇到
"D"：将栈顶元素的两倍入栈，要注意判断此时栈中元素个数len(stack)是否大于等于1。
if record == 'D' and len(stack) >= 1:
stack.append(stack[-1] * 2)
- 遇到
"C"：弹出栈顶元素，要注意判断此时栈中元素个数len(stack)是否大于等于1。
if record == 'C' and len(stack) >= 1:
stack.pop()
- 遇到
"+"：将栈顶的前两个元素相加后入栈，要注意判断此时栈中元素个数len(stack)是否大于等于2。
if record == '+' and len(stack) >= 2:
stack.append(stack[-1] + stack[-2])
- 如果不满足上述的任何一个条件，则说明此时出现异常。应该输出
-1。对于可能出现的异常，我们应该在最开始初始化一个标记isError = False，用于标记是否出现异常的标志，初始化为False表示最开始没有异常。当出现异常时，我们修改isError = True，并且break退出循环。
在循环体外，如果isError == True，说明出现了异常，应该直接输出-1，否则输出sum(stack)表示得分总和。
代码
Python
# 题目：2023Q1A-投篮大赛
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：栈
# 代码看不懂的地方，请直接在群上提问
# 输入表示n个操作的数组ops
ops = input().split(" ")
stack = list() # 初始化一个空栈，在python中可以用list表示栈
isError = False # 用于标记是否出现异常的标志，初始化为False表示没有异常
for record in ops: # 遍历整个ops数组
# 若record为数字，则直接将该数字加入栈中，注意要将str转为int
if record != 'D' and record != 'C' and record != '+':
stack.append(int(record))
# 若record为'D'，且栈长度大于等于1，则在栈顶压入两倍的原栈顶值
elif record == 'D' and len(stack) >= 1:
stack.append(stack[-1] * 2)
# 若record为'C'，且栈长度大于等于1，则弹出栈顶元素
elif record == 'C' and len(stack) >= 1:
stack.pop()
# 若record为'+'，且栈长度大于等于2，则在栈顶压入原栈顶的两个值
elif record == '+' and len(stack) >= 2:
stack.append(stack[-1] + stack[-2])
# 如果不满足上述的任何条件，说明出现了异常，
# 将isError修改为True，同时直接退出循环
else:
isError = True
break
# 如果出现异常，输出-1
# 如果没有异常，输出整个栈中数字的总和
print(-1 if isError else sum(stack))
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入表示n个操作的数组ops
String[] ops = scanner.nextLine().split(" ");
Stack<Integer> stack = new Stack<>(); // 初始化一个空栈
boolean isError = false; // 用于标记是否出现异常的标志，初始化为false表示没有异常
for (String record : ops) {
// 若record为数字，则直接将该数字加入栈中，注意要将字符串转为整数
if (!record.equals("D") && !record.equals("C") && !record.equals("+")) {
stack.push(Integer.parseInt(record));
}
// 若record为'D'，且栈长度大于等于1，则在栈顶压入两倍的原栈顶值
else if (record.equals("D") && stack.size() >= 1) {
stack.push(stack.peek() * 2);
}
// 若record为'C'，且栈长度大于等于1，则弹出栈顶元素
else if (record.equals("C") && stack.size() >= 1) {
stack.pop();
}
// 若record为'+'，且栈长度大于等于2，则在栈顶压入原栈顶的两个值的和
else if (record.equals("+") && stack.size() >= 2) {
int top1 = stack.pop();
int top2 = stack.pop();
stack.push(top2);
stack.push(top1);
stack.push(top1 + top2);
}
// 如果不满足上述的任何条件，说明出现了异常
// 将isError修改为true，同时直接退出循环
else {
isError = true;
break;
}
}
// 如果出现异常，输出-1
// 如果没有异常，输出整个栈中数字的总和
int sum = 0;
if (!isError) {
while (!stack.isEmpty()) {
sum += stack.pop();
}
}
System.out.println(isError ? -1 : sum);
scanner.close();
}
}
C++
#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
int main() {
// 输入表示n个操作的数组ops
string line;
getline(cin, line);
vector<string> ops;
size_t pos = 0;
while ((pos = line.find(' ')) != string::npos) {
ops.push_back(line.substr(0, pos));
line.erase(0, pos + 1);
}
ops.push_back(line);
stack<int> stack; // 初始化一个空栈
bool isError = false; // 用于标记是否出现异常的标志，初始化为false表示没有异常
for (const string& record : ops) {
// 若record为数字，则直接将该数字加入栈中，注意要将字符串转为整数
if (record != "D" && record != "C" && record != "+") {
stack.push(stoi(record));
}
// 若record为'D'，且栈长度大于等于1，则在栈顶压入两倍的原栈顶值
else if (record == "D" && stack.size() >= 1) {
stack.push(stack.top() * 2);
}
// 若record为'C'，且栈长度大于等于1，则弹出栈顶元素
else if (record == "C" && stack.size() >= 1) {
stack.pop();
}
// 若record为'+'，且栈长度大于等于2，则在栈顶压入原栈顶的两个值的和
else if (record == "+" && stack.size() >= 2) {
int top1 = stack.top();
stack.pop();
int top2 = stack.top();
stack.push(top1);
stack.push(top1 + top2);
}
// 如果不满足上述的任何条件，说明出现了异常
// 将isError修改为true，同时直接退出循环
else {
isError = true;
break;
}
}
// 如果出现异常，输出-1
// 如果没有异常，输出整个栈中数字的总和
int sum = 0;
if (!isError) {
while (!stack.empty()) {
sum += stack.top();
stack.pop();
}
}
cout << (isError ? -1 : sum) << endl;
return 0;
}
时空复杂度
时间复杂度：O(N)。仅需一次遍历数组。
空间复杂度：O(N)。栈所占用的额外空间。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD技术⾯试须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
