華為OD機試真題——荒島求生（2025A卷：200分）Java/python/JavaScript/C/C++/GO最佳實現

在這里插入圖片描述

2025 A卷 200分題型

本專欄內全部題目均提供Java、python、JavaScript、C、C++、GO六種語言的最佳實現方式；

并且每種語言均涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、3個測試用例以及綜合分析；

本文收錄于專欄：《2025華為OD真題目錄+全流程解析+備考攻略+經驗分享》

華為OD機試真題《荒島求生》：

文章快捷目錄

題目描述及說明

Java

python

JavaScript

C

GO

題目名稱：荒島求生

知識點：棧操作（貪心算法）、邏輯處理
時間限制：1秒
空間限制：256MB
限定語言：不限

題目描述

一個荒島上有若干人，島上只有一條路通往島嶼兩端的港口（左港口和右港口）。所有人以相同速度逃生，方向分為向左（負數）或向右（正數），其絕對值表示體力值。若兩人相遇（即一個向右的人與一個向左的人路徑重疊），則進行決斗：

體力值大的一方存活，但體力值減少對方體力值的絕對值；
若體力值相同，則同歸于盡（雙方均淘汰）。
最終存活的人可從兩端港口逃生，求逃生總人數。

輸入描述
一行非零整數，用空格分隔，正數表示向右逃生，負數表示向左逃生。數組長度不超過30000。

輸出描述
一個整數，表示最終逃生人數。

示例
輸入：5 10 8 -8 -5
輸出：2
說明：

8和-8同歸于盡；
10擊敗-5后剩余體力5；
最終存活[5, 5]，均從右港口逃生，輸出2。

Java

問題分析

人們在一個荒島逃生，方向分為左右（正負），體力值由絕對值表示。當兩人相遇（向右遇到向左）時，體力大者存活但減少對方體力值，相等則同歸于盡。最終存活的人從兩端港口逃生，求總人數。

解題思路

棧處理向右的人：向右的人壓入棧，向左的人與棧頂決斗。
決斗規則：
- 棧頂體力大：棧頂減少對方體力，存活。
- 相等：棧頂彈出，同歸于盡。
- 棧頂體力小：彈出棧頂，繼續與下一個棧頂決斗。
存活統計：棧內剩余為右港口逃生人數，未擊敗的向左人數為左港口逃生人數。

代碼實現

