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

Time: O(3^n*4^m)
Space: O(3^n*4^m)

📝 Идея
▫️Сопоставление цифр и букв храним в HashMap
▫️Используя подход backtrack, перебираем каждый символ текущего набора и добавляем новый из следующего
▫️Когда длина текущей комбинации равна длине строки цифр, добавляем ее в результат

#solution17

🟡 Medium
131. Palindrome Partitioning

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

Подсказка: реализуйте подход backtrack c проверкой на палиндромную строку

58/200
#medium
#leetcode131

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

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

📝 Идея
▫️Используем подход backtrack, рекурсивно перебирая возможные разбиения строки, при этом делая проверку на палиндромность подстроки функцией isPalindrom
▫️Если index равен длине строки, значит все подстроки прошли проверку на палиндромность и можно добавлять в ответ полученное разбиение

#solution131

🟢 Easy
70. Climbing Stairs

📃 Вы поднимаетесь по лестнице на вершину n.
Каждый раз вы можете подняться либо на 1, либо на 2 ступеньки. Сколькими различными способами вы можете подняться на вершину?

Подсказка: с каких ступенек вы можете подняться на n-ую?

59/200
#easy
#leetcode70

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

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

📝 Идея
▫️Используем подход "динамическое программирование", то есть когда задача раскладывается на более простую
▫️На i-ую ступеньку можно прийти только двумя способами: с предыдущей и с (i-2)-ой
▫️Соответственно, количество способов подняться на i-ую ступеньку будет равняться сумме способов с i-1 и i-2

#solution70

🟡 Medium
198. House Robber

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

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

60/200
#medium
#leetcode198

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

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

📝 Идея
▫️Начиная со 2-го элемента смотрим какую максимальную сумму можно получить, проверяя стоит ли грабить этот дом или пойти дальше
▫️Для этого берем максимум из полученной суммы в предыдущей ячейке и суммы, которую можно получить складывая текущую ячейку и ячейку n-2
▫️В итоге, пройдя весь цикл, в последней ячейке будет ответ на задачу

#solution198

🟡 Medium
215. Kth Largest Element in an Array

📃 Дан массив целых чисел и целое число k, вернуть наибольший k-ый элемент массива.
Необходимо решить задачу без использования сортировки.

Подсказка: используйте PriorityQueue

61/200
#medium
#leetcode215

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

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

📝 Идея
▫️Для решения используем ProrityQueue, данная структура данных добавляет элементы за log(n), при этом позволяя за O(1) найти минимум
▫️Поскольку задача найти максимальное значение, сохраняем все элементы со знаком минус
▫️Далее удаляем элементы, пока k > 1, чтобы в результате сверху остался k-ый максимальный элемент

#solution215

🟢 Easy
746. Min Cost Climbing Stairs

📃 Вам дан целочисленный массив cost, где cost[i] — стоимость шага на лестнице. После оплаты стоимости вы можете подняться на 1 или 2 ступеньки.
Вы можете начать движение либо с 0, либо с 1 элемента.
Верните минимальную стоимость, чтобы достичь верхнего этажа.

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

62/200
#easy
#leetcode746

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

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

📝 Идея
▫️Для каждого элемента ищем минимальный способ сюда попасть, выбирая минимум из стоимости элементов i-1 и i-2
▫️Пройдя весь цикл, выбираем минимум из последних двух элементов, так как достичь верхнего этажа можно сделав 1 или 2 шага

#solution746

🟡 Medium
213. House Robber II

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

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

63/200
#medium
#leetcode213

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

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

📝 Идея
▫️Поскольку первый и последний дом являются соседними, просто выберем максимум из двух возможных вариантов:
1. Используем первый дом, но не используем последний
2. Используем последний дом, но не используем первый
▫️Данное решение реализует такой же алгоритм, что и здесь, только с использованием двух переменных:
- в rob1 сохраняется nums[i-2]
- в rob2 nums[i - 1]

#solution213

🟡 Medium
5. Longest Palindromic Substring

📃 Дана строка, вернуть самую длинную палиндромную подстроку

Подсказка: рассматривайте каждый символ как центр палиндромной подстроки

64/200
#medium
#leetcode5

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

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

📝 Идея
▫️Рассматриваем каждый символ, как возможный центр палиндромной строки и запускаем проверку для двух случаев:
- палиндромная подстрока имеет нечетную длину
- палиндромная подстрока имеет четную длину
▫️В результат сохраняем подстроку с максимальной длиной

#solution5

🟡 Medium
200. Number of Islands

📃 Для заданной двумерной двоичной сетки grid, представляющей карту, где '1' - суша, '0' - вода, вернуть количество островов.
Остров окружен водой и образован путем соединения соседних земель по горизонтали или вертикали.

Подсказка: каждый найденный остров помечайте '0'

65/200
#medium
#leetcode200

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

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

📝 Идея
▫️Для каждого начала острова (то есть '1'), запускаем функцию, которая полностью покрывает данный остров водой (то есть '0'), используя рекурсивный обход во все стороны
▫️Таким образом, увеличивать количество островов мы всегда будем только встречая начало острова, так как нигде больше не будет единиц

#solution200

🟡 Medium
322. Coin Change

📃 Вам дан целочисленный массив, представляющий монеты разного номинала (бесконечное количество каждого вида), и целое число amount, представляющее общую сумму денег.

Верните наименьшее количество монет, которое вам нужно, чтобы составить эту сумму. Если эта сумма денег не может быть составлена, верните -1.

Подсказка: составьте массив, в котором будете хранить минимальное количество монет от 1 до amount

66/200
#medium
#leetcode322

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

Time: O(mn)
Space: O(m)

📝 Идея
▫️Инициализируем массив dp, в котором будем хранить минимальное количество монет для каждого значения от 1 до amount
▫️Далее заполняем этот массив, для каждого значения выбирая минимально возможное количество монет из тех значений dp[i], которые мы уже получили
▫️В результате dp[amount] будет хранить минимальное количество монет необходимое для данного количества

#solution322

🟡 Medium
695. Max Area of Island

📃 Дана двоичная матрица, где остров — это группа 1, соединенных в 4-х направлениях (по горизонтали или вертикали). Площадь острова — это количество ячеек со значением 1.

Верните максимальную площадь острова.

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

67/200
#medium
#leetcode695

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

Time: O(mn)
Space: O(m)

📝 Идея
▫️Так же как здесь, для каждого начала острова (то есть 1), запускаем функцию, которая полностью покрывает данный остров водой (то есть 0), чтобы позже "натыкаться" только на начало нового острова
▫️На каждом шаге рекурсии добавляем единицу, в результате получая площадь острова

#solution695