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

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

💡 Идея
🟪Используем подход с использованием скользящего окна, для этого:
▫Проходим по массиву и считаем текущую сумму
▫Если она превысила или равна target — сравниваем размер окна с текущим минимальным результатом
▫Затем передвигаем левый указатель вперед, пока сумма не станет меньше target, вычитая элементы находящиеся под ним
🟪В результате получаем минимальную длину подмассива с суммой большей или равной target

#solution209

🟡 Medium
394. Decode String

📰 Дана закодированная строка, вернуть ее декодированную.

Правило кодирования: k[string], где string внутри квадратных скобок повторяется ровно k раз, где k — гарантированно положительное целое число. Входная строка всегда соответствует данному формату.

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

141/200
#medium
#leetcode394

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

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

💡 Идея
🟦Проходя по заданной строке, есть 4 варианта обработки символа:
1⃣Цифра — запоминаем ее в переменной n, при этом учитываем вариант, что число k может иметь больше одного знака (n = n * 10 + (c - '0'))
2⃣Буква — добавляем символ в текущую строку
3⃣'[' — кладем в стек текущую строку из символов и число n, а затем обнуляем данные переменные, для того, чтобы учесть варианты вложенностей
4⃣']' — запоминаем текущую строку в переменной temp и из стеков достаем значение числа повторений и сохраненную строку, присваивая её текущей строке, а затем добавляем к ней temp n раз
🟦В результате получаем полностью декодированную строку с учетом всех вложенностей

#solution394

🟡 Medium
38. Count and Say

📰 Дано положительное целое число n, вернуть последовательность «подсчитай и скажи».
Последовательность «подсчитай и скажи» представляет собой последовательность цифр, определяемую рекурсивной формулой:
▫countAndSay(1) — "1"
▫countAndSay(n) — представляет собой кодирование RLE серий countAndSay(n - 1).
RLE — это метод сжатия строк, который работает путем замены последовательных одинаковых символов на конкатенацию символа и числа, обозначающего количество символов.

Например, чтобы сжать строку "3322251", мы заменяем "33"на "23", "222"на "32", "5"на "15" и "1"на "11". Таким образом, сжатая строка становится "23321511"

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

142/200
#medium
#leetcode38

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

Time: O(2^n)
Space: O(n)

💡 Идея
🟪Рекурсивно доходим до базового случая, получая строку s = "1"
🟪Затем преобразуем каждый вариант строки из стека рекурсии, проходя по ней следующим образом:
▫увеличиваем счетчик символов
▫если символ последний в строке или он не равен следующему — добавляем счетчик и данный символ в текущее преобразование строки
🟪Таким образом, с помощью рекурсии мы каждый раз получаем текущий вариант кодирования строки от 1 до n, пока не получим итоговый ответ

#solution38

🟡Medium
713. Subarray Product Less Than K

📝 Дан массив целых чисел и целое число k, вернуть количество подмассивов, где произведение всех элементов строго меньше k

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

143/200
#leetcode713 | #medium

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

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

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

#solution713

🟡Medium
583. Delete Operation for Two Strings

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

💡: найдите длину самой длинной общей подпоследовательности

144/200
#leetcode583 | #medium

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

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

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

#solution583

🟡 Medium
279. Perfect Squares

📝Дано целое число n, вернуть наименьшее количество полных квадратов чисел, сумма которых равна n

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

145/200
#leetcode279 | #medium

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

Time: O(√nn)
Space: O(n)

⚡️ Идея
▫используем динамическое программирование, перебирая все числа от 1 до n и последовательно вычисляя dp[i]:
➖изначально для каждого i присваиваем значение n, как максимально возможный случай
➖далее вложенным циклом перебираем все квадраты j от 1 до i и для каждого выбираем минимальное значение между текущим dp[i] и dp[i - j²] + 1
▫в результате в dp[n] получаем ответ

#solution279

🔴Hard
32. Longest Valid Parentheses

📝 Для данной строки, содержащей только символы '(' и ')', вернуть длину самой длинной допустимой подстроки

💡: используйте стек с индексами открывающих скобок

146/200
#leetcode32 | #hard

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

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

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

#solution32

🟡Medium
356. Line Reflection

📝Дано n точек на двумерной плоскости, верните true, если существует такая прямая, параллельная оси Y, которая симметрично отражает данные точки

💡: найдите наименьшее и наибольшее значение x из всех точек, а затем используйте прямую minX + maxX для проверки отражения всех точек

147/200
#leetcode356 | #medium #premium

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

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

⚡️ Идея
▫первым проходом по точкам ищем минимальное и максимальное значения координаты x, а также складываем все точки в Set для дальнейшей проверки за O(1)
▫так как для прямой s = (minX + maxX) / 2, любая точка будет отражаться в координату (2*s - x, y), то для проверки будем сразу использовать прямую line = minX + maxX
▫вторым проходом смотрим, содержатся ли в Set все точки (line - x, y), если нет — сразу возвращаем false

#solution356

🟡Medium
658. Find K Closest Elements

📝 Дан отсортированный массив целых чисел и два целых числа K и X, верните K ближайших чисел к X в массиве. Результат также должен быть отсортирован.

Целое число a ближе к x, чем b, если:

|a - x| < |b - x|, или
|a - x| == |b - x|и a < b

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

148/200
#leetcode658 | #medium

✅ Решение задачи 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