Почему мы практикуем алгоритмы? (не только для интервью)

Почему мы практикуем алгоритмы? (не только для интервью)

Решение проблем с алгоритмами может помочь научить наш разум использовать структуру данных и алгоритмы и быть готовым использовать их для решения проблем.

вместо работы с CRUD проблемы с литкодом обычно требуют хорошего понимания структур данных, таких как деревья, графы, куча, хотя большинство из них вряд ли будут использоваться в повседневной работе, но когда появляется требование (нахождение пути, короткий путь (вес на основе), обход графа/дерева, подсчет ссылок и т. д.) поможет, если мы сможем быстро найти решения, а затем сравним плюсы и минусы, чтобы получить оптимальное решение.

поэтому нам нужна практика.

Теги проблем

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

ДФС

Классический способ обхода дерева или графа начинается с узла и доходит до конца. или внутри матрицы поиск области путем перехода вверх, вниз, влево, вправо. Обычно каждое дерево или граф или проблема поиска матрицы 0–1 может быть связана с DFS.

БФС

В отличие от ДФС. BFS можно было бы сделать с очередью. Найдите следующие доступные узлы и добавьте их в очередь, пока очередь не станет пустой. в отличие от DFS, BFS больше фокусируется на всех «следующих узлах» из текущей «родительской» очереди.

Бинарный поиск

В отсортированном массиве найдите какое-нибудь значение, которое обычно попадает в эту категорию.

куча

При поиске максимума или минимума, или верхней проблемы. обычно эта структура доступна на выбранном вами языке, ее можно использовать напрямую. java, c#, python и т. д., если нет, вы также можете создать свою кучу.

попробовать

Имея словарь, создайте Trie, выполните поиск слова или частоты.

Куча

Используйте минимальный или максимальный стек, чтобы сравнить верхний 1 в стеке при циклическом просмотре некоторого массива.

Список ссылок

общие проблемы, такие как цикл поиска, общий узел между двумя списками ссылок, реверс и т. д.

Жадный

Идея состоит в том, чтобы использовать «жадное мышление», чтобы найти максимум или минимум.

Раздвижное окно

используйте начальную и конечную позицию для отслеживания начальной и конечной позиции «окна» при циклическом массиве, необходимо увеличить начало при совпадении с некоторым условием, обычно также необходимо отслеживать размер окна

Два указателя

поддерживать 2 индекса при циклическом массиве или строке

Обратное отслеживание

как и DFS, просто нужно перебирать каждую возможность для каждой рекурсии. Этот подход полезен только для небольшого количества входных значений.

Разделяй и властвуй

Идея состоит в том, чтобы найти разделитель и разделить задачу на более мелкие (например, на левую и правую), найти ответ для каждой из них и «объединить» подответы. например быстрая сортировка

Союз Найти

«Группировать» родителей к одному и тому же «корневому родителю» при поиске родителя для дочернего узла

Динамическое программирование

Существует массив для хранения «предыдущих ответов». может быть нелегко выйти с этим подходом в первый раз. но когда мы решили какую-то проблему с DFS или возвратом, мы можем обнаружить, что «некоторая проблема решена, для этих предыдущих ответов должен быть кеш». это когда DP становится решением.

Еще одна модель — «снизу вверх». попробуйте решить проблему с небольшим количеством чисел, посмотрите ответ, затем попробуйте повторно использовать предыдущий ответ, чтобы решить проблему с добавлением большего количества чисел.

Топографическая сортировка

в то время как график обхода удалите «степень выхода = 0»

Битовые манипуляции

используйте битовую операцию для решения проблемы. например битовая маска

Как решить проблемы?

По тегу

Если не знаете, с чего начать, на leetcode есть много тегов (или начните со списка выше). нажатие на каждый из них может сосредоточиться только на этих вопросах.

чтобы вы «уменьшили» уровень сложности, зная, где найти ответ (например, если вы выбрали DFS, вы уже знаете, что эта проблема должна быть решена с помощью подхода DFS)

Сначала пропустите проблемы с низким рейтингом

Те проблемы с низким рейтингом обычно возникают из-за плохого описания или не связаны с каким-либо алгоритмом или не связаны с проблемой программирования, например. чистая математика. можете пропустить эти вопросы сначала, если вы не заинтересованы.

Если вы готовитесь к интервью, сначала сосредоточьтесь на средних проблемах.

У меня действительно брали интервью Facebook, Amazon, Google и Microsoft. все они дают мне некоторые проблемы с литкодом среднего уровня, такие как top (найти 5-е по величине число среди миллионов), read4, самый длинный палиндром str, двоичный поиск, обход графа, Trie, перестановка строк и т. д. вам не нужно решать все проблемы, но убедитесь, что вы хорошо понимаете проблемы под общими тегами.

Хронология

Установите себе ограничение по времени при решении задач (например, 20 минут). это немного напрягает вас, чтобы дать ответ в течение заданного времени, а не неограниченного.

Обсуждать

Если вы застряли, не волнуйтесь, есть сотни или тысячи хороших ответов на каждый из вопросов во вкладке «Обсудить».

Вот и все. Удачного программирования!

Если вы все еще читаете меня, почему бы нам не связаться?

Подпишитесь на меня в Твиттере: https://twitter.com/Awaiskhan4040

Следуйте за мной на GitHub: https://github.com/Awaiskhan404