✅ Решение задачи 968

Time: O(n)
Space: O(n)

💡 Идея
🟦Естественно, размещение камер на всех узлах — это лишнее, поэтому мы стремимся размещать камеры стратегически, в идеале на родителях листовых узлов, а не на самих листьях

🟦Это приводит нас к подходу снизу вверх (постпорядковый DFS) с использованием системы состояний, чтобы определить, какое действие следует предпринять на каждом уровне

🟦Реализуем функцию dfs, которая возвращает:
➖-1 — если узлу нужна камера
➖ 0 — если узел охвачен камерой
➖ 1 — если у узла есть камера

🟦Обходим дерево, используя метод обратного поиска в глубину:
➖рекурсивно вычисляем статус левого и правого поддеревьев

➖если какому-либо ребенку нужна камера (-1) , помещаем камеру в текущий узел: увеличиваем счетчик и возвращаем 1

➖если у какого-либо дочернего узла есть камера (1) , текущий узел будет покрыт — возвращаем 0

➖если оба дочерних узла покрыты и не имеют камер, то этому узлу она нужна — возвращаем -1

🟦После выполнения обхода, если корню по-прежнему нужна камера, мы увеличиваем счетчик еще раз

👩‍💻 Java Algo | #solution968

🔴Hard
272. Closest Binary Search Tree Value II

Company: 📱📱📱

📝 Дано двоичное дерево поиска (BST), значение target и целое число k.

Верните k значений в BST, которые наиболее близки к target. Вы можете вернуть ответ в любом порядке

💡: используйте in-order обход, а затем примените идею из данной задачи

#leetcode272 | #hard #binarytree

✅ Решение задачи 272

Time: O(n)
Space: O(n)

💡 Идея
🟦Решение сводится к знакомому алгоритму на нахождение k ближайших элементов с применением бинарного поиска, если собрать отсортированный список из узлов дерева

🟦Для этого необходимо пройти бинарное дерево поиска in-order:
➖рекурсивно проходим до самого левого элемента (наименьшего), затем, поднимаясь вверх по стеку рекурсии, добавляем значение узла в список и переходим к правому поддереву, продолжая обход

🟦В результате получаем отсортированный список, к которому применяем бинарный поиск для нахождения левой границы ответа:
➖если элемент mid ближе к target, чем mid + k, значит элемент mid + k, а также каждый элемент справа от него не может быть в ответе, поэтому, перемещаем правую границу

➖та же самая логика, но в обратном порядке — если элемент mid + k ближе к target, перемещаем левую границу

🟦В конце возвращаем k элементов из списка, используя найденную границу: subList(left, left + k)

👩‍💻 Java Algo | #solution272

🔴Hard
297. Serialize and Deserialize Binary Tree

Company: 🚔📱📱

📝Разработайте алгоритм сериализации и десериализации бинарного дерева. Никаких ограничений на реализацию нет.

Вам просто нужно убедиться, что бинарное дерево может быть сериализовано в строку, а эта строка может быть десериализована в исходную структуру дерева.

Для решения реализуйте класс Codec:

public class Codec {

    public String serialize(TreeNode root) {}

    public TreeNode deserialize(String data) {}
}

💡: сериализуйте дерево, используя dfs и разделяя значения запятыми, а при десериализации рекурсивно восстанавливайте левое и правое поддеревья

#leetcode297 | #hard #binarytree

✅ Решение задачи 297

Time: O(n)
Space: O(n)

💡 Идея
1⃣Сериализация
🟦Используем прямой обход дерева — сначала обрабатываем текущий узел, затем левое поддерево, затем правое:
➖если узел существует — записываем его значение
➖если узел отсутствует (равен null) — записываем специальное обозначение "N"
➖в результате все значения объединяются в одну строку, разделённую запятыми

🟦Таким образом, структура дерева сохраняется, потому что на каждом месте в строке либо значение, либо "N", строго в порядке обхода

2⃣Десериализация
🟦Рабиваем строку на части по запятым — получается список значений. Этот список превращаем в очередь, чтобы обрабатывать элементы по порядку

