Пошаговое объяснение того, как можно использовать жадный алгоритм для решения этой задачи. Я бы порекомендовал пойти и проверить детали этой проблемы и попробовать решить ее самостоятельно на любом языке программирования или просто псевдокоде.
В нем говорится, что если у вас есть массив длиной x, например a [1, 2, 3, 4, 5] и количество поворотов d равно 2, вам необходимо написать функцию для выполнения левый поворот d массива a. Представьте этот массив как очередь людей, и вы хотите, чтобы 2 человека 1, 2 с начала строки переместились в конец, чтобы получить результат массив [3, 4, 5, 1, 2]. Простой!
Это выглядит довольно просто, поэтому давайте перечислим шаги, необходимые для решения этой проблемы.
- Проходите по массиву d раз, и на первой итерации значение d равно 1.
- Вытяните первый элемент из массива, который равен 1, и добавьте его в массив a.
- Новый массив станет [2, 3, 4, 5, 1].
- Значение d на следующей итерации равно 2.
- Вытяните первый элемент из массива, который равен 2, и добавьте его в массив a.
- Новый массив станет [3, 4, 5, 1, 2].
- Итерация завершается, и мы получаем окончательный результат [3, 4, 5, 1, 2], который нужно вернуть.
Судя по всему, мы описали это решение в большой нотации O как O of d или O (d).
Напишем простую функцию для реализации этого алгоритма:
Или вы можете использовать более простую версию с циклом while:
Функция push используется для добавления значения в массив и shift для извлечения первого элемента из массива copy.
Провел все тесты на hackerrank.com и все тесты прошли.
Здорово! но я думал о разных тестовых примерах. Предположим, у нас есть тот же массив длиной 5, и на этот раз значение d равно 5, поэтому с помощью O (d) мы пройдемся 5 раз и в end результат будет точно таким же, как и исходный массив [1, 2, 3, 4, 5]. Это пустая трата 5 итераций, и мы могли бы просто вернуть исходный массив, что было бы очень быстро. Здорово! Для этого добавим одну строку вверху нашей функции:
Хорошо, продолжаем, что, если значение d равно 10? Повторите 5 раз, чтобы получить тот же результат, и затем еще 5 раз, чтобы снова получить тот же результат, что и исходный массив. То же самое означает 10, 15, 20… если вы заметили, что если длина массива a кратна d, нам не нужно делать что угодно и просто верните исходный массив a. С помощью оператора остатка % JavaScript мы можем улучшить наш код с помощью этой проверки.
С помощью этого кода, даже если значение d равно 100000…, пока остаток равен 0, нашим большим выражением нотации O будет O ( 1).
Затем возьмем еще одно большое значение d, для которого остаток не равен 0, например 12
Это означает, что мы можем избежать 5 + 5 = 10 итераций и просто вытащить первых 2 человек и поместить их в конец очереди, чтобы получить [3, 4, 5, 1, 2]
Нам нужно найти способ убрать все ненужные итерации и просто найти минимальное количество ходов, чтобы получить результат. В этом случае только 2.
Как мы получили это число 2?
2 - это остаток от 12 % 5, поэтому с этой формулой мы никогда не будем повторять одно лицо / число дважды. В этом случае новое значение d становится 2. Давайте обновим наш предыдущий код, чтобы добиться этого:
В строке №2 выше наше значение d всегда будет меньше длины массива a. В строке №4 мы проверяем значение d, которое будет значением остатка. Теперь давайте рассмотрим несколько примеров в уме.
если array.length равно 5
- а значение d равно 0, остаток будет равен 0, поэтому 0 итераций
- а значение d равно 4, остаток будет равен 4, поэтому 4 итерации
- а значение d равно 5, остаток будет равен 0, поэтому 0 итераций
- а значение d равно 6, остаток будет равен 1, поэтому 1 итерация
- а значение d равно 12, остаток будет равен 2, поэтому 2 итерации
- а значение d равно 3888886, остаток будет равен 1, поэтому только 1 итерация
Это большое улучшение. Вместо 3888886 итераций мы повторили всего один раз.
Итак, теперь мы узнали, что значение d всегда будет меньше длины массива a
Следуя концепции жадного алгоритма, как мы можем еще немного улучшить этот алгоритм?
В том же кратком и простом для понимания примере значение массива a равно [1, 2, 3, 4, 5], а на этот раз значение d равно 3.
Основываясь на нашем предыдущем оптимизированном алгоритме, нам нужно повторить 3 раза. Нарисуем это.
Мы переместили человека 1, затем 2 и, наконец, 3, чтобы получить результат [4, 5, 1, 2, 3]
Если вы сравните его с исходным массивом [1, 2, 3, 4, 5], похоже, что мы переместили 4 и 5 в начало очереди / массива. . Мы могли бы просто выполнить итерацию 2 раза от конца массива / очереди к началу.
Здесь разница составляет всего 1 итерацию, однако эта разница будет увеличиваться с увеличением значения d. Даже для такого небольшого массива, если значение d равно 4, мы можем переместить 5 из конца в начало массива / очереди. что уменьшит его на 2 итераций.
Следовательно, мы можем разделить длину массива на 2 половины, например 5/2 = 2,5 и сравните его со значением d, например 3. Если значение d больше, переместите элементы с конца массива на передний план, в противном случае переместите элементы из переднего конца в заднюю часть массива.
В этом случае 3 (и 4) больше, чем 2,5, поэтому мы можем начать вытягивать с конца и нажимать / добавлять вперед. очереди / массива. Обновленные скетчи:
Хорошо, давайте обновим наш предыдущий код, чтобы добиться этого
unshift используется для добавления элемента в начало массива в Javascript, а pop удаляет последний элемент из массива (он изменяет исходный массив). Поэтому в приведенном выше коде copy.pop() удаляет элемент из исходного массива и передает его функции unshift, которая затем добавляет его обратно в исходный массив, но впереди.
Выглядит неплохо. Отлично. Всего 2 итерации вместо 3. Замечательно (немного похлопать по плечу)
Все еще чувствуете себя жадным? Я тоже! Мне не нравятся эти 2 итерации. Что еще мы можем сделать для улучшения этого алгоритма? Допустим, у нас есть массив из 10 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], а значение d равно 5.
Хм ... Я вижу, что в этом случае мне совсем не нужно повторять. Я знаю, что значение d составляет ровно половину длины массива, что означает, что я могу просто переместить первую половину массива в конец или переместить вторую половину в начало массива. без повторения d раз и получите тот же результат.
Следовательно, нам нужно проверить, равно ли array.length/2 d. Если это так, то вытащите половину массива, добавьте ее в конец и верните новый массив.
splice - это функция, используемая для получения начального и конечного индекса / позиции массива и возврата этого фрагмента массива, в данном случае это будет slice [1, 2, 3, 4, 5]
Важно отметить, что он изменяет исходный массив (в отличие от slice) и удаляет эти нарезанные значения из исходного массива. Таким образом, он удаляет 1, 2, 3, 4, 5 из массива a, и исходный массив становится [6, 7, 8, 9, 10]
concat, как видно из названия, объединить один массив с другим. Таким образом, исходный массив был [6, 7, 8, 9, 10], а [1, 2, 3, 4, 5] был объединением этих двух массивов, возвращенных [6, 7, 8, 9, 10, 1, 2 , 3, 4, 5].
Итак, наш алгоритм теперь немного улучшен, но мы можем переместить половину элементов / людей из очереди и переместить их в конец всего за один раз.
Что теперь? можем ли мы еще немного улучшить этот алгоритм? Абсолютно!
Мы заметили 2 вещи. Во-первых, мы улучшили значение d, чтобы оно всегда было меньше длины массива, а во-вторых, мы можем извлечь x элементов из исходного массива и добавить все в один раз с функциями splice / concat, и это совершенно безопасно, потому что, как я уже упоминал, значение d меньше длины исходного массива. Так зачем просто использовать splice / concat, если мы можем переместить половину массива? Почему не на любое количество d?
например если значение d равно 3 с предыдущим массивом из 10 элементов. Мы можем просто вытащить первые 3 элемента и добавить их в конец. Что, если значение d равно 11? ну этого никогда не случится. с d = d % a.length 11 станет 1 и, конечно, если d равно 10, мы преобразовали это с этим условием if (d % a.length === 0) return a; Итак, мы хороши и можем ли мы превратить наш алгоритм с O (d) в просто O (1).
Давай сделаем это:
Все тесты все еще проходят с множеством различных комбинаций массива a и числа d.
Я хотел бы знать, сможете ли вы найти способ оптимизировать этот алгоритм, чтобы он работал еще быстрее, или у вас есть совершенно другое решение.
Спасибо за чтение!
