До первого алгособеса я прорешал не так много задач, его вытянул на своих силах и за счёт того что задачи были простые.
Ко второму алгособесу у меня было около 100 решённых задач, и это спасло мне жизнь. Если бы не вся эта практика, то не смог бы придумать и закодить решение к одной сложной задаче.
Вот что нового я узнал в процессе:
•
Fast & Slow pointers — для нахождения цикла в односвязном списке (
задача).
• Применение решения выше в задаче где нет ни слова об односвязных списках 🤯 (
задача). Оказывается односвязные списки могут применяться не только разработчиками стандартной библиотеки.
•
Алгоритм Манакера — для нахождения всех палиндромов в строке за O(n), похож на Z-функцию. Очень прикольно, мне понравилось. Я смог его сам реализовать просто по текстовому описанию за счёт того что уже знал как работает Z-функция.
•
Monotonic queue — позволяет находить ближайший элемент больше текущего за O(n). Прикольная структура данных.
•
Trie — как я раньше об этом не знал, это офигенная структура данных, и так просто кодится! Обожаю теперь.
•
Sliding window — с помощью этого паттерна можно решать многие задачи очень быстро. И это очень хитро, я раньше даже не подозревал что так вообще можно было.
•
Multiset — структура данных, имитирующая отсортированный массив, и позволяющая за O(log(N)) вставлять/удалять элемент и находить минимум/максимум.
Multimap примерно то же.
Ну а так же я очень сильно закрепил следующие темы:
• Динамическое программирование
• Map, Set, Priority Queue
• Backtracking
• Деревья
• Two pointers
• Prefix/suffix sum/min/max/etc
Хоть я раньше их и знал, но теперь мне кажется они прям идеально отточены.
В общем узнал очень очень много нового, несмотря на некоторый олимпиадный бэкграунд.
Раньше я относился к LeetCode как к сайту со слишком простыми задачами, а теперь после всего этого я изменил своё мнение. Теперь всем буду рекомендовать сначала набраться базы на LeetCode, а затем идти на CodeForces за более серьёзными задачами.
Ну и для подготовке к собесам LeetCode тоже отлично подходит.