🟦Дальше используем рекурсивную функцию dfs:
➖берём первый элемент из очереди
➖если это "N" — значит узел отсутствует, возвращаем null
➖если это число — создаём узел с этим значением
➖затем вызываем эту же функцию для левого поддерева, затем для правого

🟦В итоге все узлы дерева рекурсивно восстанавливаются, и структура получается точно такой же, как была до сериализации

👩‍💻 Java Algo | #solution297

🔴Hard
1373. Maximum Sum BST in Binary Tree

Company: 📱📱🚖

📝Дано двоичное дерево, верните максимально возможную сумму всех узлов любого поддерева, которое является двоичным деревом поиска (BST)

💡: используйте обход dfs, возвращая структуру данных {sum, maxLeft, minRight}

#leetcode1373 | #hard #binarytree

✅ Решение задачи 1373

Time: O(n)
Space: O(n)

💡 Идея
🟦Первым делом для каждого узла мы пытаемся понять – может ли он являться корнем бинарного дерева поиска (BST), то есть проверяем:
➖текущий узел больше всех узлов левого поддерева и меньше всех узлов правого поддерева

🟦Для обхода дерева используем функцию dfs, которая возвращает заготовленную структуру данных TreeData, хранящую сумму, максимальный и минимальный элементы поддерева для проверки узла на BST:

➖рекурсивно проходим до самого левого элемента, затем, поднимаясь вверх по стеку рекурсии переходим к правому поддереву, продолжая обход

➖на каждом шаге обхода делаем основную проверку на валидность BST:
▫если проверка прошла — считаем текущую сумму, используя данные левого и правого поддеревьев, и возвращаем новую TreeData для следующего шага рекурсии

▫иначе — для оптимизации алгоритма возвращаем null, поэтому в основном условии сначала проверяем, что левое и правое поддеревья не null, то есть являются BST, а затем уже проверяем текущий узел

➖для базового случая node == null, возвращаем такую TreeData, которая гарантированно сделает родителя null-узла корнем BST-поддерева, так как листья подходят под определение бинарного дерева поиска

👩‍💻 Java Algo | #solution1373

➡️ Стартуем тему PriorityQueue (Heap)

▫Представь, что у тебя есть список задач на день с указанием приоритета: сходить в магазин (3), написать письмо (2), ответить на сообщение в чате (4), решить задачу на LeetCode (1), посмотреть фильм (5)

▫Ты ведь не будешь делать эти дела по порядку, как они записаны. Ты выберешь самое срочное и начнёшь с него, потом возьмёшь следующее по срочности — и так далее

▫Вот это и есть PriorityQueue — такая "умная" очередь дел:
➖ты можешь добавлять новые задачи с приоритетами
➖она сама внутри отслеживает, что сейчас самое важное
➖и когда ты готов делать следующее дело, она говорит: "Вот, это самое срочное!"

▫В Java по умолчанию PriorityQueue работает как минимальная очередь (min-heap) — то есть первым выходит элемент с наименьшим значением. Для Integer это значит: 1 выйдет раньше, чем 3 или 5

PriorityQueue<Integer> pq = new PriorityQueue<>();

▫Если нужен свой порядок приоритета, можно использовать лямбда-выражение. Например, чтобы первым шел наибольший элемент (max-heap):

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

🟦Структура и Time Complexity

▫PriorityQueue в Java использует бинарную кучу — это особая структура, похожая на дерево, но хранящаяся в массиве:

Представь, что элементы выстраиваются в виде пирамидки:
➖cамый приоритетный элемент — всегда на вершине

➖каждый родитель меньше (или больше — в зависимости от очереди) своих "детей"

➖при добавлении элемент "всплывает наверх", сравнивается с родителями и меняется местами, если меньше

➖при удалении — последний элемент ставится наверх, а затем "просеивается вниз", пока не восстановится порядок

▫Отсюда получаем временную сложность:

➖добавление элемента (add, offer) — O(log n)

➖извлечение элемента с наивысшим приоритетом (poll) — O(log n)

➖просмотр элемента с наивысшим приоритетом (peek) — O(1)

#priorityqueue

🟢Easy
1046. Last Stone Weight

Company: 🏢📱🚔

📝Вам дан массив целых чисел stones, где stones[i] — вес камня.

На каждом ходу мы выбираем два самых тяжелых камня (x и y, x <= y) и разбиваем их друг о друга:

