Я просто хочу пройти алгоритмический собес 🥺
Тут будут какие-то заметки, когда я столкнусь с чем-то сложным/интересным/новым для себя.
Кроме этого сформирую базу ссылок того что читал/смотрел/изучал.
На текущий момент основная платформа LeetCode.
- KMP — поиск подстроки в строке за O(m + n). Встретился в 28. Брутфорс ушёл в TL. Алгос списал с псевдокода на вики: Knuth–Morris–Pratt algorithm.
- Prefix sum — быстрый ответ на множество вопросов "Какая сумма на подмассиве от L до R?" (pref[0] = a[0]; pref[i] = pref[i - 1] + a[i]. Q: pref[r] - pref[l - 1] или pref[r] если l == 0). Точ в точ задача 303. Интересное и легкое усложнение задачи в 724.
- Kadane's algorithm — подмассив с наибольшей суммой (tSum += a[i]; tSum = max(tSum, a[i]); res = max(res, tSum)).
- В 1408 допустил ошибку при оценке временной сложности. Там не O(N^2*L), а O(N*L), где L сумма длин всех строк. Потому что несмотря на вложенный цикл мы выполняем поиск в строке за длину строку, а циклы порождают сравнение строки с каждой другой. Где каждую другую можно заменить на сумму длин всех строк (L). Поэтому оценка количество строк умноженное на сумму длин (N*L). Что меньше моей изначальной оценки, так как в условии задачи максимальная длинна строк 30, а количество слов 100.
- Долго мучался с 11 (бассейн с двумя бортиками). Брутфорс конечно не зашёл, прочитал подсказки, частично дорешал, не справившись отловить баг пошёл в обсуждения к задаче. Посмотря на чужой код понял, что нафантазировал ненужные дополнительные условия (diff). В итоге списал с чужого кода, но свою ошибку понял (кажется). Upd. 121 задача мне сильно напомнила эту.
- В 1337 первый раз использовал кучу. В условии задачи условия повторяют сравнение пары интов. Если первые элементы (сила строки AKA кол-во единиц в ней) равны, то сравниваем вторые (индекс в массиве по задаче). Так как по условию нам нужно вывести слабейших, то используем кучу для поиска минимума (
std::priority_queue<T, vector<T>, greater<T>>). - В 231 сраные граничные случаи с -2^31 и 2^31-1.
- brestprog by @kodek16
- algorithm gitbook by @lzl124631x
- USACO Guide
- Maximum subarray problem (Kadane's algorithm). LeetCode 53
- Sliding Window Technique
- Префиксные суммы. XOR. Задачи на запросы
- Полное бинарное дерево. Куча. Очередь с приоритетом
- Hamming weight. LeetCode 191
- Custom impl of
__builtin_popcount - Hamming distance
- How to count leading zeros in integer (
__builtin_clzand pure impls)
- Четыре задачи на два указателя
- Алгоритм Кнута-Морриса-Пратта
- Динамическое программирование это просто
- Задача о рюкзаке. Динамическое программирование
- Прямая и обратная польская нотация
- Популярная в собеседованиях гугл задача. Разбор и решение (Guess the word 843 на LeetCode)
- Хитрая задача на Стек
- Поиск Знаменитости. Метод двух указателей
- Динамическое Программирование: Количество Уникальных Путей
- What is Bitmasking
- Bitwise Operations tutorial #1 | XOR, Shift, Subsets
- Плейлист АиСД year2020 s1
- Что такое sliding window: Solve subarray problems FASTER (using Sliding Windows)
- Что такое dynamic programming: Mastering Dynamic Programming - How to solve any interview problem (Part 1)
- Linked List Cycle - Floyd's Tortoise and Hare
- Найти позицию начала цикла (
len(head -> cycle_start) == len(equal_pointers -> cycle_start)) Floyd's Cycle Detection - How Dijkstra's Algorithm Works