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

🟡 Medium
973. K Closest Points to Origin

📃 Дан двумерный массив points, где points[i] представляет точку на плоскости XY и целое число, вернуть k ближайших точек к началу координат (в любом порядке).

Расстояние до начала координат: √(x² + y²)

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

68/200
#medium
#leetcode973

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

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

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

#solution973

🟡 Medium
152. Maximum Product Subarray

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

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

69/200
#medium
#leetcode152

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

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

📝 Идея
▫️В массиве могут быть отрицательные элементы и их может быть четное количество, что даст положительный результат, поэтому храним две переменные: c максимальным текущим произведением и минимальным
▫️Если встретился отрицательный элемент, меняем минимум и максимум местами, чтобы получить максимально возможное текущее произведение

#solution152

🟡 Medium
139. Word Break

📃 Дана строка s и словарь строк wordDict, вернуть значение true, если s можно разбить в последовательность из одного или нескольких слов словаря, разделенных пробелами.

Одно и то же слово в словаре может использоваться в разбиении несколько раз.

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

70/200
#medium
#leetcode139

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

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

📝 Идея
▫️Инициализируем массив dp, в котором будем хранить true для каждой позиции в строке s, если начиная с этой позиции можно разбить оставшуюся подстроку на слова из wordDict
▫️Идем с конца массива и для каждой позиции перебираем все слова из wordDict, проверяя, что подстрока с позиции i начинается с этого слова
▫️Если условие выполнилось — копируем в dp[i] выражение из dp[i + w.length()], так как нужно понимать, что данное слово также позволит разбить оставшийся отрезок на слова
▫️Если dp[i] = true — останавливаем текущий цикл, так как мы нашли возможность разбиения
▫️В результате в dp[0] хранится результат, так как мы последовательно с конца строки искали все возможные разбиения

#solution139

🟡 Medium
91. Decode Ways

📃 Дана строка, содержащая только цифры, вернуть количество способов ее декодирования . Если вся строка не может быть декодирована каким-либо допустимым способом, верните 0.

Кодировка следующая:

"1" -> 'A'
"2" -> 'B'
...
"26" -> 'Z'

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

71/200
#medium
#leetcode91

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

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

📝 Идея
▫️Инициализируем массив dp, в котором будем хранить количество возможных вариантов декодирования для текущей позиции строки
▫️Заполняем dp[0] = dp[1], так для 1 и 0 символов есть только один способ декодирования
▫️Начиная со 2-го символа, суммируем варианты, проверяя условия:
- предыдущий символ не равен 0
- символ (i-2) равен 1 или символ (i-2) равен 2, тогда предыдущий символ должен быть строго меньше 7, так как кодировка до 26
▫️В результате в последней ячейке массива будет лежать сумма всех возможных вариантов декодирования

#solution91

🟡 Medium
416. Partition Equal Subset Sum

📃 Дан массив целых чисел, вернуть true, если можно разбить массив на два подмножества так, чтобы сумма элементов в обоих подмножествах была равна.

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

72/200
#medium
#leetcode416

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

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

📝 Идея
▫️Инициализируем массив dp, в котором будем хранить true для суммы n, если ее можно составить из элементов массива
▫️Используя каждый элемент nums, заполняем массив dp, при этом начинаем идти с конца, так как элементы nums можно использовать для суммы только 1 раз

#solution416