➖если x == y, то оба камня разрушены
➖если x != y, то камень веса x разрушается, а камень веса y имеет новый вес y - x
➖в конце игры остается максимум один камень

Верните вес последнего оставшегося камня. Если камней не осталось, верните 0

💡: настройте приоритет очереди и смоделируйте процесс игры

#leetcode1046 | #easy #priorityqueue

✅ Решение задачи 1046

Time: O(n log(n))
Space: O(n)

💡 Идея
🟦В начале создадим приоритетную очередь pq, но в Java PriorityQueue — это min-heap, что не подходит по задаче, поэтому с помощью компаратора ((a, b) -> b - a) превращаем ее в max-heap, чтобы всегда быстро получать самый тяжелый камень

🟦Добавляем все камни в pq, а затем начинаем цикл моделирования игры, пока в очереди больше одного элемента:

➖последовательно достаем из очереди два самых тяжелых камня: y и x
➖если камни разной массы, добавляем разницу обратно

🟦В конце возвращаем вес камня, если остался один или 0, если все камни разбиты

👩‍💻 Java Algo | #solution1046

🟢Easy
703. Kth Largest Element in a Stream

Company: 🏢📱📕

📝Реализуйте класс KthLargest, который поддерживает поток ввода чисел и непрерывно возвращает k-ый наибольший элемент после загрузки нового числа

💡: поддерживайте очередь размером k

#leetcode703 | #easy #priorityqueue

✅ Решение задачи 703

Time: O(n log(k))
Space: O(k)

💡 Идея
🟦Для решения используем минимальную кучу, то есть PriorityQueue, в которой хранятся только k самых больших чисел. Самое маленькое из них — это как раз k-й по величине элемент

🟦При добавлении нового числа используем метод add:
➖если в куче меньше k элементов — число просто добавляется

➖если уже есть k элементов, то новое число сравнивается с наименьшим в куче:
▫если оно больше, то старое удаляется и добавляется новое, иначе шаг просто пропускается
▫так мы всегда поддерживаем только k самых больших чисел из всех, которые встречались

🟦В результате, верхушка кучи всегда содержит k-й по величине элемент, что позволяет эффективно работать даже с большим потоком данных, так как операция добавления занимает O(log k) и не требуется хранить все числа — только k нужных

👩‍💻 Java Algo | #solution703

🟢Easy
3318. Find X-Sum of All K-Long Subarrays I

Company: 🔍

📝Дан целочисленный массив nums и два целых числа k и x. Верните массив answer длины n - k + 1, где answer[i] — X-сумма подмассива nums[i..i + k - 1].

X-сумма вычисляется следующим образом:
➖посчитайте частоту всех элементов в подмассиве
➖вычислите сумму только x самых частых элементов. Если два элемента имеют одинаковую частоту, элемент с большим значением считается более частым

При этом, если подмассив содержит менее x различных элементов, его X-сумма равна сумме подмассива

💡: настройте компаратор очереди на сравнение частот элементов из HashMap

#leetcode3318 | #easy #priorityqueue

✅ Решение задачи 3318

Time: O((n - k) * klogk)
Space: O(n)

💡 Идея
🟦Проходим по массиву окном длины k и для каждого определяем частоты всех чисел с помощью HashMap

🟦Далее нужно найти x самых частых элементов, для этого используем PriorityQueue с настроенным компаратором на сравнение частот из HashMap, учитывая, что при одинаковых – приоритет отдается большему значению

🟦Добавив в очередь все уникальные значения, извлекаем из нее x самых частых и суммируем в результат для текущего окна произведение каждого числа на его частоту

🟦В итоге формируется массив, содержащий такие суммы для всех возможных окон длины k в исходном массиве

👩‍💻 Java Algo | #solution3318

🟡Medium
253. Meeting Rooms II

Company: 📱📱🏢

📝Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимально необходимое количество переговорных комнат

💡: отсортируйте встречи по времени начала и используйте очередь, чтобы отслеживать, когда освобождаются комнаты

#leetcode253 | #medium #priorityqueue

✅ Решение задачи 253

Time: O(n log(n))
Space: O(n)

