跳至主要內容

2025A-投篮大赛

题目描述

你现在是一场采用特殊赛制投篮大赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：

  1. 整数 x 表示本回合新获得分数 x
  2. + 表示本回合新获得的得分是前两次得分的总和。
  3. D 表示本回合新获得的得分是前一次得分的两倍。
  4. C 表示本回合没有分数，并且前一次得分无效，将其从记录中移除。

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

输入

输入为一个字符串数组

输出描述

输出为一个整形数字

备注

  1. 1 ≤ ops.length ≤ 1000
  2. ops[i] 为 C、D、+，或者一个表示整数的字符串。整数范围是 [−3×10^4,3×10^4]
  3. 需要考虑异常的存在，如有异常情况，请返回-1：
  4. 对于 + 操作，题目数据不保证记录此操作时前面总是存在两个有效的分数
  5. 对于 C 和 D 操作，题目数据不保证记录此操作时前面存在一个有效的分数
  6. 题目输出范围不会超过整型的最大范围

示例一

输入

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. 棒球比赛几乎完全一致。唯一的区别在于，本题需要考虑异常的存在，稍微增加了难度。

对于所有的输入，我们可以分为两类：

  1. 数字
  2. 操作符，包括"C"，"D"，"+"

这三种操作符，都是对最近的一次或两次得分进行操作。看到最近二字，我们应该马上想到使用后进先出LIFO的栈来解题，本质上也是一道表达式求值/化简类型的栈题。

我们首先构建一个空栈stack，然后遍历ops数组中的字符串record，对不同类型的record进行不同操作：

1、遇到数字型字符串：直接数字入栈，要注意将字符串类型str转化为整数类型int。

if record.isdigit():
    stack.append(int(record))

2、遇到"D"：将栈顶元素的两倍入栈，要注意判断此时栈中元素个数len(stack)是否大于等于1。

if record == 'D' and len(stack) >= 1:
    stack.append(stack[-1] * 2)

3、遇到"C"：弹出栈顶元素，要注意判断此时栈中元素个数len(stack)是否大于等于1。

if record == 'C' and len(stack) >= 1:
    stack.pop()

4、遇到"+"：将栈顶的前两个元素相加后入栈，要注意判断此时栈中元素个数len(stack)是否大于等于2。

if record == '+' and len(stack) >= 2:
    stack.append(stack[-1] + stack[-2])

5、如果不满足上述的任何一个条件，则说明此时出现异常。应该输出-1。对于可能出现的异常，我们应该在最开始初始化一个标记isError = False，用于标记是否出现异常的标志，初始化为False表示最开始没有异常。当出现异常时，我们修改isError = True，并且break退出循环。

在循环体外，如果isError == True，说明出现了异常，应该直接输出-1，否则输出sum(stack)表示得分总和。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 免费获取华为 OD 笔试真题题库和视频

# 输入表示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;
}

Node JavaScript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 读取一行输入
rl.on('line', (line) => {
    // 输入表示 n 个操作的数组 ops
    const ops = line.trim().split(" ");

    const stack = []; // 初始化一个空栈
    let isError = false; // 是否出现异常的标志

    for (const record of ops) {
        // 若 record 为数字，则将该数字转为整数后压入栈
        if (record !== 'D' && record !== 'C' && record !== '+') {
            const num = parseInt(record);
            if (isNaN(num)) {
                isError = true;
                break;
            }
            stack.push(num);
        }
        // 若 record 为 'D'，且栈中至少有一个元素，则压入栈顶元素的两倍
        else if (record === 'D' && stack.length >= 1) {
            stack.push(stack[stack.length - 1] * 2);
        }
        // 若 record 为 'C'，且栈中至少有一个元素，则弹出栈顶
        else if (record === 'C' && stack.length >= 1) {
            stack.pop();
        }
        // 若 record 为 '+'，且栈中至少有两个元素，则压入栈顶两个数之和
        else if (record === '+' && stack.length >= 2) {
            const top1 = stack.pop();
            const top2 = stack.pop();
            stack.push(top2);
            stack.push(top1);
            stack.push(top1 + top2);
        }
        // 若不满足以上任意条件，则标记为错误并终止处理
        else {
            isError = true;
            break;
        }
    }

    // 如果出现异常输出 -1，否则输出栈中所有元素的和
    if (isError) {
        console.log(-1);
    } else {
        const sum = stack.reduce((acc, val) => acc + val, 0);
        console.log(sum);
    }

    rl.close();
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    reader := bufio.NewReader(os.Stdin)
    input, _ := reader.ReadString('\n')
    ops := strings.Fields(strings.TrimSpace(input))  // 将输入拆分为操作数组

    stack := []int{}         // 初始化一个空栈
    isError := false         // 标记是否出现异常，初始化为false表示没有异常

    // 遍历ops数组中的每一个操作
    for _, record := range ops {
        // 若record为数字，将该数字加入栈
        if record != "D" && record != "C" && record != "+" {
            num, err := strconv.Atoi(record)
            if err == nil {
                stack = append(stack, num)
            }
        // 若record为'D'，且栈长度大于等于1，在栈顶压入两倍的原栈顶值
        } else if record == "D" && len(stack) >= 1 {
            stack = append(stack, stack[len(stack)-1]*2)
        // 若record为'C'，且栈长度大于等于1，弹出栈顶元素
        } else if record == "C" && len(stack) >= 1 {
            stack = stack[:len(stack)-1]
        // 若record为'+'，且栈长度大于等于2，在栈顶压入栈顶的两个值之和
        } else if record == "+" && len(stack) >= 2 {
            stack = append(stack, stack[len(stack)-1]+stack[len(stack)-2])
        // 如果以上条件均不满足，说明出现异常
        } else {
            isError = true
            break
        }
    }

    // 如果出现异常，输出-1；如果没有异常，输出栈中所有元素的总和
    if isError {
        fmt.Println("-1")
    } else {
        sum := 0
        for _, val := range stack {
            sum += val
        }
        fmt.Println(sum)
    }
}

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组。

空间复杂度：O(N)。栈所占用的额外空间。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法