Алгоритмы и структуры данных
Я намерен использовать этот репозиторий в качестве практической игровой площадки (KATA), а также напоминание о некоторых общих, простых, но мощных алгоритмах. Там, где элегантно буду использовать преобразователи Clojure, которые представляют собой отличные электроинструменты для обработки последовательностей. Хотя этот документ может показаться исчерпывающим, я намерен использовать его в качестве списка, в который я могу вернуться в любое время, когда мне нужно учиться. Я не реализовал все, что здесь перечислено.
Стиль письма
Код здесь не формируется в стиле, который я бы использовал для профессионального кодирования. У каждой команды есть культура и мнения о стиле кода, и лучше придерживаться этих общих руководящих принципов. Более того, код написан в первую очередь для чтения другими людьми, или все из нас будут кодировать в сборке для максимальной производительности, если бы мы были нацелены на только для читателей машины. Код, который я пишу как часть команды, может быть написан кем угодно в этой команде.
Код здесь записан в программировании Litterate благодаря EMACS и ORG-режиму. Это означает, что код, записанный в Clojure, получен из текстовых файлов, объясняющих причины, стоящие за ним. Я надеюсь, что это облегчит чтение.
Питон
Готовимся к новой проблеме
./dev-resources/new-problem.sh
--problem-path neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups
Смотрите --help .
Когда сценарий инициализации завершится, в конце появится предложенная команда для тестов:
poetry run ptw -- --
src/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups.py
tests/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups_test.py
Взаимодействие с поэзией и питестом
Например, чтобы смотреть тесты во время развития:
poetry run ptw
poetry run ptw -- -- --memray
poetry run ptw -- -- --benchmark-only
poetry run ptw -- -- --benchmark-skip
Маленький танец вокруг -- -- вероятно, можно избежать, но я предпочитаю быть очень явным в отношении того, что работает, поэтому я держу poetry как самый левый передний аргумент.
Чтобы получить пламен для памяти:
poetry run memray run -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4 "
poetry run python -m memray flamegraph memray-neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate.554244.bin
Чтобы получить пламический граф процессора (или другие графики):
poetry run python -m cProfile -o program.prof -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4, 4 "
poetry run snakeviz program.prof
Чтобы запустить тесты и получить графическую резюме:
poetry run pytest --benchmark-only --benchmark-histogram
Список обучения
Сортировка алгоритмов
- Реализуйте с нуля: пузырьковая сортировка, сортировка слияния, быстрая сортировка, сортировка кучи.
- Учитывая массив целых чисел, найдите наименьший элемент KTH, используя алгоритм быстрого выбора.
- Реализуйте алгоритм сортировки подсчета, чтобы сортировать массив целых чисел с известным диапазоном значений.
- Решите проблему «трехсторонний раздел», используя быструю сортировку, чтобы эффективно сортировать массив с дублирующими значениями.
Поиск алгоритмов
- Реализуйте с нуля: двоичный поиск (для отсортированного массива), линейный поиск.
- Учитывая повернутый сортированный массив, найдите целевой элемент, используя модифицированный бинарный поиск.
График, дерево и алгоритмы его обходов
- Реализуйте с нуля: поиск в ширине (BFS), поиск по глубине (DFS), алгоритм Dijkstra, алгоритм Bellman-Ford.
- Реализуйте разные представления: матрица смежности, список смежности.
- Найдите кратчайший путь между двумя узлами в взвешенном графике, используя алгоритм Dijkstra.
- Реализуйте бинарное дерево поиска и выполните основные операции, такие как вставка, удаление и поиск.
- Учитывая направленный график, проверьте, есть ли маршрут между двумя узлами.
- Найдите количество подключенных компонентов в неориентированном графике.
- Реализуйте топологическую сортировку для направленного ациклического графика (DAG).
- Найдите самый низкий общий предок (LCA) двух узлов в бинарном дереве.
- Учитывая двоичное дерево, проверьте, является ли это действительное двоичное дерево поиска (BST).
- Учитывая график, найдите все тесно связанные компоненты (SCCS), используя алгоритм Косараджу или алгоритм Тарджана.
- Реализуйте алгоритм Floyd-Warshall, чтобы найти самые короткие пути на все первые пути на взвешенном графике.
- Учитывая N-Ary Tree, выполните обход на уровне порядка или первую глубину (например, предварительный заказ, пост-заказ).
Динамическое программирование
- Понимание концепции разбивания проблемы на меньшие перекрывающиеся подпрограммы и использование меморизации или таблицы.
- Решите классическую проблему "Fibonacci", используя как рекурсивные, так и динамические подходы программирования.
- Учитывая набор элементов с весами и значениями, найдите максимальное значение, которое может быть получено с заданным максимальным весом, используя задачу 0-1 randack.
Жадные алгоритмы
- Понимание проблем, где локально оптимальное выборы приводит к глобально оптимальному решению.
- Реализуйте решение для «проблемы выбора активности», где вам нужно выбрать максимальное количество действий, которые не перекрываются.
- Учитывая набор монет с различными конфессиями и суммой, найдите минимальное количество монет, необходимых для изготовления этой суммы, используя жадный подход.
Алгоритмы возврата
- Решите проблему «n-Queens», чтобы поместить n Queens на шахматную доску N × N, не атакуя друг друга.
- Реализуйте решатель Sudoku для решения частично заполненной головоломки судоку.
Алгоритмы манипуляции строк
- Сопоставление строки
- Обращение строки
- Палиндром проверяет
- Учитывая две строки, проверьте, является ли одна перестановка другой.
- Реализуйте алгоритм "Rabin-Karp", чтобы найти рисунок в данном тексте.
Бит -алгоритмы манипуляции
- Побитовые операции, поиск единственного уникального элемента в массиве.
- Учитывая массив, где все числа встречаются дважды, за исключением одного числа, найдите единственное уникальное число.
- Реализуйте функцию, чтобы подсчитать количество битов, которые установлены на 1 в целом.
Алгоритмы разделения и завоевания
- Бинарный поиск, поиск максимальной суммы Subarray.
- Реализуйте алгоритм карацуба для быстрого умножения больших целых чисел.
- Найдите ближайшую пару точек среди набора точек в 2D -пространстве, используя подход Divide и Conquer.
Рандомизированные алгоритмы
- Сразите массив случайным образом на месте.
- Реализуйте алгоритм «рандомизированного выбора», чтобы найти самый маленький элемент KTH в массиве.
Техника скользящего окна
- Учитывая массив целых чисел, найдите максимальную сумму любого смежного субрайя размера k.
- Найдите самую длинную подстроение с максимально k различными символами в данной строке.
Проблемы с интервалом
- Учитывая список интервалов, слияние перекрывающихся интервалов.
- Найдите минимальное количество конференц -залов, необходимых для планирования списка интервалов.
Пытается
- Реализуйте структуру данных TRIE для эффективного поиска и поиска строки.
- Учитывая список слов, найдите самый длинный обычный префикс, используя Trie.
- Реализуйте функцию автозаполнения, используя TRIE для данного набора слов.
- Учитывая список слов, найдите все пары слов, так что конкатенация образует палиндром.
Хешинг
- Реализация хэш -функций, методы разрешения столкновений и варианты использования.
- Реализуйте хэш -таблицу с разрешением столкновения (например, цепочка или открытая адресация).
- Найдите первый не повторный символ в строке, используя хэш-карту.
- Реализуйте алгоритм Rabin-KARP для сопоставления строк с несколькими узорами.
- Найдите самую длинную подстроение без повторяющихся символов, используя хэш -карту для частоты символов.
Куча
- Внедрение Min-Heaps и Max-Heaps и их приложения (например, приоритетные очереди).
- Реализуйте Min-Heap или Max-Heap с нуля.
- Учитывая множество элементов, найдите крупнейший KTH-элемент, используя подход на основе кучи.
Матрица манипуляции
- Учитывая матрицу M × N, поверните ее на 90 градусов на месте.
- Учитывая матрицу 0s и 1s, найдите самый большой квадрат 1s (квадратная подматрица максимального размера) и верните ее площадь.
Красные черные деревья или деревья
- Реализовать операции внедрения и удаления для красного черного дерева или дерева AVL.
- Выполните ротации, чтобы сбалансировать несбалансированное бинарное дерево поиска.
Реализации структуры данных
- Массивы и списки: реализация массивов, связанных списков и их операции.
- Стеки и очереди: реализация структур данных стека и очередей и их приложений.
- Хэш -карты: внедрение хэш -карт и понимание их сложности времени.
Инструменты
Алгоритмы и структуры данных выявляются с помощью простого API RESTful для более реалистичных настройки и для более надежного теста:
(Инструменты, перечисленные здесь, могут быть специфичными для некоторых языков)
