Здравствуйте, товарищи!
0. Friendly SWE Guide Manifesto
- У меня есть документ, в котором я собираю дельные советы начинающим программистам. Там про настройку рабочей среды и всего такого. Иногда добавляю туда что-то новенькое. Комментарии приветствуются.
1. Бинарный поиск
Описание задачи: Классический алгоритм поиска элемента в отсортированном массиве за логарифмическое время $O(\log n)$. Разбор фокусируется на правильной работе с границами интервала и избежании переполнения int.
- 📺 Видео-разбор: Теория и практика
- 📝 Задача на LeetCode: Binary Search
- 💡 Мое решение и заметки: Код и замечания
- 🏠 Домашнее задание: Реализовать поиск самого левого и самого правого вхождения элемента (см. заметки).
2. Быстрое возведение в степень
Описание задачи: Алгоритм вычисления $x^n$ за $O(\log n)$. Обсуждаем рекурсивный и итеративный подходы, а также обработку отрицательных степеней.
3. Задача о кузнечике
Описание задачи: Введение в динамическое программирование (одномерный случай). Решаем задачу о количестве способов добраться до ступеньки $n$, прыгая на 1 или 2 шага.
- 📺 Видео-разбор: Теория
- 📝 Задача на LeetCode: Climbing Stairs
- 💡 Мое решение и заметки: Формула и связь с Фибоначчи справа
4. Задача о водопаде (Trapping Rain Water)
Описание задачи: Задача на нахождение объема воды, который может удержаться между столбиками разной высоты. Разбираем эффективный подход с двумя указателями.
- 📺 Видео-разбор:
- 📝 Задача на LeetCode: Trapping Rain Water
- 💡 Мое решение и заметки: Код и замечания
5. Проверка IP-адреса
Описание задачи: Задача на аккуратную работу со строками и валидацию данных. Проверяем, является ли строка корректным IPv4-адресом.
- 📺 Видео-разбор: Разбор решения
- 📝 Задача на LeetCode: Validate IP Address
6. Связные списки (Linked List)
Общая теория: Видео по структурам данных
6.1. Проектирование списка
Описание: Реализация односвязного списка "с нуля". Учимся управлять указателями, добавлять и удалять элементы в разных частях списка.
- 📝 Задача на LeetCode: Design Linked List
- 💡 Мое решение и заметки: Имплементация
6.2. Переворот списка
Описание: Классическая задача на изменение направления связей в списке. Разбираем как итеративный, так и рекурсивный способы.
- 📺 Видео-разбор: Рекурсивный подход
- 📝 Задача на LeetCode: Reverse Linked List
- 💡 Мое решение и заметки: Код и замечания
6.3. Цикл в списке
Описание: Определение наличия цикла и нахождение точки входа в цикл.
-
Наличие цикла (Has Cycle?)
- 📺 Видео-разбор: Алгоритм Флойда
- 📝 Задача на LeetCode: Linked List Cycle
- 💡 Мое решение: Заметки
-
Точка входа в цикл (Cycle Start Point)
- 📝 Задача на LeetCode: Linked List Cycle II
- 💡 Мое решение: Заметки
6.4. Слияние списков
Описание: Объединение двух отсортированных связных списков в один новый отсортированный список.
- 📺 Видео-разбор: Кодинг онлайн
- 📝 Задача на LeetCode: Merge Two Sorted Lists
- 💡 Мое решение и заметки: Код и замечания
7. Массивы
Общая теория: Видео по работе с массивами
-
7.1. Пересечение массивов Описание: Нахождение общих элементов в двух массивах. Разбираем подходы с использованием Hash Map и сортировки.
- 📺 Видео-разбор: Логика решения
- 📝 Задача на LeetCode: Intersection of Two Arrays II
- 💡 Мое решение: Python код на GitHub
-
7.2. k-ая порядковая статистика Описание: Поиск k-го по величине элемента в неотсортированном массиве. Разбираем алгоритм Quick Select со средним временем $O(n)$.
- 📺 Видео-разбор: Quick Select и кучи
- 📝 Задача на LeetCode: Kth Largest Element
8. Перебор (Backtracking)
Описание задачи: Метод поиска решений путем полного перебора вариантов с отсечением неперспективных ветвей. Используется для задач типа "N королев", генерации перестановок или поиска путей в графе.
- 📺 Видео-разбор:
9. Бинарные деревья
Общая теория: Видео по деревьям
9.1. Проверка на BST (Binary Search Tree)
Описание: Проверка того, является ли дерево корректным деревом поиска (для каждого узла все левые потомки меньше, а правые — больше).
- 📺 Видео-разбор: Разбор и кодинг
- 📝 Задача на LeetCode: Validate BST
- 💡 Мое решение и заметки: Код (рекурсия)
9.2. Работа с BST
Описание: Базовые операции in дерево поиска.
-
Поиск значения в BST
- 📝 Задача на LeetCode: Search in BST
- 💡 Мое решение: Код и заметки
-
Минимальная разница между узлами
- 📝 Задача на LeetCode: Min Diff in BST
- 💡 Мое решение: Код и заметки
9.3. Наименьший общий предок (LCA)
Описание: Поиск самого "глубокого" узла в дереве, который является предком для двух данных узлов.
- 📺 Видео-разбор: LCA без предподсчета
- 📝 Задача на LeetCode: LCA of Binary Tree
- 🏠 Домашнее задание: LCA of Binary Search Tree
9.4. Десериализация дерева
Описание: Восстановление структуры бинарного дерева по результатам двух его обходов (например, Inorder и Postorder).
- 📺 Видео-разбор: Inorder + Postorder
- 📝 Задача на LeetCode: Construct Tree
- 💡 Мое решение: Код и заметки
10. Бор (Trie)
Описание: Реализация префиксного дерева — структуры данных для эффективного хранения и поиска строк. Незаменим в задачах автодополнения и проверки орфографии.
- 📺 Видео-разбор: Базовая теория
- 📝 Задача на LeetCode: Implement Trie
11. Графы
Описание: Основы теории графов: способы представления (матрица смежности, списки смежности) и базовые понятия.
- 📺 Видео-разбор:
12. Комбинаторика
Описание: Генерация перестановок. Изучаем алгоритм нахождения следующей в лексикографическом порядке перестановки.
- 📺 Видео-разбор: Next Permutation
- 📝 Задача на LeetCode: Next Permutation
13. Два указателя (Two Pointers)
Описание: Техника оптимизации перебора, использующая два индекса, движущихся навстречу друг другу или в одном направлении.
-
13.1. Minimum Window Substring Описание: Поиск кратчайшей подстроки, содержащей все символы заданного набора. Задача на технику "скользящего окна".
- 📺 Видео-разбор: Разбор с кодом
- 📝 Задача на LeetCode: Minimum Window Substring
-
13.2. Сумма двух элементов Описание: Нахождение в отсортированном массиве двух чисел, сумма которых равна заданному значению.
- 📺 Видео-разбор: Поиск в отсортированном массиве
- 💡 Мое решение: Код
14. Динамическое программирование (Advanced)
Описание: Метод решения сложных задач путем разбиения их на более простые подзадачи с сохранением промежуточных результатов.
-
14.1. Stock Price Описание: Нахождение максимальной прибыли от покупки и продажи акции.
- 📺 Видео-разбор: Best Time to Buy and Sell Stock
- 📝 Задача на LeetCode: Best Time to Buy and Sell Stock
-
14.2. Regular Expression Matching Описание: Реализация простейшего парсера регулярок с поддержкой
.и*.- 📺 Видео-разбор: Логика DP
- 📝 Задача на LeetCode: Regular Expression Matching
- 💡 Мое решение: Gist с кодом
-
14.3. Jump Game II Описание: Нахождение минимального количества прыжков для достижения конца массива. Разбираем через DP и оптимизацию с помощью Segment Tree.
- 📺 Видео-разбор:
- 📝 Задача на LeetCode: Jump Game II
- 💡 Мое решение: Gist с кодом
15. Разделяй и властвуй
Описание: Стратегия решения задачи путем её рекурсивного разбиения на две или более подзадачи того же типа. Разбираем на примере вычисления всех возможных результатов расстановки скобок в выражении.
- 📺 Видео-разбор: Different Ways to Add Parentheses
- 📝 Задача на LeetCode: Different Ways to Add Parentheses
16. Комплексные задачи (Бор + Перебор + ДП)
- Описание: Задача про расстановку пробелов в строке (Word Break II). Требует интеграции нескольких подходов для эффективного решения.
- 📺 Видео-разбор:
- 📝 Задача на LeetCode: Word Break II
- 💡 Мое решение: Gist с кодом
Продвинутые и интересные темы
Теория вероятностей
Описание: Разбор нестандартных задач, требующих применения основ теории вероятностей и математического ожидания в контексте программирования.