华为OD机试真题——投篮大赛（2025A卷：100分）Java/python/JavaScript/C++/C语言/GO六种最佳实现

2025Q1 A卷 100分 题型

本文涵盖详细解题思路、代码注释、讲解、复杂的分析以及测试用例；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

华为OD机试A卷真题《投篮大赛》：

题目名称：投篮大赛

知识点：字符串、栈操作、逻辑处理
时间限制：1秒
空间限制：256MB
限定语言：不限

---

题目描述

你作为一场特殊赛制投篮大赛的记录员，需根据操作字符串列表 ops 记录得分。规则如下：

1. 整数 x：当前回合得分为 x，直接记录。
2. +：当前回合得分为前两回合有效得分之和。
3. D：当前回合得分为前一回合有效得分的两倍。
4. C：当前回合无得分，且前一回合得分无效（需移除）。

最终返回所有有效得分的总和。若操作过程中出现异常（如操作符无法执行），返回 -1。

---

输入输出格式

• 输入：字符串数组 ops，元素为整数或操作符（C、D、+）。
• 输出：整型数字，总得分或 -1（异常时）。

约束条件：

• 1 <= ops.length <= 1000
• 整数范围：[-3*10^4, 3*10^4]
• 需处理以下异常：
  • + 操作时，前两有效得分不存在。
  • C/D 操作时，前一有效得分不存在。

---

示例

示例1
输入：5 2 C D +
输出：30
解释：

• 5 → 记录 [5]
• 2 → 记录 [5, 2]
• C → 移除 2，记录 [5]
• D → 记录 5*2=10 → [5, 10]
• + → 记录 5+10=15 → [5, 10, 15]
  总和：5+10+15=30

示例2
输入：+
输出：-1
解释：+ 操作时栈中无足够元素，触发异常。

---

Java

详细分析与解答

题目分析

题目要求模拟一个得分记录的栈操作，根据不同的操作符对栈进行相应处理。关键点在于处理每个操作时需验证前置条件是否满足，否则返回-1。最终返回所有有效得分的总和。

解题思路

1. 数据结构选择：使用动态数组（如 ArrayList）模拟栈，便于快速访问和修改末尾元素。
2. 操作处理：
   • 整数：直接入栈。
   • C：移除栈顶元素，栈为空时无效。
   • D：栈顶元素翻倍入栈，栈为空时无效。
   • +：取栈顶两个元素之和入栈，栈元素不足两个时无效。
3. 异常处理：每个操作前检查前置条件，不满足则立即返回-1。
4. 复杂度：时间复杂度 O(n)，空间复杂度 O(n)，均为最优。

代码实现

