赞
踩
华为OD机试 2024D卷题库疯狂收录中,刷题点这里
本专栏收录于《华为OD机试(JAVA)真题(D卷+C卷+A卷+B卷)》。
刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。
有一个荒岛,只有左右两个港口,只有一座桥连接这两个港口,现在有一群人需要从两个港口逃生,有的人往右逃生,有的往左逃生,如果两个人相遇,则PK,体力值大的能够打赢体力值小的,体力值相同则同归于尽,赢的人才能继续往前逃生,并较少相应地体力。
一行非0整数,用空格隔开,正数代表向右逃生,负数代表向左逃生。
最终能够逃生的人数。
题意是这样的:
体力值大的能够打赢体力值小的,体力值相同则同归于尽,赢的人才能继续往前逃生,并较少相应地体力。
正数代表向右逃生,负数代表向左逃生。
有点小错误,没考虑负数在左,正数在右,无法相遇的情况,感谢@迷雾追踪同学的指正。
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()); } }
改进了如果负数在桥的左侧,正数在桥的右侧,没有机会相遇的情况。
package com.guor.od; import java.util.*; /** * undefined提供算法 */ 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()); } }
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()); } }
10 20 -20 -5 10
2
正数集合:10 20 10
负数集合: -20 -5
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。