哪个角落的单元测试会失败

本文关键字：失败 单元测试 角落 | 更新日期: 2023-09-27 18:14:04

我在codiility上尝试了Fish问题，我获得了75%的正确性分数，因为结果报告我的代码失败了一个简单的测试用例。结果不报告为测试用例提供了什么输入。

你能帮我找出我的代码有什么问题，什么情况下它会失败吗?

using System;
public class Solution
{
    // Time complexity: O(N)
    // Space complexity: O(N)
    public int solution(int[] sizes, int[] direction)
    {
        if (sizes == null || direction == null)
            throw new ArgumentNullException();
        var sizesLen = sizes.Length;
        var directionLen = direction.Length;
        if (sizesLen != direction.Length)
            throw new ArgumentException();
        var len = sizesLen;
        if (len <= 1) return len;
        var survivors = new Fish[len];
        survivors[0] = new Fish(sizes[0], direction[0]);
        var curr = 0;
        for (int i = 1; i < len; i++)
        {
            var fish = new Fish(sizes[i], direction[i]);
            if (survivors[curr].Direction == 1 && fish.Direction == 0)
            {
                if (fish.Size < survivors[curr].Size) continue;
                while(curr >= 0 && 
                    fish.Size > survivors[curr].Size && 
                    survivors[curr].Direction == 1)
                {
                    curr--;
                }
            }
            survivors[++curr] = fish;
        }
        return ++curr;
    }
}
public class Fish
{
    public Fish(int size, int direction)
    {
        Size = size;
        Direction = direction;
    }
    public int Size { get; set; }
    public int Direction { get; set; }
}

哪个角落的单元测试会失败

如代码中所述，您的解决方案是O(M*N)。如问题链接中所述，代码应该在线性时间内运行。因此，我不会纠正您的解决方案，因为它最终会在更大的测试用例中失败。我将为您提供一个您可以轻松实现的线性算法。

保留一个堆栈S，初始为空

从0到n-1遍历数组A, i

当您遇到元素(例如A[i])时，执行以下操作

  • 如果堆栈S为空，则将两者(A[i], B[i])作为一对压入

  • 否则，从堆栈S中取出顶部对，比较B[top]和B[i]的值。

    而 B[top]是1, B[i]是0，那么其中一条鱼会吃掉另一条鱼。从栈S中取出，也就是最上面的元素。现在，用A[top]和A[i]的值比较哪条鱼更大。哪个更大，那条鱼就活下来。将这对放入堆栈S中，这对应于存活的鱼。继续while循环，直到条件失败如果B[top]不是1, B[i]也不是0，则直接推入新的对(A[i],B[i])

最后的堆栈S的大小，是你的答案。

注意:您可能没有通过该测试用例，因此您的解决方案超时了。例如，当N=100000时，您的解决方案将超时。

在我的解决方案中，时间复杂度最坏的情况是O(N+N) = O(2N) = O(N)。N次，因为在数组A上迭代，另一个N次，最坏的情况是由于堆栈不断收缩，因为而条件保存true。

希望有帮助!!

编辑:

假设一个=(99、98、92、91、93),和B =[1, 1, 1, 1, 0]。你的代码给出的答案是3。期望答案= 2

Edit-2:这是您修改的代码，将通过每个测试用例

public int solution(int[] sizes, int[] direction)
    {
        if (sizes == null || direction == null)
            throw new ArgumentNullException();
        var sizesLen = sizes.Length;
        var directionLen = direction.Length;
        if (sizesLen != direction.Length)
            throw new ArgumentException();
        var len = sizesLen;
        if (len <= 1) return len;
        var survivors = new Fish[len];
        survivors[0] = new Fish(sizes[0], direction[0]);
        var curr = 0;
        for (int i = 1; i < len; i++)
        {
            var fish = new Fish(sizes[i], direction[i]);
            if (survivors[curr].Direction == 1 && fish.Direction == 0)
            {
                if (fish.Size < survivors[curr].Size) continue;
                while(curr >= 0 && 
                    fish.Size > survivors[curr].Size && 
                    survivors[curr].Direction == 1)
                {
                    curr--;
                }
                if (curr >= 0)
                {
                    if (fish.Size < survivors[curr].Size && 
                         survivors[curr].Direction == 1) 
                               continue;
                }
            }
            survivors[++curr] = fish;
        }
        return ++curr;
    }
}
public class Fish
{
    public Fish(int size, int direction)
    {
        Size = size;
        Direction = direction;
    }
    public int Size { get; set; }
    public int Direction { get; set; }
}

我认为这里的意图是使用堆栈或队列。下面是两个Stack的解决方案。

  public static int Fish(int[] A, int[] B)
        {
            var downStreamFish = new Stack<int>(B.Length);
            var upStreamFish = new Stack<int>(B.Length);
            var result = B.Length;
            for (var i = 0; i < B.Length; i++)
            {
                // push the fish into up/down stream stack.
                if (B[i] == 1)
                    downStreamFish.Push(i);
                else
                    upStreamFish.Push(i);
                // check to see whether it's possible to eat a fish
                while (downStreamFish.Count > 0 && upStreamFish.Count > 0)
                {
                    var dfIndex = downStreamFish.Peek();
                    var ufIndex = upStreamFish.Peek();
                    //NOTE:downstream fish index must be less than upstream fish index in order for 'eat' to happen
                    if (dfIndex < ufIndex) 
                    {
                        if (A[dfIndex] > A[ufIndex])
                            upStreamFish.Pop();
                        else
                            downStreamFish.Pop();
                        result--; // one fish is eatten
                    }
                    else
                        break; // eat condition is not met 
                }
            }
            return result;
        }
相关文章：