💡 Идея
🟦Сначала отсортируем все интервалы встреч по времени начала, что позволит в правильном порядке отслеживать, какие комнаты освобождаются, а какие ещё заняты

🟦Далее для текущей встречи стоит необходимость выбора комнаты, поэтому полезно знать самое раннее завершение какой-либо встречи, для чего используем PriorityQueue, в которую последовательно добавляем времена окончания всех встреч

🟦Если текущая встреча начинается после завершения самой ранней встречи (pq.peek()), значит, комната освобождается, и можно снова её использовать, а время окончания этой встречи из очереди удалить

🟦В результате размер очереди указывает на максимальное количество одновременно активных встреч, что и есть минимально необходимое число переговорных комнат

👩‍💻 Java Algo | #solution253

🟡Medium
2182. Construct String With Repeat Limit

Company: 🔍 📱

📝Вам дана строка s и целое число repeatLimit.

Постройте новую строку, используя символы из s так, чтобы ни одна буква не встречалась подряд более repeatLimit раз, при этом необязательно использовать все символы.

Верните лексикографически наибольшую возможную строку

💡: используйте очередь для составления букв по убыванию, и при достижении лимита вставьте новый символ

#leetcode2182 | #medium #priorityqueue

✅ Решение задачи 2182

Time: O(n log(k))
Space: O(k)

💡 Идея
🟦Сначала посчитаем частоту каждого символа с помощью HashMap и поместим все уникальные в PriorityQueue, которая упорядочена по убыванию для построения строки в лексикографически наибольшем порядке

🟦Затем запускаем процесс формирования строки:
➖извлекаем из очереди наибольший доступный символ и добавляем его к результату не более repeatLimit раз

➖если частота этого символа больше, чем repeatLimit, то извлекаем из очереди следующий по убыванию символ и добавляем его один раз в результат

➖если оба символа ещё встречаются — возвращаем их обратно в очередь

🟦В итоге, если нет больше символа для чередования, а текущий превышает лимит повторений, построение строки завершается, и мы получаем лексикографически максимальный результат с учетом ограничения

👩‍💻 Java Algo | #solution2182

🟡Medium
1642. Furthest Building You Can Reach

Company: 📱📱🏢

📝Дан массив heights — высоты зданий и числа bricks и ladders — количество кирпичей и лестниц.

Вы начинаете с 0-го здания и движетесь вправо:

▫если следующее здание не выше текущего — просто спрыгиваете
▫если выше — используйте кирпичи на разницу высот или лестницу, которая покрывает любую высоту

Верните индекс самого дальнего здания, до которого можно добраться при оптимальном использовании ресурсов

💡: жадно используйте лестницы для всех подъемов, а когда они закончатся — замените наименьший кирпичами

#leetcode1642 | #medium #priorityqueue

✅ Решение задачи 1642

Time: O(n log(k))
Space: O(k)

💡 Идея
🟦Проходим по массиву и на каждом шаге:
➖оцениваем разницу в высоте между следующим зданием и текущим — climb

➖если climb > 0, значит нужно каким-то образом преодолеть подъём, для чего всегда используем лестницы и добавляем текущий подъем в PriorityQueue

➖но, если размер очереди стал больше ladders, значит лестницы закончились, и пора использовать кирпичи вместо самого маленького подъема, который мы достаем из очереди

➖если после этого кирпичей стало меньше 0, значит все ресурсы закончились и можно возвращать текущий индекс

🟦В результате получаем оптимальное использование ресурсов, жадно используя лестницы для самых больших подъемов, а кирпичи — для меньших

👩‍💻 Java Algo | #solution1642

🟡Medium
1353. Maximum Number of Events That Can Be Attended

Company: 💰🚖🏢

📝Дан массив events, где events[i] = [startDayi, endDayi] — мероприятие, которое начинается в день startDayi и заканчивается в endDayi.

Вы можете посетить мероприятие i в любой день d, который входит в интервал его проведения.

Верните максимальное количество мероприятий, которые вы можете посетить, при условии, что в один день можно посетить только одно мероприятие

💡: отсортируйте события по дню начала и используйте очередь, чтобы всегда выбирать событие с ближайшим днём окончания

#leetcode1353 | #medium #priorityqueue