Блог

Я попробовал проблему Fish на Codility и получил 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 amp;amp; fish.Direction == 0)
            {
                if (fish.Size < survivors[curr].Size) continue;

                while(curr >= 0 amp;amp; 
                    fish.Size > survivors[curr].Size amp;amp; 
                    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 , изначально пустой.

Выполните итерацию по массиву A , i от 0 до n-1

Скажем, когда вы сталкиваетесь с элементом A[i] , выполните следующее

• Если стек S пуст, затем вставьте оба ( A[i], B[i] ) в виде пары

• В противном случае извлеките верхнюю пару из стека S и сравните значение B[top] и B[i] .

  Пока B[top] есть 1 и B[i] есть 0 , одна из рыб съест другую. Итак, извлеките содержимое из stack 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 раз в худшем случае из-за стека, если он продолжает сокращаться, для выполнения условия while true .

Надеюсь, это поможет!!!

Редактировать: предположим, что = [ 99, 98, 92, 91, 93 ], и B = [1, 1, 1, 1, 0]. Ваш код выдает ответ как 3. Ожидаемый ответ = 2

Правка-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 amp;amp; fish.Direction == 0)
            {
                if (fish.Size < survivors[curr].Size) continue;

                while(curr >= 0 amp;amp; 
                    fish.Size > survivors[curr].Size amp;amp; 
                    survivors[curr].Direction == 1)
                {
                    curr--;
                }

                if (curr >= 0)
                {
                    if (fish.Size < survivors[curr].Size amp;amp; 
                         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 или Queue. Вот решение с двумя стеками.

   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 amp;amp; 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 resu<
        }