Решаем задачки LeetCode на Java

Пробуем собрать, разобрать и решить по нескольку задач в каждом направлении
Задачи распределены по категориям по особенностям самих задач, их решений и других факторов.

Многие задачи могут находится одновременно в разных категориях. Если вы склонируете проект себе на компьютер, то вы сможете искать или наоборот проставлять метки к задачам например: #Easy, #Medium, #Array, #String и другие.

Ко многим задачам добавлены комментарии и пояснения для лучшего понимания. Также для многих задач приводятся альтернативные решения. Подходит как учебное пособие для начинающих.
Как учить алгоритмы - практическими повторениями. Выбираете тему, переписывайте 10-20 задач из неё, пока в общих чертах не поймете как это решается, потом пытаетесь воссоздать решения самостоятельно, пока не перестанете подглядывать решение)).

Технический стек: Для работы используется Windows 11, 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 Sum14. Longest Common Prefix66. Plus One88. Merge Sorted Array169. Majority Element217. Contains Duplicate219. Contains Duplicate II252. Meeting Rooms268. Missing Number349. Intersection Of Two Arrays350. Intersection Of Two Arrays II414. Third Maximum Number455. Assign Cookies463. Island Perimeter506. Relative Ranks561. Array Partition I594. Longest Harmonious Subsequence628. Maximum Product Of Three Numbers645. Set Mismatch860. Lemonade Change2089. Find Target Indices After Sorting Array2900. Longest Unequal Adjacent Groups Subsequence I

