这是一个创建于 1596 天前的主题，其中的信息可能已经有所发展或是发生改变。
说有一个游戏战斗场景：左右两边各有一定数量战斗力不等（战斗力就是数组中的数值）的小兵，战斗开始的时候左边的小兵永远只会向右前进且不能回头，右边的小兵永远只会向左前进且不能回头，当两个小兵相遇的时高战斗力的小兵会把低战斗力的给淘汰掉。
现用一个数组来表示场上的所有小兵，其中正数代表左变的小兵，负数代表右边的小兵，然后实现一个函数输入这个输入返回战斗结果。
举例：
- 输入：[5, 10, -5]
- 结果：[5, 10]
- 解释：左边有战力分别为 5,10 的两个小兵，右边有一个战斗力为 5 的小兵，战斗开始的时候，5 和 10 向右一定，-5 向左移动，10 和-5 相遇，-5 小兵的战斗力是 5，被 10 淘汰掉，于是结果是 5,10
- 输入：[6, -6]
- 结果：[ ]
- 解释：左边有一个战斗力 6 的小兵，右边有一个战斗为 6 的小兵，战斗开始双方移动并相遇后因为战斗力相等均被淘汰
- 输入：[-1, -2, 3, -4, 5]
- 结果：[-1, -2, -4, 5]
- 解释：左边有 2 个小兵战斗力分别为 3,5，右边有 3 个小兵战斗力分别为 1,2,4 。战斗开始后-1 和-2 因为不能回头所以不会遇到敌方小兵，5 也同理。然后 3 和-4 相遇，3 被淘汰，所以结果是-1, -2, -4, 5
 |
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 |
Select Language