V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
cat404
V2EX  ›  程序员

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

  •  
  •   cat404 · 2020-07-10 10:36:41 +08:00 · 3163 次点击
    这是一个创建于 1357 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    举例:


    • 输入:[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 条回复    2020-07-10 16:45:07 +08:00
    azcvcza
        1
    azcvcza  
       2020-07-10 10:47:47 +08:00
    先找到数组中的一个正数,然后 slice 数组进行求和?
    azcvcza
        2
    azcvcza  
       2020-07-10 10:48:05 +08:00
    第一个
    MoYi123
        3
    MoYi123  
       2020-07-10 11:14:03 +08:00
    用栈模拟战斗过程,保存战死士兵的 index,然后输出就行了
    easonHHH
        4
    easonHHH  
       2020-07-10 11:17:25 +08:00
    @azcvcza #1 看[-1, -2, 3, -4, 5]
    easonHHH
        5
    easonHHH  
       2020-07-10 11:18:41 +08:00
    看了一下题目感觉可以用双指针解
    TomatoYuyuko
        6
    TomatoYuyuko  
       2020-07-10 11:24:15 +08:00
    设置一个窗口向右遍历,遇到负数就锁定并向左依次做对比,打得过就删除对应正数,打不过就删除负数窗口继续右移直到指向下一个负数
    goodboy95
        7
    goodboy95  
       2020-07-10 11:30:36 +08:00
    第二反应是建个栈,最后就倒序输出栈元素
    marquina
        8
    marquina  
       2020-07-10 11:32:16 +08:00
    zhjy23212
        9
    zhjy23212  
       2020-07-10 11:34:53 +08:00 via iPhone
    stack,一个个推进去,比大小,复杂度 O(n)
    DJQTDJ
        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();
    }
    lenqu
        11
    lenqu  
       2020-07-10 11:35:50 +08:00
    C 的标准做法应该是双指针,还是挺简单的,毕竟不需要递归出最后的结果
    其他语言,用俩个数组,执行一次就能出结果
    shilyx
        12
    shilyx  
       2020-07-10 11:47:17 +08:00
    zifangsky
        13
    zifangsky  
       2020-07-10 12:53:19 +08:00
    我看了下,10L 兄弟的代码在逻辑上有点不太完善,你可以试试我这种写法(算法逻辑请参考注释部分):
    https://i.loli.net/2020/07/10/T94Rrce2nkJhwHV.png
    zifangsky
        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;
    }
    xiaoming1992
        15
    xiaoming1992  
       2020-07-10 13:11:25 +08:00 via Android
    从右往左遍历正数,依次与其后的负数进行对比,正数小则移除正数,负数小则移除负数,最后剩下的就是所求
    index90
        16
    index90  
       2020-07-10 13:48:36 +08:00
    对向移动,可以理解成一边静止,另一边单向移动。这样问题是不是变得更简单了?
    wolfzz
        17
    wolfzz  
       2020-07-10 14:05:11 +08:00
    (1)一个栈;
    (2)数组从左到右遍历;
    (3)如果栈顶为负,取出数为正, 判断胜负:
    如果负数胜,继续取下一个数字 goto(2);
    如果正数胜,出栈,goto(3);
    (4)其他情况: 把取出数入栈
    把栈顺序输出即可
    phpcyy
        18
    phpcyy  
       2020-07-10 15:38:44 +08:00
    楼上的说的基本上是对的,我也是这个思路实现的

    gist.github.com/phpcyy/283bc10742b89e9daa908fc2c1270820
    whileFalse
        19
    whileFalse  
       2020-07-10 16:45:07 +08:00
    简单。
    首先,正数总是向右移动,负数总是向左移动。所以一旦负数达到最左边,它就不会遇到任何敌人;正数达到最右边就不会遇到任何敌人。
    那么可以构建三个数组:
    [负数逃逸区]、[战场]、[正数逃逸区]
    一开始两个逃逸区是空的;战场就是输入数组。战斗结束后战场为空,两个逃逸区相加就是结果。

    https://gist.github.com/Just4test/db4093ff0411df673f0206354ce9710f
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1064 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 19:06 · PVG 03:06 · LAX 12:06 · JFK 15:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.