说有一个游戏战斗场景:左右两边各有一定数量战斗力不等(战斗力就是数组中的数值)的小兵,战斗开始的时候左边的小兵永远只会向右前进且不能回头,右边的小兵永远只会向左前进且不能回头,当两个小兵相遇的时高战斗力的小兵会把低战斗力的给淘汰掉。
现用一个数组来表示场上的所有小兵,其中正数代表左变的小兵,负数代表右边的小兵,然后实现一个函数输入这个输入返回战斗结果。
举例:
1
azcvcza 2020-07-10 10:47:47 +08:00
先找到数组中的一个正数,然后 slice 数组进行求和?
|
2
azcvcza 2020-07-10 10:48:05 +08:00
第一个
|
3
MoYi123 2020-07-10 11:14:03 +08:00
用栈模拟战斗过程,保存战死士兵的 index,然后输出就行了
|
5
easonHHH 2020-07-10 11:18:41 +08:00
看了一下题目感觉可以用双指针解
|
6
TomatoYuyuko 2020-07-10 11:24:15 +08:00
设置一个窗口向右遍历,遇到负数就锁定并向左依次做对比,打得过就删除对应正数,打不过就删除负数窗口继续右移直到指向下一个负数
|
7
goodboy95 2020-07-10 11:30:36 +08:00
第二反应是建个栈,最后就倒序输出栈元素
|
8
marquina 2020-07-10 11:32:16 +08:00
leetcode 735,https://leetcode-cn.com/problems/asteroid-collision/
|
9
zhjy23212 2020-07-10 11:34:53 +08:00 via iPhone
stack,一个个推进去,比大小,复杂度 O(n)
|
10
DJQTDJ 2020-07-10 11:35:36 +08:00
public int[] test(int[] a) {
LinkedList<Integer> s = new LinkedList<>(); for (int i = 0; i < a.length; i++) { if (a[i] > 0 || s.isEmpty() || s.getLast() < 0) s.add(a[i]); else if (s.getLast() <= -a[i]) if (s.pollLast() < -a[i]) i--; } return s.stream().mapToInt(i->i).toArray(); } |
11
lenqu 2020-07-10 11:35:50 +08:00
C 的标准做法应该是双指针,还是挺简单的,毕竟不需要递归出最后的结果
其他语言,用俩个数组,执行一次就能出结果 |
12
shilyx 2020-07-10 11:47:17 +08:00
|
13
zifangsky 2020-07-10 12:53:19 +08:00
我看了下,10L 兄弟的代码在逻辑上有点不太完善,你可以试试我这种写法(算法逻辑请参考注释部分):
https://i.loli.net/2020/07/10/T94Rrce2nkJhwHV.png |
14
zifangsky 2020-07-10 13:02:38 +08:00
有个地方逻辑有点问题,我改了一下:
//如果平局,则将其从存活数组移除,本次战斗结束 else if(lastItem == Math.abs(arr[i])){ survivors.remove(survivors.size() - 1); rightWin = false; break; } |
15
xiaoming1992 2020-07-10 13:11:25 +08:00 via Android
从右往左遍历正数,依次与其后的负数进行对比,正数小则移除正数,负数小则移除负数,最后剩下的就是所求
|
16
index90 2020-07-10 13:48:36 +08:00
对向移动,可以理解成一边静止,另一边单向移动。这样问题是不是变得更简单了?
|
17
wolfzz 2020-07-10 14:05:11 +08:00
(1)一个栈;
(2)数组从左到右遍历; (3)如果栈顶为负,取出数为正, 判断胜负: 如果负数胜,继续取下一个数字 goto(2); 如果正数胜,出栈,goto(3); (4)其他情况: 把取出数入栈 把栈顺序输出即可 |
18
phpcyy 2020-07-10 15:38:44 +08:00
|
19
whileFalse 2020-07-10 16:45:07 +08:00
简单。
首先,正数总是向右移动,负数总是向左移动。所以一旦负数达到最左边,它就不会遇到任何敌人;正数达到最右边就不会遇到任何敌人。 那么可以构建三个数组: [负数逃逸区]、[战场]、[正数逃逸区] 一开始两个逃逸区是空的;战场就是输入数组。战斗结束后战场为空,两个逃逸区相加就是结果。 https://gist.github.com/Just4test/db4093ff0411df673f0206354ce9710f |