Skip to content

YarTsin/leetcode_java

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

33 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

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

Многие задачи могут находится одновременно в разных категориях.
Если вы склонируете проект себе на компьютер, то вы сможете искать или наоборот проставлять метки к задачам например: #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