🟡Medium
735. Asteroid Collision

📝 Дан массив целых чисел, представляющий движение астероидов в ряд.

Для каждого астероида его абсолютное значение является размером, а знак его направлением (+ вправо, - влево).

Если два астероида встретятся, меньший из них взорвется, если они одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Верните состояние астероидов после всех столкновений

💡: используйте стек

153/200
#leetcode735 | #medium

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

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

⚡️ Идея
▫важно понять, что астероиды столкнуться только если первый летит вправо, а второй влево, то есть предположение, что столкновение происходит, только лишь когда знаки у астероидов разные — неверно
▫ используем стек, в который добавляем элементы следующим образом:
▫ если астероид больше 0 (летит вправо), добавляем его в стек
▫ иначе рассматриваем случай столкновения:
➖пока стек не пуст и верхний астероид меньше текущего, удаляем его
➖далее проверяем — если стек пуст или верхний элемент меньше 0, значит можно добавить в стек текущий астероид
➖также обрабатываем случай равенства астероидов и удаляем верхний астероид, если он положительный и равен текущему по размеру
▫в конце из стека составляем массив для ответа

#solution735

🟡Medium
652. Find Duplicate Subtrees

📝Для заданного двоичного дерева вернуть все корни дублирующихся поддеревьев.

Два дерева являются дубликатами, если они имеют одинаковую структуру с одинаковыми значениями узлов

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

154/200
#leetcode652 | #medium

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

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

⚡️ Идея
▫реализуем функцию helper, которая рекурсивно обходит дерево и собирает корни дублирующихся поддеревьев:
➖обходим правое и левое поддеревья и получаем их идентификаторы
➖далее составляем строковый ключ поддерева, который вычисляется как leftId + "," + node.val + "," + rightId и по нему кладем в HashMap идентификатор (id), если такой ключ отсутствует. Для идентификатора используем размер map + 1
➖затем по id увеличиваем значение в HashMap подсчетов поддеревьев и если оно равно 2, значит мы нашли дубликат и можно добавить его в результат
➖в конце функции возвращаем идентификатор для рекурсивных вызовов

#solution652

🟡Medium
253. Meeting Rooms II

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

💡: используйте PriorityQueue для хранения времени окончания встреч

155/200
#leetcode253 | #medium #premium

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

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

⚡️ Идея
▫инициализируем PriorityQueue (minHeap) для хранения времени окончания встреч
▫отсортируем интервалы по времени начала, а затем пройдем по ним:
➖проверяем, свободна ли какая-либо комната, сравнивая текущее начало с верхним элементом очереди, поскольку это будет комната, которая освободится раньше всех
➖если текущая встреча начинается позже, значит мы можем занять освободившуюся комнату и удалить ее из очереди
➖далее добавляем текущее окончание встречи в очередь
▫в результате ответом будет являться размер очереди

#solution253

🟢Easy
3105. Longest Strictly Increasing or Strictly Decreasing Subarray

📝 Вам дан массив целых чисел. Верните длину самого длинного подмассива, который либо строго увеличивается, либо строго уменьшается

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

156/200
#leetcode3105 | #easy

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

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

⚡️ Идея
▫инициализируем две переменные increase и decrease, которые помогут подсчитать различные варианты последовательностей
▫далее проходим по массиву и обрабатываем 3 возможных случая:
1⃣текущий элемент больше предыдущего — увеличиваем переменную increase, а decrease приравниваем к 1, так как убывание закончилось на этом элементе, если оно было
2⃣текущий элемент меньше предыдущего — по той же логике увеличиваем decrease, а increase приравниваем к 1
3⃣элементы равны — приравниваем обе переменные к единице, так как по условию необходима строгая последовательность
▫после каждой проверки сравниваем текущий результат с максимальным из increase и decrease

#solution3105

🟡Medium
63. Unique Paths II

📝Вам дана сетка m x n. В левом верхнем углу находится робот, который может двигаться только вправо или вниз.

Препятствие и свободная клетка в сетке обозначены, как 1 и 0 соответственно.

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

💡: используйте динамическое программирование

157/200
#leetcode63 | #medium

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

Time: O(nm)
Space: O(nm)

⚡️ Идея
▫инициализируем матрицу dp размерностью на 1 больше исходной сетки, чтобы не обрабатывать выходы за пределы
▫заполняем dp:
➖в первую ячейку кладем 1, если в исходной сетке там нет препятствия
➖далее заполняем оставшиеся ячейки, суммируя количество путей из верхней и левой, при этом пропуская ячейки, где находятся препятствия, оставляя в них значение 0
▫В результате в dp[n][m] получаем ответ

📎Код с решением по памяти за O(1) в комментариях

#solution63

🟡Medium
274. H-Index

