题目描述与示例
题目描述
有一个荒岛，只有左右两个港口，只有一座桥连接这两个港口，现在有一群人需要从两个港口逃生，有的人往右逃生，有的往左逃生，如果两个人相遇，则 pk，体力值大的能够打赢体力值小的，体力值相同则同归于尽，赢的人才能继续往前逃生，并减少相应的体力
输入描述
系列非 0 整数，用空格隔开，正数代表向右逃生，负数代表向左逃生
输出描述
最终能够逃生的人数
示例一
输入
5 10 8 -8 -5
输出
5 5
说明
8` 与 `-8` 相遇，同归于尽，`10` 遇到`-5`，打赢并减少五点体力，最终逃生的为`[5，5]`，均从右侧港口逃生，输出 `2
示例二
输入
5 6 -10
输出
1
解题思路
注意，本题和LC735. 行星碰撞几乎完全一致。唯一的区别在于，本题出现体力不相等的情况，需要进行减法操作。
代码
Python
# 题目：2023B-荒岛求生
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：栈
# 代码看不懂的地方，请直接在群上提问
# 输入体力数组
nums = list(map(int, input().split()))
# 初始化一个栈，用于维护逃生过程中的人的体力
stack = list()
# 从左到右遍历逃生的人的体力
for num in nums:
# 当前逃生的人向右移动的情况
if num > 0:
# 无需考虑栈顶元素的方向或值，直接入栈即可
stack.append(num)
# 当前逃生的人向左移动的情况
else:
# 进行while循环，退出循环的条件为以下三个条件中的一个
# 1. 栈为空栈，即原栈中没有向左的人，经过pk后所有向右的人都倒下；
# 2. 栈顶元素向左，即原栈中包含若干向左的人，经过pk后所有向右的人都倒下；
# 3. num为0，即经过pk后该人倒下
while len(stack) != 0 and stack[-1] > 0 and num != 0:
# 当前向左的人和栈顶向右的人的体力相等，则两个人均倒下
if abs(num) == stack[-1]:
# 向右的人倒下，出栈
stack.pop()
# 当前向左的人倒下，修改num为0
num = 0
# 当前向左的人的体力大于栈顶向右的人
elif abs(num) > stack[-1]:
# 向右的人倒下，出栈
right = stack.pop()
# 当前向左的人损失right点体力
# 注意num是个负数，right是个正数，使用加法修改num
num += right
# 当前向左的人的体力小于栈顶向右的人
elif abs(num) < stack[-1]:
# 向右的人损失abs(num)点体力，但仍未倒下，无需出栈
# 此处使用stack[-1] += num也可以
stack[-1] += num
# 当前向左的人倒下，修改num为0
num = 0
# 如果经过pk后，num的体力仍不为0，则需要入栈
if num != 0:
stack.append(num)
print(" ".join(str(num) for num in stack))
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] numsArr = scanner.nextLine().split(" ");
int n = numsArr.length;
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(numsArr[i]);
}
List<Integer> stack = new ArrayList<>();
for (int num : nums) {
if (num > 0) {
stack.add(num);
} else {
int i = stack.size() - 1;
while (i >= 0 && stack.get(i) > 0 && num != 0) {
if (Math.abs(num) == stack.get(i)) {
stack.remove(i);
num = 0;
} else if (Math.abs(num) > stack.get(i)) {
int right = stack.remove(i);
num += right;
} else if (Math.abs(num) < stack.get(i)) {
stack.set(i, stack.get(i) + num);
num = 0;
}
i--;
}
if (num != 0) {
stack.add(num);
}
}
}
StringBuilder result = new StringBuilder();
for (int i = 0; i < stack.size(); i++) {
result.append(stack.get(i));
if (i < stack.size() - 1) {
result.append(" ");
}
}
System.out.println(result.toString());
}
}
C++
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
int main() {
string line;
getline(cin, line);
stringstream ss(line);
vector<int> nums;
int num;
while (ss >> num) {
nums.push_back(num);
}
vector<int> stack;
for (int num : nums) {
if (num > 0) {
stack.push_back(num);
} else {
int i = stack.size() - 1;
while (i >= 0 && stack[i] > 0 && num != 0) {
if (abs(num) == stack[i]) {
stack.erase(stack.begin() + i);
num = 0;
} else if (abs(num) > stack[i]) {
int right = stack[i];
stack.erase(stack.begin() + i);
num += right;
} else if (abs(num) < stack[i]) {
stack[i] += num;
num = 0;
}
i--;
}
if (num != 0) {
stack.push_back(num);
}
}
}
for (int i = 0; i < stack.size(); i++) {
cout << stack[i];
if (i < stack.size() - 1) {
cout << " ";
}
}
cout << endl;
return 0;
}
时空复杂度
时间复杂度：O(N)。仅需一次遍历数组。
空间复杂度：O(N)。栈所占用的额外空间。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
