Задание TapeEquilibrium от Codility, не пройдя 100% тестов, производительности и правильности (76% общего балла) - PullRequest
0 голосов
/ 22 сентября 2019

Извините, если я написал слишком много.Я старался быть очень подробным, чтобы найти собственный ответ при описании проблемы (решение и как я туда попал), и все же, если я этого не сделал, не оставлял сомнений читателю.Я не хочу, чтобы проблема была решена кем-то другим, просто получите несколько советов и где я должен искать, чтобы улучшить свое решение, если это возможно.Я открыт, чтобы отказаться от подхода, если он неправильный, но мне также нравится, чтобы этот подход прошел 100%, если это возможно, и если он имеет смысл и подходит в отношениях качества и усилий.Если моя идея плохая, я не против того, чтобы мне сказали, и следуйте другой, но опять же, пожалуйста, не показывайте мне код или «правильный ответ», я могу сам прогуглить или найти его здесь в SO.
Упражнение выглядит так:

Дан непустой массив A, состоящий из N целых чисел.Массив A представляет числа на ленте.

Любое целое число P, такое, что 0

 A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

Разница между двумя частями - это значение:

|(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

Другими словами, это абсолютная разница между суммой первой части и суммойвторая часть.

Например, рассмотрим массив A такой, что:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3

Мы можем разделить этолента в четырех местах:

P = 1, разница = | 3 - 10 |= 7
P = 2, разница = | 4 - 9 |= 5
P = 3, разница = | 6 - 7 |= 1
P = 4, разница = | 10 - 3 |= 7

Напишите функцию:

class Solution { public int solution(int[] A); }

, которая при непустом массиве A из N целых чисел возвращает минимальную разницу, которая может быть достигнута.

Например, с учетом:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3

функция должна возвращать 1, как описано выше.

Напишите эффективный алгоритм для следующих предположений:

N - целое число в диапазоне [2..100,000];каждый элемент массива A является целым числом в диапазоне [−1,000..1,000].


Как указано в заголовке, мое решение не так уж велико (производительность 66%; 85% в правильности; 76% как общий балл).
Этот подход я использовал вчера:

накапливается с левой и правой стороны полученного массива и проверяет, какая сторона будет меньше после добавления следующей справа отлевая сторона или ближайшая слева от правой стороны массива.
Графически идея заключалась в том, чтобы сделать два поезда: сначала локомотивы (соответственно, голову и хвост массива) каждой стороны, а затем добавить к каждому локомотиву вагоны поезда (если они есть, и если они соответствуют)и сделать оба поезда крушения .Я вроде как «добавлял вагоны в поезд, только если другой поезд был больше, чем тот, который я добавил в вагон».
Код, который я написал, работал не очень хорошо, потому что мне нужно было найти наименьшее различие , которое я мог бы между двумя разделами массива.


но я получил несколько ошибок: с отрицательными числами, смешанными с неотрицательными, массивами из двух элементов и т. Д., И еще худшими результатами (например, 65% общего балла).
Идея аналогична той, которой я придерживался сегодня:

Накапливайтесь с левой и правой стороны и проверяйте разницу между левой и правой поездами был меньше после добавления вагона слева или справа.В этом подходе я сконцентрировался на «разнице между двумя поездами , а не в добавлении вагона, если другой был больше и нашел равновесие».

В любом случае, яполучил ошибки в:

  • small_random: random small, length = 100: WRONG ANSWER, получил 269 ожидаемых 39
  • large_ones: большая последовательность, числа от -1 до 1, длина = ~ 100 000: НЕПРАВИЛЬНЫЙ ОТВЕТ, получено 228 ожидаемых 0;НЕПРАВИЛЬНЫЙ ОТВЕТ, получено 147 ожидаемых 1. (возможное переполнение?)
  • large_random random large, длина = ~ 100 000: НЕПРАВИЛЬНЫЙ ОТВЕТ, получено 202635 ожидаемых 1;НЕПРАВИЛЬНЫЙ ОТВЕТ, получил 34394, ожидал 2

Все остальные тесты были в порядке.Это код, который я написал:

using System;

class Solution {
    public int solution(int[] A)
    {
        int N = A.Length, P;
        if (N == 0)
        {
             P = 0;
        }
        else
        {
            P = findTapeEquilibrium(A, N);
        }
        return P;
    }

    private static int findTapeEquilibrium(int[] A, int N)
    {
        int I = 0, J = N - 1;
        if( N > 0 )
        {
            int leftP = A[I++], rightP = A[J--];
            bool AIsPair = N - 1 % 2 == 0;
            while((!AIsPair &&  J - I >= 0) || (AIsPair && J - I >= 1))
            {
                if (Math.Abs((leftP+A[I])-rightP) <= Math.Abs(leftP-(rightP+A[J])))
                {
                    leftP += A[I++];
                }
                else
                {
                    rightP += A[J--];
                }
            }
            return Math.Abs(leftP - rightP);
        }
        return 0;
    }
}

1 Ответ

1 голос
/ 23 сентября 2019

Итак, я остановился на решении yusheng123, которое написано на python, но его код настолько прост для понимания.
Теперь я понимаю, что делал все так плохо: пытался отладить или исправитьРешение, которое было плохо продумано.
Решение этого парня было несколько похоже на то, за которым я следовал наконец, но с огромными различиями.
Я сравнивал первый и последний элемент массива, а затем добавлял числа к голове или хвосту (аккумуляторам), в зависимости от того, будет ли разница между этими двумя значениями меньше, было ужасно: слишком сложно, слишкомсосредоточиться на полученной структуре и, самое главное, не абстрагироваться от самого массива (разделов!), чтобы найти правильный способ решения проблемы: тот факт, что вы должны найти эти разделы, не означает, что вы должны на самом делесвоего рода создание двух собственных массивов, хотя я накапливал с обоих концов, теперь я вижу, что он вообще не отделен от самой проблемы, я не создавал массивы как таковые, но процедура для этого была бы одинаковойпоследовал мой дебильный подход.
Если, напротив, я подчеркиваю разницу между головой (являющейся только первым элементом) и хвостом (являющейся суммой всех других элементов массива), то я нахожусь в более высокомуровень абстракции и тот факт, что я могу просто перебирать массив от начала до конца и добираться до решения, многое говорит в сопоставлении.
Итак, в будущем, когда я увижу, что я делаю что-то похожее на то, что я сделал, я скажу мне: «Как вы можете следовать более простому плану (более простой итерации в данном конкретном случае) и все же довольствоваться собойследуя идее, о которой вы подумали, но не слишком настаивая на этом (как я сделал в этом случае)? Не выбрасывайте свою идею в мусорное ведение пока , хотя отбросьте сложный кодсделайте его проще и попытайтесь изолировать, возможно, правдоподобную идею от реализации на данный момент , пока не найдете то, что щелкает в вашем уме, поскольку многие правила и вопросы должныпопросить выполнить то, что вы пытаетесь ".Извините, если я использую этот ответ, чтобы говорить с собой в будущем, а не говорить о самом коде целиком.
Продолжая с блестящим решением, которое я нашел в Интернете, стратегия (установка заголовка в качестве первого элемента массива и хвоста в качестве суммы остальной части массива) будет продолжаться путем установки в качестве начального значения наименьшее отличие от того, которое существует между головкой и суммой остальных элементов, а затем вы просто перебираете массив, добавляете текущий элемент в накопитель головы и уменьшаете этозначение из остатка (хвостовой аккумулятор), при этом проверяя, что если новая разница между этими двумя меньше, чем та, что была сохранена в начале, то она должна быть переопределена новым значением (что мы и хотели найти в первую очередь), это значение, которое функция будет возвращать в конце или в начале, если в массиве 0, 1 или 2 элемента).
Нет никаких вагонов, добавляющих в локомотивы (теперь я вижу, как глупо я должен звучать в ваших собственных голосах, подрывая то, что я написал).Нет необходимости в таких глупых аналогиях в этой простой проблеме с таким easy и элегантным решением.Прямо здесь: я смогу заметить, что я делаю что-то не так в будущем в подобной ситуации.
В этом подходе так много порядка.Более высокий уровень абстракции.Если бы были ошибки, их было бы легко найти, и так далее.Это «мой» окончательный код.

public int solution(int[] A)
{
    int head = A[0], tail = A.Sum() - head;
    int min_diff = Math.Abs(head - tail);
    for (int i = 1; i < A.Length; i++)
    {
        if (Math.Abs(head - tail) < min_diff)
            min_diff = Math.Abs(head - tail);
        head += A[i];
        tail -= A[i];
    }
    return min_diff;
}

Конечно, окончательная оценка этого решения составляет 100%.Просто так красиво и просто.

...