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

Time: O(logn + k)
Space: O(1)

⚡️ Идея
▫для решения найдем левую границу результата, используя бинарный поиск с начальными указателями l = 0 и r = arr.length - k
▫выполняем бинарный поиск:
➖если arr[mid] ближе к X, чем arr[mid + k], значит arr[mid + k], а также каждый элемент справа от него не может быть в ответе, следовательно, перемещаем правый указатель
➖та же самая логика, но в обратном порядке — если arr[mid + k] ближе к X, перемещаем левый указатель.
▫в конце составляем список из элементов массива длиной k, начиная с индекса l

#solution658

🟡Medium
986. Interval List Intersections

📝 Вам даны два отсортированных списка интервалов, верните их пересечение.
Например, пересечение [1, 3] и [2, 4] равно [2, 3]

💡: используйте слияние интервалов

149/200
#leetcode986 | #medium

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

Time: O(n + m)
Space: O(n + m)

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

#solution986

🟡Medium
161. One Edit Distance

📝 Даны две строки s и t, вернуть true, если они находятся на расстоянии одного редактирования друг от друга.

Строка s находится на расстоянии одного редактирования от t, если можно:
➖Вставить ровно один символ в s, чтобы получить t
➖Удалить ровно один символ из s, чтобы получить t
➖Заменить ровно один символ s другим символом, чтобы получить t

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

150/200
#leetcode161 | #medium #premium

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

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

⚡️ Идея
▫реализуем функцию helper, которая принимает два указателя на строки и возвращает true, если все символы двух строк от этих указателей равны и строки пройдены полностью
▫проходим по двум строкам и, если текущие символы не равны, используем все возможные операции, вызывая функцию helper в 3-x вариантах:
1⃣ замена символа — передаем указатели (i + 1, i + 1)
2⃣ вставка — передаем указатели (i, i + 1)
3⃣ удаление — передаем указатели (i + 1, i)
▫если все символы равны, то helper ни разу не вызовется, тогда нужно проверить, что длины строк отличаются строго на 1

#solution161

🟢Easy
680. Valid Palindrome II

📝 Для данной строки s вернуть true, если она может быть палиндромом после удаления из нее не более одного символа

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

151/200
#leetcode680 | #easy

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

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

⚡️ Идея
▫реализуем функцию check, которая с помощью двух переданных указателей проходит строку с двух сторон и возвращает true, если от этих указателей строка палиндромная и при этом количество удалений символов не больше 1
▫проверяем всю строку на палиндромность, вызвав check с указателями (0, s.length() - 1) и count = 0, и при несовпадении символов рекурсивно вызываем функцию, используя два варианта удаления:
1⃣удаляем левый символ, check(l + 1, r, count + 1)
2⃣удаляем правый символ, check(l, r - 1, count + 1)

#solution680

🟡Medium
2743. Count Substrings Without Repeating Character

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

💡: используйте подход sliding window

152/200
#leetcode2743 | #medium #premium

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

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

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

#solution2743

🖼Иллюстрация подхода sliding window к задаче 2743

Пример:

s = "abab"

#figure #slidingwindow

🟡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