未分類
7 7 月 2020

大佬们来解答一下这个面试题（语言不限）

大佬们来解答一下这个面试题（语言不限）

資深大佬 : cat404 6

说有一个游戏战斗场景：左右两边各有一定数量战斗力不等（战斗力就是数组中的数值）的小兵，战斗开始的时候左边的小兵永远只会向右前进且不能回头，右边的小兵永远只会向左前进且不能回头，当两个小兵相遇的时高战斗力的小兵会把低战斗力的给淘汰掉。

现用一个数组来表示场上的所有小兵，其中正数代表左变的小兵，负数代表右边的小兵，然后实现一个函数输入这个输入返回战斗结果。

举例：

  • 输入：[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
大佬有話說 (19)

  • 資深大佬 : azcvcza

    先找到数组中的一个正数，然后 slice 数组进行求和？

  • 資深大佬 : azcvcza

    第一个

  • 資深大佬 : MoYi123

    用栈模拟战斗过程，保存战死士兵的 index，然后输出就行了

  • 資深大佬 : easonHHH

    @azcvcza #1 看[-1, -2, 3, -4, 5]

  • 資深大佬 : easonHHH

    看了一下题目感觉可以用双指针解

  • 資深大佬 : TomatoYuyuko

    设置一个窗口向右遍历，遇到负数就锁定并向左依次做对比，打得过就删除对应正数，打不过就删除负数窗口继续右移直到指向下一个负数

  • 資深大佬 : goodboy95

    第二反应是建个栈，最后就倒序输出栈元素

  • 資深大佬 : marquina

    leetcode 735，https://leetcode-cn.com/problems/asteroid-collision/

  • 資深大佬 : zhjy23212

    stack，一个个推进去，比大小，复杂度 O(n)

  • 資深大佬 : DJQTDJ

    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();
    }

  • 資深大佬 : lenqu

    C 的标准做法应该是双指针，还是挺简单的，毕竟不需要递归出最后的结果
    其他语言，用俩个数组，执行一次就能出结果

  • 資深大佬 : shilyx

    https://play.golang.org/p/E6BU5b6iOMn

  • 資深大佬 : zifangsky

    我看了下，10L 兄弟的代码在逻辑上有点不太完善，你可以试试我这种写法（算法逻辑请参考注释部分）：
    https://i.loli.net/2020/07/10/T94Rrce2nkJhwHV.png

  • 資深大佬 : zifangsky

    有个地方逻辑有点问题，我改了一下：

    //如果平局，则将其从存活数组移除，本次战斗结束
    else if(lastItem == Math.abs(arr[i])){
    survivors.remove(survivors.size() – 1);
    rightWin = false;
    break;
    }

  • 資深大佬 : xiaoming1992

    从右往左遍历正数，依次与其后的负数进行对比，正数小则移除正数，负数小则移除负数，最后剩下的就是所求

  • 資深大佬 : index90

    对向移动，可以理解成一边静止，另一边单向移动。这样问题是不是变得更简单了？

  • 資深大佬 : wolfzz

    (1)一个栈；
    (2)数组从左到右遍历；
    (3)如果栈顶为负，取出数为正, 判断胜负：
    如果负数胜，继续取下一个数字 goto(2)；
    如果正数胜，出栈,goto(3);
    (4)其他情况： 把取出数入栈
    把栈顺序输出即可

  • 資深大佬 : phpcyy

    上的说的基本上是对的，我也是这个思路实现的

    gist.github.com/phpcyy/283bc10742b89e9daa908fc2c1270820

  • 資深大佬 : whileFalse

    简单。
    首先，正数总是向右移动，负数总是向左移动。所以一旦负数达到最左边，它就不会遇到任何敌人；正数达到最右边就不会遇到任何敌人。
    那么可以构建三个数组：
    [负数逃逸区]、[战场]、[正数逃逸区]
    一开始两个逃逸区是空的；战场就是输入数组。战斗结束后战场为空，两个逃逸区相加就是结果。

    https://gist.github.com/Just4test/db4093ff0411df673f0206354ce9710f