import java.util.ArrayList;
import java.util.List;public class Solution {public int calPoints(String[] ops) {List<Integer> stack = new ArrayList<>();for (String op : ops) {if (op.equals("C")) {// 检查栈是否为空if (stack.isEmpty()) {return -1;}// 移除最后一个元素stack.remove(stack.size() - 1);} else if (op.equals("D")) {// 检查栈是否为空if (stack.isEmpty()) {return -1;}// 前一个得分的两倍int last = stack.get(stack.size() - 1);stack.add(last * 2);} else if (op.equals("+")) {// 检查是否有至少两个元素if (stack.size() < 2) {return -1;}// 前两个有效得分之和int a = stack.get(stack.size() - 1);int b = stack.get(stack.size() - 2);stack.add(a + b);} else {try {// 尝试转换为整数int num = Integer.parseInt(op);stack.add(num);} catch (NumberFormatException e) {// 无效的操作数（题目保证输入合法，此分支可省略）return -1;}}}// 计算总和int sum = 0;for (int num : stack) {sum += num;}return sum;}public static void main(String[] args) {Solution solution = new Solution();// 示例测试System.out.println(solution.calPoints(new String[]{"5", "2", "C", "D", "+"})); // 30System.out.println(solution.calPoints(new String[]{"+"})); // -1}
}

代码讲解

• 栈模拟：使用 ArrayList 作为栈，支持动态扩容。
• 操作处理分支：
  • C：移除栈顶前检查是否为空。
  • D：取栈顶元素并计算双倍值。
  • +：取栈顶两个元素求和。
  • 整数转换：捕获无效转换（题目保证输入合法，此异常处理为冗余安全措施）。
• 总和计算：遍历栈元素累加。

复杂度分析

• 时间复杂度：O(n)，每个操作处理时间为 O(1)，遍历一次操作数组。
• 空间复杂度：O(n)，最坏情况所有操作均为整数入栈。

边界案例验证

1. 示例1：["5","2","C","D","+"] → 正确处理，返回30。
2. 示例2：["+"] → 立即返回-1。
3. 空栈后操作：["5","C","D"] → 第二次操作后栈空，后续D操作无效返回-1。
4. 多C操作：["5","D","C","C"] → 最终栈空，返回0。

总结

该方案通过栈模拟和前置条件检查确保操作合法性，兼顾时间与空间效率，是处理此类问题的标准最优解法。

---

Pytnon

详细分析与解答

题目分析

题目要求模拟得分记录的栈操作，处理包含整数和三种操作符（C、D、+）的输入列表，最终返回有效得分总和。若操作无法执行（如栈不满足条件），返回 -1。

解题思路

1. 数据结构选择：使用列表模拟栈，支持快速访问和修改末尾元素。
2. 操作处理逻辑：
   • 整数：直接入栈。
   • C：移除栈顶元素，栈为空时无效。
   • D：将栈顶元素翻倍后入栈，栈为空时无效。
   • +：将栈顶两个元素之和入栈，元素不足时无效。
3. 异常处理：每个操作前验证前置条件，不满足则立即返回 -1。
4. 时间复杂度：所有操作仅遍历一次，复杂度为 $O(n)$，最优。

代码实现

def calPoints(ops):stack = []for op in ops:if op == 'C':# 移除前一个得分，栈必须非空if not stack:return -1stack.pop()elif op == 'D':# 前一个得分的两倍，栈必须非空if not stack:return -1stack.append(2 * stack[-1])elif op == '+':# 前两个得分之和，栈至少两个元素if len(stack) < 2:return -1stack.append(stack[-1] + stack[-2])else:# 尝试转为整数，失败则返回-1try:num = int(op)stack.append(num)except ValueError:return -1return sum(stack)

代码讲解

• 栈操作：使用列表直接模拟栈的 push 和 pop。
• 条件检查：
  • C/D 操作前检查栈是否为空。
  • + 操作前检查栈是否有至少两个元素。
  • 整数转换失败时直接返回异常。
• 总和计算：遍历栈元素求和，时间复杂度 $O(n)$。

复杂度分析

• 时间复杂度：$O(n)$，每个操作处理时间为 $O(1)$，总操作数为 $n$。
• 空间复杂度：$O(n)$，最坏情况下所有操作均为整数入栈。

示例验证

1. 示例1：

   print(calPoints(["5", "2", "C", "D", "+"]))  # 输出：30
   

   • 处理步骤：
     • 5 → [5]
     • 2 → [5, 2]
     • C → [5]
     • D → [5, 10]
     • + → [5, 10, 15]
     • 总和：$5+10+15=30$。

2. 示例2：

   print(calPoints(["+"]))  # 输出：-1
   

   • + 操作时栈为空，直接返回 -1。

边界案例

1. 空栈后操作：

   print(calPoints(["5", "C", "D"]))  # 输出：-1
   

   • 处理 C 后栈空，后续 D 无效。

2. 多 C 操作：

   print(calPoints(["5", "D", "C", "C"]))  # 输出：0
   

   • 最终栈空，总和为 $0$。

总结

该解法通过栈模拟和严格的前置条件检查，确保所有操作合法。每个操作处理时间为 $O(1)$，总时间复杂度为 $O(n)$，空间复杂度为 $O(n)$，均为最优。此方案能高效处理大规模输入，符合题目所有约束条件。

---

JavaScript

详细分析与解答

题目分析

题目要求根据操作字符串列表模拟得分记录，处理整数和三种操作符（C、D、+）。需验证操作合法性，异常时返回 -1，否则返回有效得分总和。核心思路是用栈结构记录得分，动态调整栈内容。

---

代码实现

function calPoints(ops) {const stack = [];for (const op of ops) {if (op === 'C') {// 检查栈是否为空if (stack.length === 0) return -1;stack.pop(); // 移除最后一个元素} else if (op === 'D') {// 检查栈是否为空if (stack.length === 0) return -1;const last = stack[stack.length - 1];stack.push(last * 2); // 前一个得分的两倍} else if (op === '+') {// 检查栈是否有至少两个元素if (stack.length < 2) return -1;const a = stack[stack.length - 1];const b = stack[stack.length - 2];stack.push(a + b); // 前两个得分之和} else {// 尝试转换为整数const num = parseInt(op, 10);if (isNaN(num)) return -1; // 非整数直接返回-1stack.push(num); // 压入栈}}// 计算总和return stack.reduce((sum, num) => sum + num, 0);
}

---

代码解析与优化分析

核心逻辑

1. 栈模拟：

   • 使用数组 stack 模拟栈操作，支持动态扩容。
   • push 和 pop 方法直接操作数组末尾，时间复杂度 $O(1)$。

2. 操作处理：

   • C（移除）：检查栈是否为空，非空则弹出末尾元素。
   • D（翻倍）：检查栈是否为空，取末尾元素计算双倍值后入栈。
   • +（求和）：检查栈长度是否 ≥2，取末尾两个元素求和后入栈。
   • 整数：转换为数字后入栈，转换失败则返回 -1。

3. 异常处理：

   • 每个操作执行前检查栈状态，不满足条件立即返回 -1，避免后续无效操作。

复杂度分析

• 时间复杂度：$O(n)$，每个操作仅需常数时间，遍历一次操作数组。
• 空间复杂度：$O(n)$，最坏情况下所有操作均为整数入栈。

---

示例验证

示例1

输入：["5", "2", "C", "D", "+"]

执行过程：
5 → [5]
2 → [5, 2]
C → [5]
D → [5, 10]
+ → [5, 10, 15]
总和：5 + 10 + 15 = 30 → 正确。

示例2

输入：["+"]

执行过程：
+ → 栈长度不足2 → 立即返回-1 → 正确。

---

边界条件测试

测试1：连续 C 操作

输入：["5", "D", "C", "C"]

执行过程：
5 → [5]
D → [5, 10]
C → [5]
C → []
总和：0 → 返回0。

测试2：负数与异常操作

输入：["3", "-2", "4", "C", "D", "+"]

执行过程：
3 → [3]
-2 → [3, -2]
4 → [3, -2, 4]
C → [3, -2]
D → [3, -2, -4]
+ → [3, -2, -4, -6]
总和：3 + (-2) + (-4) + (-6) = -9 → 正确。

---

总结

• 最优性：栈结构天然适配题目需求，操作时间复杂度为 $O(1)$，整体复杂度为 $O(n)$，时间和空间效率均达到最优。
• 鲁棒性：严格的前置条件检查确保异常操作立即终止，避免无效计算。
• 扩展性：代码逻辑清晰，易于扩展其他操作符或调整规则。

---

C语言

思路总结

1. 数据结构选择：使用栈（数组模拟）来记录有效得分，便于处理最近的操作。
2. 遍历操作列表：逐个处理每个操作符或数字。
3. 异常处理：
   • + 需要前两有效得分，栈中至少两个元素。
   • D 需要前一有效得分，栈中至少一个元素。
   • C 需要前一有效得分，栈非空。
4. 结果计算：遍历栈中所有元素求和。

优化点

• 数组模拟栈：避免动态内存分配，提高效率。
• 提前终止：遇到异常立即返回，减少不必要的计算。

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int calculate(char** ops, int opsSize) {int stack[1000]; // 栈数组，假设操作数不超过1000int top = -1;    // 栈顶指针，初始化为-1表示空栈for (int i = 0; i < opsSize; i++) {char* op = ops[i];size_t len = strlen(op);// 判断操作符类型if (len == 1) {char c = op[0];if (c == '+') {// 需要前两个得分if (top < 1) {return -1;}int sum = stack[top - 1] + stack[top];stack[++top] = sum; // 压栈} else if (c == 'D') {// 需要前一个得分if (top < 0) {return -1;}int val = stack[top] * 2;stack[++top] = val;} else if (c == 'C') {// 需要前一个得分if (top < 0) {return -1;}top--; // 弹出栈顶元素} else {// 数字（如"5"）int num = atoi(op);stack[++top] = num;}} else {// 处理多位数（包括负数）int num = atoi(op);stack[++top] = num;}}// 计算总和int sum = 0;for (int i = 0; i <= top; i++) {sum += stack[i];}return sum;
}// 示例测试
int main() {// 示例1char* ops1[] = {"5", "2", "C", "D", "+"};int result1 = calculate(ops1, 5);printf("示例1输出：%d\n", result1); // 应输出30// 示例2char* ops2[] = {"+"};int result2 = calculate(ops2, 1);printf("示例2输出：%d\n", result2); // 应输出-1return 0;
}

代码解释

• 栈操作：使用数组 stack 和指针 top 模拟栈，操作符处理时检查栈的状态。
• 异常处理：在每次操作前检查栈的合法性，非法时立即返回-1。
• 结果计算：遍历栈中剩余元素求和，确保正确返回有效得分总和。

该实现时间复杂度为O(n)，空间复杂度O(n)，符合题目约束且高效。

---

C++

方法思路

本题要求根据操作字符串列表计算得分总和，并处理可能的异常情况。使用栈（或动态数组）来维护有效得分是最直接的解决方案，每次操作前检查栈状态以确保合法性。具体步骤如下：

1. 数据结构选择：使用动态数组模拟栈结构，便于快速访问和修改末尾元素。
2. 遍历操作列表：逐个处理每个操作符或数字。
3. 异常处理：
   • C 操作需栈非空，否则异常。
   • D 操作需栈非空，否则异常。
   • + 操作需栈中至少两个元素，否则异常。
4. 结果计算：遍历栈中所有元素求和。

解决代码

#include <vector>
#include <string>
#include <numeric> // 用于求和using namespace std;int calculateScore(vector<string>& ops) {vector<int> stack;for (const string& op : ops) {if (op == "C") {if (stack.empty()) return -1;stack.pop_back();} else if (op == "D") {if (stack.empty()) return -1;stack.push_back(stack.back() * 2);} else if (op == "+") {if (stack.size() < 2) return -1;int sum = stack[stack.size() - 2] + stack.back();stack.push_back(sum);} else {// 转换为整数int num = stoi(op);stack.push_back(num);}}// 计算总和return accumulate(stack.begin(), stack.end(), 0);
}// 测试示例
#include <iostream>
int main() {// 示例1vector<string> ops1 = {"5", "2", "C", "D", "+"};cout << calculateScore(ops1) << endl; // 30// 示例2vector<string> ops2 = {"+"};cout << calculateScore(ops2) << endl; // -1return 0;
}

代码解释

• 数据结构：使用 vector<int> 模拟栈，支持快速末尾操作（push_back、pop_back、back）。
• 操作处理：
  • C：移除栈顶元素，需检查栈非空。
  • D：将栈顶元素乘2后压入栈，需检查栈非空。
  • +：取栈顶前两个元素的和压入栈，需检查栈大小≥2。
  • 数字：直接转换为整数压入栈。
• 异常处理：在操作符处理前检查栈状态，不满足条件立即返回-1。
• 结果求和：使用 accumulate 函数快速计算栈中元素总和。

复杂度与优化

• 时间复杂度：O(n)，每个操作仅需常数时间处理。
• 空间复杂度：O(n)，栈最多存储所有有效得分。
• 优化点：使用 vector 的末尾操作保证高效性，提前终止异常减少计算量。此方法在时间和空间上均达到最优，无法进一步优化。

---

Go

解决思路

1. 数据结构选择：使用切片（slice）模拟栈结构，便于快速访问和修改末尾元素。
2. 遍历操作列表：逐个处理每个操作符或数字，根据规则更新栈。
3. 异常处理：
   • C、D 操作需栈非空，否则返回 -1。
   • + 操作需栈中至少有两个元素，否则返回 -1。
   • 数字转换失败时返回 -1。
4. 结果计算：遍历栈中所有元素求和。

Go 代码实现

package mainimport ("strconv"
)func calculateScore(ops []string) int {stack := make([]int, 0)for _, op := range ops {switch op {case "C":if len(stack) < 1 {return -1}stack = stack[:len(stack)-1] // 移除前一个有效得分case "D":if len(stack) < 1 {return -1}stack = append(stack, stack[len(stack)-1]*2) // 前一个得分的两倍case "+":if len(stack) < 2 {return -1}sum := stack[len(stack)-2] + stack[len(stack)-1]stack = append(stack, sum) // 前两得分之和default:num, err := strconv.Atoi(op)if err != nil {return -1 // 无效数字}stack = append(stack, num) // 记录当前得分}}// 计算总得分sum := 0for _, val := range stack {sum += val}return sum
}

代码解释

1. 栈的模拟：

   • 使用 stack := make([]int, 0) 初始化空栈。
   • 通过 append 和切片操作实现压栈和弹栈。

2. 操作处理逻辑：

   • C 操作：移除栈顶元素（stack = stack[:len(stack)-1]），若栈为空则返回 -1。
   • D 操作：取栈顶元素乘以 2 后压栈，若栈为空则返回 -1。
   • + 操作：取栈顶前两个元素之和压栈，若栈中元素不足两个则返回 -1。
   • 数字处理：转换为整数后压栈，若转换失败则返回 -1。

3. 总和计算：

   • 遍历栈中所有元素累加求和。

复杂度与优化

• 时间复杂度：O(n)，每个操作仅需常数时间处理。
• 空间复杂度：O(n)，栈最多存储所有有效得分。
• 优化点：直接使用切片操作避免了动态内存分配的开销，提前终止异常处理减少计算量。

示例测试

func main() {// 示例1：输出30ops1 := []string{"5", "2", "C", "D", "+"}println(calculateScore(ops1)) // 示例2：输出-1ops2 := []string{"+"}println(calculateScore(ops2))
}

总结

该实现利用 Go 的切片高效处理栈操作，每个步骤严格检查异常条件，确保正确性和效率。代码结构清晰，逻辑严谨，是解决该问题的最优方案。