📝Дан массив целых чисел citations, где citations[i] — количество цитирований, полученных исследователем для i-ой статьи. Необходимо вернуть индекс Хирша исследователя.

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

💡: используйте подсчет количества цитирований для решения за O(n)

158/200
#leetcode274 | #medium

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

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

⚡️ Идея
▫инициализируем переменную max, как максимальный возможный h-индекс, который равен длине заданного массива
▫для подсчета количества цитирований используем массив count размером max + 1
▫далее проходимся по заданному массиву и увеличиваем в count количество статей с текущим значением цитирования. При этом если значение больше max, кладем его по индексу max, так как h-индекс не может быть больше длины заданного массива
▫затем проходим по массиву count, начиная с max, и суммируем текущее количество цитирований: если оно стало больше или равно текущему индексу, значит возвращаем данный индекс в качестве ответа

#solution274

🟡Medium
328. Odd Even Linked List

📝 Дан связный список, сгруппируйте все узлы с нечетными индексами, а затем узлы с четными индексами и верните переупорядоченный список.

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

Необходимо решить задачу за O(1) по памяти и O(n) по времени

💡: одновременно передвигайте два указателя — на четную и нечетную группы

159/200
#leetcode328 | #medium

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

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

⚡️ Идея
▫сохраним указатель на начало четной группы и проинициализируем указатели для прохода по списку на 1-ый и 2-ой узел
▫проходимся по списку, пока четный указатель и его следующий узел не null:
➖для обоих указателей меняем ссылку на следующий узел — ссылкой через один и передвигаем их на новую позицию
▫в конце для нечетного указателя следующим узлом делаем сохраненный указатель на начало четной группы и возвращаем начало нового списка

#solution328

🟡Medium
221. Maximal Square

📝Дана матрица, заполненная символами '0' и '1', найти наибольший квадрат, содержащий только '1', и вернуть его площадь

💡: используйте динамическое программирование

160/200
#leetcode221 | #medium

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

Time: O(nm)
Space: O(1)

⚡️ Идея
▫проходим по исходной матрице, используя динамическое программирование прямо в ней
▫если это первая строка или первый столбец, максимальный размер квадрата будет не больше 1
▫иначе, если текущий элемент равен 1:
➖считаем максимальную сторону квадрата, как минимум из диагонального, левого и верхнего элементов плюс 1
➖сохраняем полученную сторону в текущую ячейку и проверяем ее на максимальный результат
▫в конце возводим в квадрат полученную максимальную сторону, так как необходимо вернуть площадь

#solution221

🟢Easy
605. Can Place Flowers

📝 Дан целочисленный массив, содержащий 0 и 1, где 0 означает пустое место, 1 — посаженный цветок, а также целое число n.
Вернуть true, если можно посадить n цветов так, чтобы никакие два не находились рядом

💡: проверяйте места с двух сторон и учтите краевые случаи

161/200
#leetcode605 | #easy

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

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

⚡️ Идея
▫проходим данный массив и используем две переменные для проверки свободных мест слева и справа:
➖emptyL — true, если текущий элемент нулевой или значение слева равно 0
➖emptyR — true, если текущий индекс последний или значение справа равно 0
▫если обе переменные true и текущий элемент равен 0, значит здесь можно посадить цветок:
➖текущий элемент делаем 1 и уменьшаем переменную n
▫в конце возвращаем true, если n <= 0

#solution605

🟡Medium
1657. Determine if Two Strings Are Close

📝Даны две строки, вернуть true, если они близкие.

Две строки считаются близкими, если одну из другой можно получить с помощью следующих операций:
➖поменять местами любые два символа
➖поменять местами все вхождения двух символов. Например, все 'a' превращаются в 'b', а все 'b' превращаются в 'a':

"aacabb" —> "bbcbaa"

Можно использовать операции над любой строкой столько раз, сколько необходимо

💡: используйте массив частот символов для двух строк

162/200
#leetcode1657 | #medium

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

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

⚡️ Идея
▫формируем массив частот символов длиной 26 для двух строк и заполняем его
▫далее проходим по двум массивам и проверяем — существует ли текущий символ в обоих строках, если нет — возвращаем false
▫так как мы можем использовать операции любое количество раз, необходимо только проверить, что
частоты символов в двух строках совпадают, поэтому возвращаем true, если массивы идентичны после сортировки
▫сортировка выполняется за 26(log26), что сводится к O(1), поэтому общая сложность алгоритма O(n)

#solution1657

🟡Medium
962. Maximum Width Ramp

📝Дан целочисленный массив, вернуть максимальную ширину рампы.

Рампа в целочисленном массиве nums — это пара (i, j), для которой i < j и nums[i] <= nums[j]. Ширина такой рампы равна j - i

💡: используйте монотонный стек

163/200
#leetcode962 | #medium