Breadth-First Search (#BFS)
Breadth First Search (BFS) — это алгоритм обхода или поиска в графе или дереве в ширину, который изучает все узлы на одном уровне перед переходом к следующему уровню. Проще говоря, он сначала посещает всех соседей начальной точки, потом их соседей и так далее, двигаясь "по ширине". Это, например, помогает найти кратчайший путь в невзвешенных графах.
Примечания.
Невзвешенный граф — это граф, в котором ребрам не присвоены какие-либо числовые значения (веса). То есть все ребра считаются равнозначными, без указания стоимости, длины или другого параметра. В таком графе при поиске пути или обходе обычно учитывается только количество ребер, а не их "вес". Например, если ребро соединяет две вершины, то переход по нему считается одинаково "дорогим" для всех ребер. Level Easy (#Easy)
100. Same Tree101. Symmetric Tree104. Maximum Depth Of Binary Tree112. Path Sum226. Invert Binary Tree404. Sum Of Left Leaves

Binary Search (#BinarySearch)
Здесь помещаем задачи с бинарным поиском. Binary Search (бинарный поиск) — это алгоритм поиска элемента в отсортированном массиве, который делит область поиска пополам на каждом шаге.
Level Easy (#Easy)
35. Search Insert Position69. Sqrtx108. Convert Sorted Array To Binary Search Tree222. Count Complete Tree Nodes278. First Bad Version367. Valid Perfect Square374. Guess Number Higher Or Lower441. Arranging Coins704. Binary Search744. Find Smallest Letter Greater Than Target1337. The K Weakest Rows In A Matrix1351. Count Negative Numbers In A Sorted Matrix1385. Find The Distance Value Between Two Arrays1539. Kth Missing Positive Number1608. Special Array With X Elements Greater Than Or Equal X2089. Find Target Indices After Sorting Array2389. 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 Traversal100. Same Tree101. Symmetric Tree104. Maximum Depth Of Binary Tree108. Convert Sorted Array To Binary Search Tree110. Balanced Binary Tree112. Path Sum144. Binary Tree Preorder Traversal145. Binary Tree Postorder Traversal222. Count Complete Tree Nodes226. Invert Binary Tree404. Sum Of Left Leaves257. Binary Tree Paths

Bits (#Bits)
Операции с битами
Level Easy (#Easy)
67. Add Binary231. Power Of Two268. Missing Number338. Counting Bits342. Power Of Four389. Find The Difference405. 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 Traversal100. Same Tree101. Symmetric Tree104. Maximum Depth Of Binary Tree110. Balanced Binary Tree112. Path Sum144. Binary Tree Preorder Traversal145. Binary Tree Postorder Traversal222. Count Complete Tree Nodes226. Invert Binary Tree257. Binary Tree Paths404. Sum Of Left Leaves463. Island Perimeter

Dynamic Programming (#DP)
Динамическое программирование (DP) — это метод решения задач, которые можно разбить на похожие подзадачи. Идея в том, чтобы не считать одну и ту же подзадачу несколько раз, а сохранить её результат и использовать повторно.
Пример: вычисление чисел Фибоначчи. Вместо того, чтобы каждый раз вычислять число заново, мы запоминаем уже посчитанные значения и берём их из памяти.
В Java обычно делают так: создают массив или таблицу для хранения результатов подзадач, заполняют этот массив постепенно, начиная с самых простых случаев, используют сохранённые результаты для решения более сложных задач.
Level Easy (#Easy)
70. Climbing Stairs292. Nim Game746. Min Cost Climbing Stairs509. Fibonacci Number1137. N th Tribonacci Number

Greedy (#Greedy)
Задачи использующие "Жадный алгоритм"
Жадный алгоритм — это способ решения задач, где на каждом шаге выбирается самый выгодный или лучший вариант в данный момент, не задумываясь о будущем. Такой подход прост и часто эффективен, но не всегда гарантирует оптимальное решение. Пример: выбор монет для сдачи, когда берём сначала самые крупные монеты.
Level Easy (#Easy)
455. Assign Cookies561. Array Partition I605. Can Place Flowers680. Valid Palindrome II860. Lemonade Change942. DI String Match976. Largest Perimeter Triangle1005. Maximize Sum Of Array After K Negations1013. Partition Array Into Three Parts With Equal Sum1217. Minimum Cost To Move Chips To The Same Position2389. Longest Subsequence With Limited Sum

Hash Table (#HashMap)
В этом разделе находятся задачи, использующие для решения хеш таблицы, например HashMap, HashSet
Level Easy (#Easy)
1. Two Sum205. Isomorphic Strings290. Word Pattern349. Intersection Of Two Arrays350. Intersection Of Two Arrays II594. Longest Harmonious Subsequence888. Fair Candy Swap

Linked List (#LinkedList)
Задачи, связанные со связанными списками или использующие связанные списки в качестве решения
Примечания.
Можно сказать, что хорошее знание Linked List (связанных списков) полезно для изучения более сложной темы - разного рода деревьев.
Алгоритм "Черепахи и Зайца" - Floyd's Cycle-Finding Algorithm
Level Easy (#Easy)
141. Linked List Cycle160. Intersection Of Two Linked Lists226. Invert Binary Tree

Math (#Math)
Как правило это зачи с цифрами, числами, или использующие какие-то математические свойства и особенности
Примечения: Палиндром - это число (или строка), которое читается одинаково в обоих направлениях. Цифровой корень числа — это однозначное число, которое получается путём последовательного сложения всех цифр исходного числа, пока не останется одна цифра. Полный квадрат — это целое число, которое является квадратом другого целого числа. Треугольник существует если выполняется неравенство треугольника: сумма любых двух сторон должна быть больше третьей стороны.
Level Easy (#Easy)
9. Palindrome number69. Sqrtx118. Pascals Triangle119. Pascals Triangle II202. Happy Number263. Ugly Number258. Add Digits292. Nim Game326. Power Of Three342. Power Of Four367. Valid Perfect Square405. Convert A Number TO Hexadecimal441. Arranging Coins628. Maximum Product Of Three Numbers645. Set Mismatch942. DI String Match976. Largest Perimeter Triangle1217. Minimum Cost To Move Chips To The Same Position1025. Divisor game

Pointers (#Pointers) - указатели
Здесь показываем задачи, которые используют указатели для решения задач
Level Easy (#Easy)
26. Remove Duplicates From Sorted Array27. Remove Element125. Valid Palindrome141. Linked List Cycle392. Is Subsequence455. Assign Cookies680. Valid Palindrome II905. Sort Array By Parity942. DI String Match1346. Check If N And Its Double Exist1385. Find The Distance Value Between Two Arrays2389. Longest Subsequence With Limited Sum

Recursion (#Recursion)- рекурсия
Сюда помещаем примеры задач, которые могут использовать рекурсию в одном из решений
Level Easy (#Easy)
94. Binary Tree Inorder Traversal100. Same Tree101. Symmetric Tree104. Maximum Depth Of Binary Tree108. Convert Sorted Array To Binary Search Tree110. Balanced Binary Tree112. Path Sum144. Binary Tree Preorder Traversal145. Binary Tree Postorder Traversal171. Excel Sheet Column Number222. Count Complete Tree Nodes226. Invert Binary Tree404. Sum Of Left Leaves509. Fibonacci Number680. Valid Palindrome II704. Binary Search1137. N th Tribonacci Number

Sort (#Sort)
Задачи, использующие для решения сортировку
Level Easy (#Easy)
252. Meeting Rooms414. Third Maximum Number455. Assign Cookies506. Relative Ranks561. Array Partition I594. Longest Harmonious Subsequence628. Maximum Product Of Three Numbers905. Sort Array By Parity976. Largest Perimeter Triangle1005. Maximize Sum Of Array After K Negations1337. The K Weakest Rows In A Matrix1346. Check If N And Its Double Exist1351. Count Negative Numbers In A Sorted Matrix11385. Find The Distance Value Between Two Arrays1608. Special Array With X Elements Greater Than Or Equal X2089. Find Target Indices After Sorting Array2389. Longest Subsequence With Limited Sum

String (#String)
В этом разделе находятся некоторые задачи, использующие строки
Примечания: Подпоследовательность (subsequence) - это последовательность символов, которая появляется в том же порядке, но не обязательно подряд. Две строки считаются изоморфными, если символы первой строки могут быть заменены на символы второй строки с сохранением порядка.
Level Easy (#Easy)
13. Roman To Integer14. Longest Common Prefix20. Valid Parentheses28. Find The Index Of The First Occurrence In A String58. Length Of Last Word67. Add Binary125. Valid Palindrome168. Excel Sheet Column Title171. Excel Sheet Column Number205. Isomorphic Strings242. Valid Аnagram290. Word Pattern389. Find The Difference392. Is Subsequence680. Valid Palindrome II942. DI String Match1668. Maximum Repeating Substring2900. Longest Unequal Adjacent Groups Subsequence I

Tree (#Tree)
Здесь помещаем задачи, которые используют для решения различнные виды деревьев
Примечания.
Для многих решений, использующих деревья добавлен класс модель TreeNode. Он вспомогательный для решения, отправлять его на проверку не нужно, у LeetCode он уже есть. Отправляйте на проверку только класс Solution.
Что такое Backtracking. Backtracking (возврат/откат) - это техника в программировании, когда мы: Делаем шаг вперед (добавляем элемент), Пробуем все возможные варианты продолжения, Возвращаемся назад (убираем последний элемент) Пробуем другие варианты. Представьте, что вы идете по лабиринту: Идете по коридору (добавляете в путь) Если тупик - возвращаетесь назад (убираете из пути) Пробуете другой коридор
Level Easy (#Easy)
94. Binary Tree Inorder Traversal100. Same Tree101. Symmetric Tree104. Maximum Depth Of Binary Tree108. Convert Sorted Array To Binary Search Tree110. Balanced Binary Tree112. Path Sum144. Binary Tree Preorder Traversal145. Binary Tree Postorder Traversal222. Count Complete Tree Nodes226. Invert Binary Tree257. Binary Tree Paths404. Sum Of Left Leaves506. Relative Ranks