Я просматривал проблемы с кодом, которые я решил, и искал ту, о которой было бы хорошо написать пост. Я столкнулся с проблемой Голландского национального флага и сразу понял, что это будет хорошо.
LeetCode говорит, что я решил эту проблему 12 декабря 2020 года в 18:04. Я помню этот случай, потому что смог решить его самостоятельно. Способность самостоятельно решить проблему, безусловно, является мощным положительным подкреплением. Мне, конечно, не помешает немного взбодриться после вчерашнего конкурса LeetCode . Я смог ответить только на один вопрос! Ну что ж, всегда есть следующая неделя.
Прежде чем мы перейдем к проблеме, я просто хотел рассказать об этом. На самом деле он был впервые создан Эдсгером В. Дейкстрой. Довольно аккуратно, если хотите знать мое мнение. Читайте об этом подробнее здесь .
Проблема
Учитывая массив nums с n объектами, окрашенными в красный, белый или синий, отсортируйте их на месте так, чтобы объекты одного цвета были смежными, с цветами в порядке красного, белого и синего.
Мы будем использовать целые числа 0, 1 и 2 для представления красного, белого и синего цветов соответственно.
Примеры
Пример 1: Ввод: числа = [2,0,2,1,1,0] Вывод: [0,0,1,1,2,2]
Пример 2: Ввод: числа = [2,0,1] Вывод: [0,1,2]
Пример 3: Ввод: числа = [0] Вывод: [0]
Пример 4: Ввод: числа = [1] Вывод: [1]
Ссылка на проблему
Как решить
Хороший способ обдумать эту проблему – понять, что в массиве могут быть три разных возможных числа (или цвета). По мере повторения массива для каждого из разных чисел должно выполняться другое действие.
Все двойки должны находиться в правом конце выходного массива, все нули должны быть в левом конце выходного массива, а единицы должны быть в середине.
Одна из моих первоначальных мыслей по этой проблеме заключалась в том, что должно быть несколько указателей. Один указатель для отслеживания нижней границы, один для верхней границы, а затем один, который повторяется. Указатели для границ будут увеличиваться или уменьшаться только в том случае, если позиция, соответствующая этому указателю, отсортирована правильно.
Вот шаги:
Если текущее число равно нулю, то поменяйте текущее число на число на нижней границе. Увеличьте нижнюю границу и текущий индекс на единицу.
Если текущее число равно единице, увеличьте только текущий индекс на единицу.
Если текущее число равно двум, поменяйте текущее число местами с числом на верхней границе. Уменьшите верхнюю границу на единицу.
Повторяйте этот процесс до тех пор, пока индекс для текущего не превысит значение индекса верхней границы.
Код
Вот код, который я придумал. Может быть, это и не односложно, но я все равно очень горжусь этим. Если вы хотите увидеть некоторые другие решения, вот одно из лучших и вот еще один самый рейтинговый тоже.
Несколько иллюстраций
Я нахожу иллюстрации довольно полезными для лучшего понимания шагов, связанных с алгоритмом. Давайте посмотрим на некоторые иллюстрации, которые помогут нам увидеть этот алгоритм в действии.
Ввод: [2, 1, 0, 0, 1, 2]
На рисунке А показана начальная настройка. Слева 0, ток 0, а справа 5. и, таким образом, в самый раз уменьшается на единицу.
На рисунке Б, еще раз, но на этот раз. Эти два значения будут поменяны местами. право уменьшается на единицу.
На рисунке C, таким образом, только ток увеличивается на единицу.
На рисунке D, таким образом, ток снова увеличивается на единицу.
На рисунке E, таким образом, nums [ток] заменяется на nums [слева], а затем и левый, и текущий увеличиваются на единицу.
На рисунке F, таким образом, nums[текущий] заменяется на nums[слева]. левый и текущий увеличиваются на единицу. ток больше не меньше или не равен правому, поэтому цикл while завершается, и nums возвращается в качестве выходного сигнала.
result: [0, 0, 1, 1, 2, 2]
Временная сложность
Если ‘n’ – количество элементов во входном массиве, то временная сложность этого алгоритма равна O (n), так как алгоритм требует только одного прохода.
Сложность пространства
Пространственная сложность алгоритма равна O(1). Алгоритм работает в постоянном пространстве.
Совершенствуйтесь в алгоритмах!
Алгоритмы и структуры данных довольно сложны. Мне определенно требуется некоторое время, чтобы освоиться с ними. Тем не менее, есть несколько замечательных ресурсов, и я чувствую себя обязанным поделиться некоторыми из них, которые были мне наиболее полезны. Если я пропустил что-то, что было вам полезно, обязательно упомяните их в комментариях.
Взлом интервью по кодированию — Отличный ресурс. Действительно настраивает вас на правильный лад для собеседований. Вы можете найти его здесь .
Элементы интервью по программированию — Еще одна замечательная книга. Лично мне этот нравится больше, чем CTCI, но YMMV. Вы можете найти его здесь .
Прослушивание интервью по кодированию — Не могу достаточно подчеркнуть это. Не видел, чтобы он упоминал об этом слишком часто. Объясняет закономерности, возникающие в различных задачах кодирования. Отлично подходит для предоставления общей картины всех различных проблем с алгоритмами, с которыми вы можете столкнуться. Проверить это здесь .
Динамическое программирование Grokking — Динамическое программирование – это сложно. Этот курс определенно помог мне лучше понять.
Тушар Рой — Тушар действительно знает свое дело. Его плейлист динамического программирования особенно хорош. Посмотрите на его потрясающий Канал YouTube .
Спина К Спине SWE — Отличный Канал на YouTube . Очень рекомендую.
Кевин Нотон-младший. — Еще один потрясающий канал YouTube . Отлично разбирается в проблемах и дает полезные советы.
Базовый CS — Вайдехи Джоши отлично справляется с изложением основ алгоритмов и структур данных. Ознакомьтесь с серией блогов здесь . У нее также есть подкаст , которому я показываю два больших пальца вверх.
Веб—сайт Coding Challenge – Есть много разных сайтов на выбор. Хакерранк , Кодовые войны и Немного прим. ред. все они кажутся довольно популярными. Я лично использую LeetCode . Найдите тот, который работает для вас!
Прамп — Проводите инсценированные интервью! Чем скорее, тем лучше! Предусилитель оказал мне огромную помощь.
Что ж, я надеюсь, что это было полезно. Спасибо, что прочитали мой пост, и желаю удачи в изучении структур данных и алгоритмов!
Оригинал: “https://dev.to/danielleskosky/dutch-national-flag-problem-2l5b”