import java.util.ArrayDeque;
import java.util.Deque;public class Main {public static void main(String[] args) {// 示例測試int[] example1 = {5, 10, 8, -8, -5};System.out.println(escapeCount(example1)); // 輸出2int[] example2 = {3, -5};System.out.println(escapeCount(example2)); // 輸出1int[] example3 = {-3, -4, 2};System.out.println(escapeCount(example3)); // 輸出2}public static int escapeCount(int[] people) {Deque<Integer> stack = new ArrayDeque<>(); // 保存向右逃生的人int leftSurvivors = 0; // 左港口逃生人數for (int num : people) {if (num > 0) {stack.push(num); // 向右的人直接入棧} else {int k = -num; // 當前向左逃生者的體力while (k > 0) {if (stack.isEmpty()) {leftSurvivors++; // 棧空則左港口存活+1break;}int t = stack.pop(); // 取出棧頂向右的人if (t > k) {stack.push(t - k); // 棧頂體力減少k，存活k = 0; // 當前向左者被擊敗} else if (t == k) {k = 0; // 同歸于盡} else {k -= t; // 繼續與下一個棧頂決斗}}}}return stack.size() + leftSurvivors;}
}

代碼詳解

棧初始化：Deque<Integer> stack保存向右逃生的人。
遍歷處理每個人：
- 向右的人：直接壓入棧。
- 向左的人：
  - k為體力絕對值，循環處理棧頂元素。
  - 棧空則左港口存活+1。
  - 棧頂大于k：棧頂存活，體力減少k。
  - 棧頂等于k：同歸于盡。
  - 棧頂小于k：繼續處理下一個棧頂。
返回結果：棧的大小（右港口）加左港口存活人數。

示例測試

示例1：[5,10,8,-8,-5]
- 8和-8同歸于盡，10擊敗-5變為5。
- 右港口存活[5,5]，輸出2。
示例2：[3,-5]
- 3被-5擊敗，左港口存活1，輸出1。
示例3：[-3,-4,2]
- -3和-4左港口存活，2右港口存活，輸出3。

綜合分析

時間復雜度：O(N)，每個元素最多入棧和出棧一次。
空間復雜度：O(N)，棧空間最壞保存所有向右的人。
正確性：
- 棧處理保證所有相遇的向右和向左的人正確決斗。
- 左港口存活人數統計未被擊敗的向左者。
適用性：高效處理大規模數據（3萬元素）。

python

問題分析

人們在荒島上逃生，方向分為左右（正數為右，負數為左），體力值為絕對值。相遇時決斗規則：體力大者存活并減少對方體力值，相等則同歸于盡。求最終存活人數。

解題思路

棧處理向右的人：向右的人存入棧中。
處理向左的人：向左的人依次與棧頂元素決斗，直到擊敗對方或棧空。
存活統計：棧內剩余為右港口逃生者，未被擊敗的向左人數為左港口逃生者。

代碼實現

def escape_count(people):stack = []  # 保存向右逃生的人left_survivors = 0  # 左港口逃生人數for num in people:if num > 0:stack.append(num)  # 向右的人直接入棧else:k = -num  # 當前向左者的體力值while k > 0:if not stack:  # 棧空則左港口存活+1left_survivors += 1breakt = stack.pop()  # 取出棧頂向右的人if t > k:stack.append(t - k)  # 棧頂體力減少k，存活k = 0  # 當前向左者被擊敗elif t == k:k = 0  # 同歸于盡else:k -= t  # 繼續與下一個棧頂決斗return len(stack) + left_survivors# 示例測試
example1 = [5, 10, 8, -8, -5]
print(escape_count(example1))  # 輸出2example2 = [3, -5]
print(escape_count(example2))  # 輸出1example3 = [-3, -4, 2]
print(escape_count(example3))  # 輸出2

代碼詳解

棧初始化：stack保存所有向右逃生的人。
遍歷處理每個人：
- 向右的人：直接加入棧中（stack.append(num)）。
- 向左的人：
  - 取絕對值k表示體力值。
  - 循環處理棧頂元素：
    - 棧空：左港口存活+1，退出循環。
    - 棧頂體力更大：棧頂存活，體力減少k，當前向左者被擊敗（k=0）。
    - 體力相等：同歸于盡（k=0）。
    - 棧頂體力更小：繼續處理下一個棧頂（k -= t）。
返回結果：棧長度（右港口存活） + 左港口存活人數。

示例測試

示例1：[5, 10, 8, -8, -5]
- 8與-8同歸于盡。
- 10擊敗-5后變為5。
- 右港口存活[5,5]，總人數2。
示例2：[3, -5]
- 3被-5擊敗，左港口存活1。
示例3：[-3, -4, 2]
- -3和-4左港口存活，2右港口存活，總人數2。

綜合分析

時間復雜度：O(N)，每個元素最多入棧和出棧一次。
空間復雜度：O(N)，棧空間最壞保存所有向右的人。
正確性：嚴格處理決斗規則，確保棧和左港口人數正確統計。
適用性：高效處理大規模數據（如3萬元素）。

JavaScript

問題分析

人們在荒島上逃生，方向分為左右（正數右，負數左），體力值為絕對值。相遇時決斗規則：體力大者存活并減少對方體力值，相等則同歸于盡。求最終存活人數。

解題思路

棧處理向右的人：向右的人存入棧中。
處理向左的人：向左的人依次與棧頂元素決斗，直到擊敗對方或棧空。
存活統計：棧內剩余為右港口逃生者，未被擊敗的向左人數為左港口逃生者。

代碼實現

function escapeCount(people) {let stack = [];       // 保存向右逃生的人let leftSurvivors = 0; // 左港口逃生人數for (const num of people) {if (num > 0) {stack.push(num); // 向右的人直接入棧} else {let k = -num;   // 當前向左者的體力值while (k > 0) {if (stack.length === 0) { // 棧空則左港口存活+1leftSurvivors++;break;}const t = stack.pop(); // 取出棧頂向右的人if (t > k) {stack.push(t - k); // 棧頂體力減少k，存活k = 0;            // 當前向左者被擊敗} else if (t === k) {k = 0;            // 同歸于盡} else {k -= t;           // 繼續與下一個棧頂決斗}}}}return stack.length + leftSurvivors;
}// 示例測試
const example1 = [5, 10, 8, -8, -5];
console.log(escapeCount(example1)); // 輸出2const example2 = [3, -5];
console.log(escapeCount(example2)); // 輸出1const example3 = [-3, -4, 2];
console.log(escapeCount(example3)); // 輸出2

代碼詳解

棧初始化：stack數組保存向右逃生的人。
遍歷處理每個人：
- 向右的人：直接壓入棧（stack.push(num)）。
- 向左的人：
  - 取絕對值k表示體力值。
  - 循環處理棧頂元素：
    - 棧空：左港口存活+1。
    - 棧頂體力更大：棧頂存活，體力減少k。
    - 體力相等：同歸于盡。
    - 棧頂體力更小：繼續處理下一個棧頂（k -= t）。
返回結果：棧長度（右港口存活人數） + 左港口存活人數。

示例測試

示例1：[5, 10, 8, -8, -5]
- 8和-8同歸于盡。
- 10擊敗-5后變為5。
- 右港口存活[5,5]，總人數2。
示例2：[3, -5]
- 3被-5擊敗，左港口存活1。
示例3：[-3, -4, 2]
- -3和-4左港口存活，2右港口存活，總人數3。

綜合分析

時間復雜度：O(N)，每個元素最多入棧和出棧一次。
空間復雜度：O(N)，棧空間最壞保存所有向右的人。
正確性：嚴格處理決斗規則，確保棧和左港口人數正確統計。
適用性：高效處理大規模數據（如3萬元素）。

C++

問題分析

解題思路

棧處理向右的人：向右的人存入棧中。
處理向左的人：向左的人依次與棧頂元素決斗，直到擊敗對方或棧空。
存活統計：棧內剩余為右港口逃生者，未被擊敗的向左人數為左港口逃生者。

代碼實現

#include <iostream>
#include <vector>
using namespace std;int escapeCount(vector<int>& people) {vector<int> stack;       // 保存向右逃生的人（用vector模擬棧）int leftSurvivors = 0;   // 左港口逃生人數for (int num : people) {if (num > 0) {stack.push_back(num); // 向右的人直接入棧} else {int k = -num;        // 當前向左者的體力值（取絕對值）while (k > 0) {if (stack.empty()) { // 棧空則左港口存活+1leftSurvivors++;break;}int t = stack.back(); // 取棧頂元素stack.pop_back();     // 彈出棧頂if (t > k) {stack.push_back(t - k); // 棧頂體力減少k，存活k = 0;            // 當前向左者被擊敗} else if (t == k) {k = 0;            // 同歸于盡} else {k -= t;           // 繼續與下一個棧頂決斗}}}}return stack.size() + leftSurvivors;
}int main() {// 示例測試vector<int> example1 = {5, 10, 8, -8, -5};cout << escapeCount(example1) << endl; // 輸出2vector<int> example2 = {3, -5};cout << escapeCount(example2) << endl; // 輸出1vector<int> example3 = {-3, -4, 2};cout << escapeCount(example3) << endl; // 輸出2return 0;
}

代碼詳解

棧初始化：
```
vector<int> stack; // 使用vector模擬棧，便于動態操作
```
- 使用vector的push_back和pop_back實現棧的壓入和彈出。

遍歷處理每個人：

向右的人：

stack.push_back(num); // 直接存入棧尾

向左的人：

int k = -num; // 取絕對值作為體力值
while (k > 0) {if (stack.empty()) {leftSurvivors++; // 棧空則左港口存活+1break;}int t = stack.back(); // 取棧頂元素stack.pop_back();     // 彈出棧頂

循環處理棧頂元素，直到擊敗所有向左者或棧空。

決斗規則：

if (t > k) {        // 棧頂體力更大stack.push_back(t - k);k = 0;
} else if (t == k) { // 同歸于盡k = 0;
} else {             // 棧頂體力更小k -= t;
}

棧頂存活時重新壓入剩余體力，否則繼續處理。

返回結果：

return stack.size() + leftSurvivors; // 右港口存活數 + 左港口存活數

示例測試

示例1：[5, 10, 8, -8, -5]
- 8與-8同歸于盡，10擊敗-5后剩余5。
- 右港口存活[5,5]，總人數2。
示例2：[3, -5]
- 3被-5擊敗，左港口存活1。
示例3：[-3, -4, 2]
- -3和-4左港口存活，2右港口存活，總人數2。

綜合分析

時間復雜度：O(N)
- 每個元素最多入棧和出棧一次，總操作次數與輸入規模成線性關系。
空間復雜度：O(N)
- 棧空間最壞保存所有向右逃生者（例如輸入全為正數）。
正確性：
- 嚴格模擬決斗規則，確保棧頂元素與向左者正確抵消。
- 左港口存活數統計未被擊敗的向左者。
適用性：
- 高效處理大規模數據：3萬元素可在1秒內處理完畢。
- 代碼簡潔性：使用vector模擬棧，避免復雜數據結構。
為什么這是最佳實現？
- 貪心策略：每次優先處理最近的向右者，保證局部最優。
- 無需回溯：棧操作直接覆蓋所有可能的相遇情況。
- 低常數開銷：直接操作內存，無遞歸或復雜計算。

C

問題分析

解題思路

棧處理向右的人：向右的人存入棧中。
處理向左的人：向左的人依次與棧頂元素決斗，直到擊敗對方或棧空。
存活統計：棧內剩余為右港口逃生者，未被擊敗的向左人數為左港口逃生者。

代碼實現

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 30000  // 題目規定輸入數組長度不超過30000int escapeCount(int people[], int size) {int stack[MAX_SIZE]; // 模擬棧，存儲向右逃生的人int top = 0;          // 棧頂指針（指向下一個可插入的位置）int left_survivors = 0; // 左港口逃生人數for (int i = 0; i < size; i++) {int num = people[i];if (num > 0) {stack[top++] = num; // 向右的人入棧} else {int k = -num;       // 當前向左者的體力值（取絕對值）while (k > 0) {if (top == 0) { // 棧空則左港口存活+1left_survivors++;break;}int t = stack[--top]; // 取出棧頂元素if (t > k) {stack[top++] = t - k; // 棧頂體力減少k，存活k = 0;            // 當前向左者被擊敗} else if (t == k) {k = 0;            // 同歸于盡} else {k -= t;           // 繼續與下一個棧頂決斗}}}}return top + left_survivors; // 棧中剩余人數 + 左港口存活人數
}int main() {// 示例測試int example1[] = {5, 10, 8, -8, -5};printf("%d\n", escapeCount(example1, 5)); // 輸出2int example2[] = {3, -5};printf("%d\n", escapeCount(example2, 2)); // 輸出1int example3[] = {-3, -4, 2};printf("%d\n", escapeCount(example3, 3)); // 輸出2return 0;
}

代碼詳解

棧初始化：

int stack[MAX_SIZE]; // 用數組模擬棧
int top = 0;         // 棧頂指針（指向下一個空位）

數組stack存儲向右逃生的人，top表示棧頂位置。

遍歷處理每個人：

向右的人：

stack[top++] = num; // 直接存入棧頂

向左的人：

int k = -num;       // 取絕對值
while (k > 0) {if (top == 0) { // 棧空則左港口存活+1left_survivors++;break;}int t = stack[--top]; // 取出棧頂元素

循環處理棧頂元素，直到擊敗所有向左者或棧空。

決斗規則：

if (t > k) {          // 棧頂體力更大stack[top++] = t - k; // 棧頂存活，減少k體力k = 0;
} else if (t == k) {  // 同歸于盡k = 0;
} else {              // 棧頂體力更小k -= t;
}

返回結果：

return top + left_survivors; // 棧剩余人數 + 左港口存活人數

示例測試

示例1：{5, 10, 8, -8, -5}
- 8與-8同歸于盡，10擊敗-5后剩余5。
- 右港口存活[5,5]，總人數2。
示例2：{3, -5}
- 3被-5擊敗，左港口存活1。
示例3：{-3, -4, 2}
- -3和-4左港口存活，2右港口存活，總人數2。

綜合分析

時間復雜度：O(N)
- 每個元素最多入棧和出棧一次，總操作次數與輸入規模成線性關系。
空間復雜度：O(MAX_SIZE)
- 棧空間固定為MAX_SIZE，滿足題目約束（數組長度≤30000）。
正確性：
- 嚴格模擬決斗規則，確保棧頂元素與向左者正確抵消。
- 左港口存活數統計未被擊敗的向左者。
適用性：
- 高效處理大規模數據：3萬元素可在1秒內處理完畢。
- 低內存消耗：使用固定大小的數組避免動態內存分配。
為什么這是最佳實現？
- 貪心策略：每次優先處理最近的向右者，保證局部最優。
- 無需動態內存：預先分配棧數組，減少內存管理開銷。
- 代碼簡潔：直接操作數組，避免復雜數據結構。

GO

問題分析

解題思路

棧處理向右的人：向右的人存入棧中。
處理向左的人：向左的人依次與棧頂元素決斗，直到擊敗對方或棧空。
存活統計：棧內剩余為右港口逃生者，未被擊敗的向左人數為左港口逃生者。

代碼實現

package mainimport "fmt"func escapeCount(people []int) int {stack := make([]int, 0)     // 保存向右逃生的人（用切片模擬棧）leftSurvivors := 0          // 左港口逃生人數for _, num := range people {if num > 0 {stack = append(stack, num) // 向右的人直接入棧} else {k := -num                   // 當前向左者的體力值（取絕對值）for k > 0 {if len(stack) == 0 {     // 棧空則左港口存活+1leftSurvivors++break}// 取出棧頂元素t := stack[len(stack)-1]stack = stack[:len(stack)-1] // 彈出棧頂if t > k {stack = append(stack, t-k) // 棧頂體力減少k，存活k = 0                      // 當前向左者被擊敗} else if t == k {k = 0                      // 同歸于盡} else {k -= t                     // 繼續與下一個棧頂決斗}}}}return len(stack) + leftSurvivors // 右港口存活數 + 左港口存活數
}func main() {// 示例測試example1 := []int{5, 10, 8, -8, -5}fmt.Println(escapeCount(example1)) // 輸出2example2 := []int{3, -5}fmt.Println(escapeCount(example2)) // 輸出1example3 := []int{-3, -4, 2}fmt.Println(escapeCount(example3)) // 輸出2
}

代碼詳解

棧初始化：
```
stack := make([]int, 0) // 使用切片模擬棧
```
- Go 的切片（slice）動態擴展，非常適合模擬棧的 push 和 pop 操作。

遍歷處理每個人：

向右的人：

stack = append(stack, num) // 追加到切片末尾（入棧）

向左的人：

k := -num // 取絕對值
for k > 0 {if len(stack) == 0 {leftSurvivors++ // 棧空則左港口存活+1break}t := stack[len(stack)-1]     // 取棧頂元素stack = stack[:len(stack)-1]  // 彈出棧頂

循環處理棧頂元素，直到擊敗所有向左者或棧空。

決斗規則：

if t > k {stack = append(stack, t-k) // 棧頂存活，減少k體力k = 0
} else if t == k {k = 0                     // 同歸于盡
} else {k -= t                    // 繼續與下一個棧頂決斗
}

返回結果：
```
return len(stack) + leftSurvivors
```
- 棧的長度即為右港口存活人數，加上左港口存活人數。

示例測試

示例1：[5, 10, 8, -8, -5]
- 8和-8同歸于盡，10擊敗-5后剩余5。
- 右港口存活[5,5]，總人數2。
示例2：[3, -5]
- 3被-5擊敗，左港口存活1。
示例3：[-3, -4, 2]
- -3和-4左港口存活，2右港口存活，總人數3。

綜合分析

時間復雜度：O(N)
- 每個元素最多入棧和出棧一次，總操作次數與輸入規模成線性關系。
空間復雜度：O(N)
- 棧空間最壞保存所有向右逃生者（例如輸入全為正數）。
正確性：
- 嚴格模擬決斗規則，確保棧頂元素與向左者正確抵消。
- 左港口存活數統計未被擊敗的向左者。
適用性：
- 高效處理大規模數據：3萬元素可在1秒內處理完畢。
- 動態內存管理：Go 的切片自動擴容，避免手動內存分配。
為什么這是最佳實現？
- 貪心策略：每次優先處理最近的向右者，保證局部最優。
- 代碼簡潔：利用切片的動態特性，簡化棧操作。
- 低內存開銷：切片按需分配內存，避免固定數組的空間浪費。