位置：首页-资讯-后端开发

华为OD机试 - 荒岛求生 - 栈Stack（Java 2023 B卷 100分）

2023-09-09 06:48

短信预约 -IT技能 免费直播动态提醒

在这里插入图片描述

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

有一个荒岛，只有左右两个港口，只有一座桥连接这两个港口，现在有一群人需要从两个港口逃生，有的人往右逃生，有的往左逃生，如果两个人相遇，则PK，体力值大的能够打赢体力值小的，体力值相同则同归于尽，赢的人才能继续往前逃生，并较少相应地体力。

二、输入描述

一行非0整数，用空格隔开，正数代表向右逃生，负数代表向左逃生。

三、输出描述

最终能够逃生的人数。

四、解题思路

题意是这样的：

体力值大的能够打赢体力值小的，体力值相同则同归于尽，赢的人才能继续往前逃生，并较少相应地体力。
正数代表向右逃生，负数代表向左逃生。

那就将正数加到一个集合里，负数加到一个集合里；
然后开始遍历取值；
体力值大的能够打赢体力值小的，并较少相应地体力；
体力值相同则同归于尽；
最后输出正数集合和负数集合的大小之和，最终能够逃生的人数；

五、Java算法源码

1、我的原始代码：

有点小错误，没考虑负数在左，正数在右，无法相遇的情况，感谢@迷雾追踪同学的指正。

package com.guor.od;import java.util.Scanner;import java.util.*;public class OdTest01 {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        // 一行非0整数，用空格隔开        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();        // 正数        Stack<Integer> positiveStack = new Stack<Integer>();        // 负数        Stack<Integer> negativeStack = new Stack<Integer>();        for (int j = 0; j < nums.length; j++) {            int num = nums[j];            // 正数代表向右逃生            if (num > 0) {                positiveStack.push(num);                // 负数代表向左逃生            } else {                negativeStack.push(Math.abs(num));            }            // 看最后能抵消多少            while (!positiveStack.empty() && !negativeStack.empty()) {                // 体力值大的能够打赢体力值小的                if (positiveStack.peek() > negativeStack.peek()) {                    positiveStack.push(positiveStack.pop() - negativeStack.pop());                } else if (positiveStack.peek() < negativeStack.peek()) {                    negativeStack.push(negativeStack.pop() - positiveStack.pop());                } else {// 体力值相同则同归于尽                    positiveStack.pop();                    negativeStack.pop();                }            }        }        System.out.println(positiveStack.size() + negativeStack.size());    }}

2、感谢@undefined提供的改进算法：

在这里插入图片描述

改进了如果负数在桥的左侧，正数在桥的右侧，没有机会相遇的情况。

package com.guor.od;import java.util.*;public class OdTest {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        // 一行非0整数，用空格隔开        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();        // 正数        Stack<Integer> positiveStack = new Stack<Integer>();        int ans = 0;        int leftMan = 0;        for (int j = 0; j < nums.length; j++) {            int num = nums[j];            // 正数代表向右逃生            if (num > 0) {                positiveStack.push(num);                // 负数代表向左逃生            } else {                leftMan = Math.abs(num);                // 看最后能抵消多少                while (!positiveStack.empty()) {                    // 体力值大的能够打赢体力值小的                    if (positiveStack.peek() > leftMan) {                        positiveStack.push(positiveStack.pop() - leftMan);                        leftMan = 0;                    } else {                        leftMan -= positiveStack.pop();                    }                    if(leftMan == 0) {                        break;                    }                }                //他已经抵消了所有向右相遇的人，他太累了，可以休息了                if(leftMan > 0){                    ans++;                }            }        }        System.out.println(ans + positiveStack.size());    }}

3、感谢@绿蚁新醅酒提供的改进算法，条条大道通罗马

package com.guor.od;import java.util.*;public class OdTest02 {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        // 一行非0整数，用空格隔开        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();        // 正数        Stack<Integer> positiveStack = new Stack<Integer>();        // 负数        Stack<Integer> negativeStack = new Stack<Integer>();        for (int j = 0; j < nums.length; j++) {            int num = nums[j];            // 正数,直接入栈，因为正数向右，与左边的元素都不碰撞            if (num > 0) {                positiveStack.push(num);            } else {                // 负数代表向左逃生，则需要判断是否已经有向右的，要不自己被消掉，要不消掉所有的向右的                int remain_num = Math.abs(num);                while (!positiveStack.empty()) {                    int positive_top = positiveStack.peek();                    if (remain_num > positive_top) {                        //  消除当前的正数,还可以继续碰撞                        remain_num -= positive_top;                        positiveStack.pop();                    } else if (remain_num < positive_top) {                        // 消除当前的正数，然后修改top值                        int modify_num = positive_top - num;                        positiveStack.pop();                        positiveStack.push(modify_num);                        remain_num = 0;                        break;                    } else {                        // 相等，同归于尽                        positiveStack.pop();                        remain_num = 0; // 被消除了                        break;                    }                }                // 如果还活着                if (remain_num > 0) {                    negativeStack.push(-remain_num);                }            }        }        System.out.println(positiveStack.size() + negativeStack.size());    }}