Задачи распределены по особенностям самих задач и их решений.
Многие задачи могут находится одновременно в разных категориях.
Если вы склонируете проект себе на компьютер, то вы сможете искать
или наоборот проставлять метки к задачам например:
#Easy, #Medium, #Array, #String и другие.
Ко многим задачам добавлены комментарии и пояснения для лучшего понимания.
Также для многих задач приводятся альтернативные решения.
Подходит как учебное пособие для начинающих.
Как учить алгоритмы - практическими повторениями. Выбираете тему,
переписывайте 10-20 задач из неё, пока в общих чертах не поймете
как это решается, потом пытаетесь воссоздать решения самостоятельно,
пока не перестанете подглядывать решение)).
Для работы используется Java 8
Желаю вам удачно пройти алгоритмическую секцию!
Жми ★ если понравилось.
Моя статистика: https://leetcode.com/u/YarTsin/
Решено более 200 задач
Array (#Array)
В этом разделе показываем часть задач, использующих массивы
Примечания.
мажоритарный элемент - элемент, который встречается более n/2 раз.
Harmonious Subsequence - Определим гармоничную подпоследовательность
как подпоследовательность массива, в которой разница между
максимальным и минимальным элементами равна ровно 1, например 3,2,2,2,3.
Подпоследовательность (subsequence) - это последовательность, которая может быть
получена из другой последовательности удалением некоторых элементов
без изменения порядка оставшихся элементов
Level Easy (#Easy)
1. Two Sum
14. Longest Common Prefix
66. Plus One
88. Merge Sorted Array
169. Majority Element
217. Contains Duplicate
219. Contains Duplicate II
252. Meeting Rooms
268. Missing Number
349. Intersection Of Two Arrays
350. Intersection Of Two Arrays II
414. Third Maximum Number
455. Assign Cookies
463. Island Perimeter
506. Relative Ranks
561. Array Partition I
594. Longest Harmonious Subsequence
628. Maximum Product Of Three Numbers
645. Set Mismatch
860. Lemonade Change
2089. Find Target Indices After Sorting Array
2900. Longest Unequal Adjacent Groups Subsequence I
Breadth-First Search (#BFS)
Breadth First Search (BFS) — это алгоритм обхода или поиска в графе
или дереве в ширину, который изучает все узлы на одном уровне перед
переходом к следующему уровню. Проще говоря, он сначала посещает
всех соседей начальной точки, потом их соседей и так далее,
двигаясь "по ширине". Это, например, помогает найти кратчайший путь
в невзвешенных графах.
Примечания.
Невзвешенный граф — это граф, в котором ребрам
не присвоены какие-либо числовые значения (веса). То есть все ребра
считаются равнозначными, без указания стоимости, длины или другого
параметра. В таком графе при поиске пути или обходе обычно учитывается
только количество ребер, а не их "вес". Например, если ребро соединяет
две вершины, то переход по нему считается одинаково "дорогим" для всех ребер.
Level Easy (#Easy)
100. Same Tree
101. Symmetric Tree
104. Maximum Depth Of Binary Tree
112. Path Sum
226. Invert Binary Tree
404. Sum Of Left Leaves
Binary Search (#BinarySearch)
Здесь помещаем задачи с бинарным поиском. Binary Search (бинарный поиск)
— это алгоритм поиска элемента в отсортированном массиве, который делит область
поиска пополам на каждом шаге.
Level Easy (#Easy)
35. Search Insert Position
69. Sqrtx
108. Convert Sorted Array To Binary Search Tree
222. Count Complete Tree Nodes
278. First Bad Version
367. Valid Perfect Square
374. Guess Number Higher Or Lower
441. Arranging Coins
704. Binary Search
744. Find Smallest Letter Greater Than Target
1337. The K Weakest Rows In A Matrix
1351. Count Negative Numbers In A Sorted Matrix
1385. Find The Distance Value Between Two Arrays
1539. Kth Missing Positive Number
1608. Special Array With X Elements Greater Than Or Equal X
2089. Find Target Indices After Sorting Array
2389. Longest Subsequence With Limited Sum
Binary Search Tree (#BST)
BST (Binary Search Tree) — это структура данных в виде бинарного дерева с упорядочиванием,
где для каждого узла значения в левом поддереве меньше значения узла,
а в правом поддереве — больше.
Level Easy (#Easy)
108. Convert Sorted Array To Binary Search Tree
Binary Tree (#BinaryTree)
Бинарное дерево — это иерархическая структура данных, в которой каждый
узел (элемент) имеет не более двух потомков (детей).
Информация по бинарным деревьям
(эта информация поможет разобраться в типах задач по бинарным деревьям)Этих потомков принято называть левым и правым ребенком. Ключевые компоненты:
~ Корень (Root): Самый верхний узел дерева, от которого всё начинается. У корня нет родительского узла.
~ Узел (Node): Элемент дерева, который хранит какие-то данные (например, число) и ссылки (указатели) на своих левого и правого потомков.
~ Лист (Leaf): Узел, у которого нет потомков (оба ребенка равны null).
Бинарные деревья — идеальный полигон для отработки понимания рекурсии и алгоритмов поиска в глубину (DFS) и поиска в ширину (BFS), которые являются краеугольным камнем многих сложных задач.
Основные типы бинарных деревьев:
~ полное бинарное дерево: Все уровни дерева, кроме, возможно, последнего, полностью заполнены, а узлы последнего уровня смещены влево.
~ сбалансированное бинарное дерево: Глубина левого и правого поддеревьев каждого узла отличается не более чем на единицу. Это важно для эффективности операций. Пример — AVL-дерево.
~ идеальное бинарное дерево: Все внутренние узлы имеют двух детей, а все листья находятся на одном уровне.
~ Бинарное дерево поиска (BST) — очень важный вид деревьев.
Свойства: Для любого узла X: Все значения в левом поддереве X меньше значения самого X. Все значения в правом поддереве X больше значения самого X. Это свойство позволяет очень эффективно (за время O(log n)) искать, добавлять и удалять элементы. Множество задач построено вокруг BST.
Базовые операции и обходы (Traversal)
Умение обходить дерево — ключ к решению >90% задач. Есть два основных подхода.
Поиск в ширину (BFS - Breadth-First Search) - обход дерева уровень за уровнем. Реализуется с помощью очереди.
Частный случай: Level Order Traversal — классическая задача (например, LeetCode 102).
Поиск в глубину (DFS - Depth-First Search) - обход, при котором вы идете вглубь до самого конца, прежде чем вернуться.
Имеет три основных вида, которые отличаются порядком обработки узла:
~ Inorder (Лево -> Корень -> Право): Для BST обход дает отсортированную
последовательность. Классическая задача: LeetCode 94.
~ Preorder (Корень -> Лево -> Право): Полезно для копирования структуры дерева.
Классическая задача: LeetCode 144.
~ Postorder (Лево -> Право -> Корень): Полезно для удаления дерева, так как
вы сначала работаете с детьми. Классическая задача: LeetCode 145.
Morris Traversal (#MorrisTraversal) - это алгоритм обхода бинарного дерева, который позволяет
обойти дерево in-order, pre-order или post-order без использования
стека или рекурсии, с постоянной (O(1)) дополнительной памятью.
Level Easy (#Easy)
94. Binary Tree Inorder Traversal
100. Same Tree
101. Symmetric Tree
104. Maximum Depth Of Binary Tree
108. Convert Sorted Array To Binary Search Tree
110. Balanced Binary Tree
112. Path Sum
144. Binary Tree Preorder Traversal
145. Binary Tree Postorder Traversal
222. Count Complete Tree Nodes
226. Invert Binary Tree
404. Sum Of Left Leaves
257. Binary Tree Paths
Bits (#Bits)
Операции с битами
Level Easy (#Easy)
67. Add Binary
231. Power Of Two
268. Missing Number
338. Counting Bits
342. Power Of Four
389. Find The Difference
405. Convert A Number TO Hexadecimal
Clever Algorithms - это интересно
Информация о Clever Algorithms
Clever Algorithms - это алгоритмы, которые используют нетривиальные, innovative или особенно elegant подходы для решения задач, часто достигая лучшей производительности или используя меньше ресурсов, чем очевидные решения.Характеристики Clever Algorithms
~ Неочевидность - решение не сразу приходит в голову.
Пример: Morris Traversal - идея использовать временные связи вместо стека.
~ Эффективность - часто имеют лучшую временную или пространственную сложность.
Пример: Быстрая сортировка (QuickSort) vs Пузырьковая сортировка.
~ Минимальное использование ресурсов. Используют меньше памяти или вычислений.
Пример: Алгоритм Флойда для нахождения цикла в связном списке с O(1) памятью.
Примеры Clever Algorithms
Morris Traversal, Boyer-Moore Majority Vote Algorithm, Floyd's Cycle Detection (Черепаха и заяц), Kadane's Algorithm.
Depth-First Search (#DFS)
Раздел посвящён задачам, которые можно решать с помощью алгоритма поиска в глубину.
DFS (поиск в глубину) — это один из базовых алгоритмов обхода или поиска в графах
и деревьях. Идея заключается в том, что мы начинаем с корня (или с какой-то начальной вершины)
и исследуем как можно глубже каждую ветвь перед тем, как перейти к следующей.
Примечания:
Граф — это множество вершин (узлов), связанных рёбрами (связями).
Рёбра могут быть направленными или ненаправленными, граф может содержать циклы.
Дерево — это частный случай графа: связный ацикличный граф, где между любой парой
вершин существует ровно один путь. Дерево обычно имеет один корень.
Максимальная глубина бинарного дерева - это количество узлов вдоль самого
длинного пути от корневого узла до самого дальнего листового узла.
Level Easy (#Easy)
94. Binary Tree Inorder Traversal
100. Same Tree
101. Symmetric Tree
104. Maximum Depth Of Binary Tree
110. Balanced Binary Tree
112. Path Sum
144. Binary Tree Preorder Traversal
145. Binary Tree Postorder Traversal
222. Count Complete Tree Nodes
226. Invert Binary Tree
257. Binary Tree Paths
404. Sum Of Left Leaves
463. Island Perimeter
Dynamic Programming (#DP)
Динамическое программирование (DP) — это метод решения задач,
которые можно разбить на похожие подзадачи. Идея в том,
чтобы не считать одну и ту же подзадачу несколько раз,
а сохранить её результат и использовать повторно.
Пример: вычисление чисел Фибоначчи. Вместо того, чтобы каждый
раз вычислять число заново, мы запоминаем уже посчитанные значения
и берём их из памяти.
В Java обычно делают так: создают массив или таблицу для хранения результатов подзадач,
заполняют этот массив постепенно, начиная с самых простых случаев,
используют сохранённые результаты для решения более сложных задач.
Level Easy (#Easy)
70. Climbing Stairs
292. Nim Game
746. Min Cost Climbing Stairs
509. Fibonacci Number
1137. N th Tribonacci Number
Greedy (#Greedy)
Задачи использующие "Жадный алгоритм"
Жадный алгоритм — это способ решения задач, где на каждом шаге выбирается
самый выгодный или лучший вариант в данный момент, не задумываясь о будущем.
Такой подход прост и часто эффективен, но не всегда гарантирует
оптимальное решение. Пример: выбор монет для сдачи, когда берём
сначала самые крупные монеты.
Level Easy (#Easy)
455. Assign Cookies
561. Array Partition I
605. Can Place Flowers
680. Valid Palindrome II
860. Lemonade Change
942. DI String Match
976. Largest Perimeter Triangle
1005. Maximize Sum Of Array After K Negations
1013. Partition Array Into Three Parts With Equal Sum
1217. Minimum Cost To Move Chips To The Same Position
2389. Longest Subsequence With Limited Sum
Hash Table (#HashMap)
В этом разделе находятся задачи, использующие для решения хеш таблицы,
например HashMap, HashSet
Level Easy (#Easy)
1. Two Sum
205. Isomorphic Strings
290. Word Pattern
349. Intersection Of Two Arrays
350. Intersection Of Two Arrays II
594. Longest Harmonious Subsequence
888. Fair Candy Swap
Linked List (#LinkedList)
Задачи, связанные со связанными списками или использующие связанные списки
в качестве решения
Примечания.
Можно сказать, что хорошее знание Linked List (связанных списков)
полезно для изучения более сложной темы - разного рода деревьев.
Алгоритм "Черепахи и Зайца" - Floyd's Cycle-Finding Algorithm
Level Easy (#Easy)
141. Linked List Cycle
160. Intersection Of Two Linked Lists
226. Invert Binary Tree
Math (#Math)
Как правило это зачи с цифрами, числами, или использующие какие-то
математические свойства и особенности
Примечения: Палиндром - это число (или строка), которое читается одинаково
в обоих направлениях.
Цифровой корень числа — это однозначное число, которое получается путём
последовательного сложения всех цифр исходного числа, пока не останется одна цифра.
Полный квадрат — это целое число, которое является квадратом
другого целого числа. Треугольник существует если выполняется неравенство треугольника:
сумма любых двух сторон должна быть больше третьей стороны.
Level Easy (#Easy)
9. Palindrome number
69. Sqrtx
118. Pascals Triangle
119. Pascals Triangle II
202. Happy Number
263. Ugly Number
258. Add Digits
292. Nim Game
326. Power Of Three
342. Power Of Four
367. Valid Perfect Square
405. Convert A Number TO Hexadecimal
441. Arranging Coins
628. Maximum Product Of Three Numbers
645. Set Mismatch
942. DI String Match
976. Largest Perimeter Triangle
1217. Minimum Cost To Move Chips To The Same Position
1025. Divisor game
Pointers (#Pointers) - указатели
Здесь показываем задачи, которые используют указатели для решения задач
Level Easy (#Easy)
26. Remove Duplicates From Sorted Array
27. Remove Element
125. Valid Palindrome
141. Linked List Cycle
392. Is Subsequence
455. Assign Cookies
680. Valid Palindrome II
905. Sort Array By Parity
942. DI String Match
1346. Check If N And Its Double Exist
1385. Find The Distance Value Between Two Arrays
2389. Longest Subsequence With Limited Sum
Recursion (#Recursion)- рекурсия
Сюда помещаем примеры задач, которые могут использовать рекурсию в одном из решений
Level Easy (#Easy)
94. Binary Tree Inorder Traversal
100. Same Tree
101. Symmetric Tree
104. Maximum Depth Of Binary Tree
108. Convert Sorted Array To Binary Search Tree
110. Balanced Binary Tree
112. Path Sum
144. Binary Tree Preorder Traversal
145. Binary Tree Postorder Traversal
171. Excel Sheet Column Number
222. Count Complete Tree Nodes
226. Invert Binary Tree
404. Sum Of Left Leaves
509. Fibonacci Number
680. Valid Palindrome II
704. Binary Search
1137. N th Tribonacci Number
Sort (#Sort)
Задачи, использующие для решения сортировку
Level Easy (#Easy)
252. Meeting Rooms
414. Third Maximum Number
455. Assign Cookies
506. Relative Ranks
561. Array Partition I
594. Longest Harmonious Subsequence
628. Maximum Product Of Three Numbers
905. Sort Array By Parity
976. Largest Perimeter Triangle
1005. Maximize Sum Of Array After K Negations
1337. The K Weakest Rows In A Matrix
1346. Check If N And Its Double Exist
1351. Count Negative Numbers In A Sorted Matrix1
1385. Find The Distance Value Between Two Arrays
1608. Special Array With X Elements Greater Than Or Equal X
2089. Find Target Indices After Sorting Array
2389. Longest Subsequence With Limited Sum
String (#String)
В этом разделе находятся некоторые задачи, использующие строки
Примечания: Подпоследовательность (subsequence) - это последовательность символов,
которая появляется в том же порядке, но не обязательно подряд.
Две строки считаются изоморфными, если символы первой строки
могут быть заменены на символы второй строки с сохранением порядка.
Level Easy (#Easy)
13. Roman To Integer
14. Longest Common Prefix
20. Valid Parentheses
28. Find The Index Of The First Occurrence In A String
58. Length Of Last Word
67. Add Binary
125. Valid Palindrome
168. Excel Sheet Column Title
171. Excel Sheet Column Number
205. Isomorphic Strings
242. Valid Аnagram
290. Word Pattern
389. Find The Difference
392. Is Subsequence
680. Valid Palindrome II
942. DI String Match
1668. Maximum Repeating Substring
2900. Longest Unequal Adjacent Groups Subsequence I
Tree (#Tree)
Здесь помещаем задачи, которые используют для решения различнные виды деревьев
Примечания.
Для многих решений, использующих деревья добавлен класс модель TreeNode.
Он вспомогательный для решения, отправлять его на проверку не нужно,
у LeetCode он уже есть. Отправляйте на проверку только класс Solution.
Что такое Backtracking. Backtracking (возврат/откат) - это техника
в программировании, когда мы: Делаем шаг вперед (добавляем элемент),
Пробуем все возможные варианты продолжения, Возвращаемся назад (убираем последний элемент)
Пробуем другие варианты. Представьте, что вы идете по лабиринту: Идете по коридору
(добавляете в путь) Если тупик - возвращаетесь назад (убираете из пути) Пробуете другой коридор
Level Easy (#Easy)
94. Binary Tree Inorder Traversal
100. Same Tree
101. Symmetric Tree
104. Maximum Depth Of Binary Tree
108. Convert Sorted Array To Binary Search Tree
110. Balanced Binary Tree
112. Path Sum
144. Binary Tree Preorder Traversal
145. Binary Tree Postorder Traversal
222. Count Complete Tree Nodes
226. Invert Binary Tree
257. Binary Tree Paths
404. Sum Of Left Leaves
506. Relative Ranks