Задача: 93. Restore IP Addresses
Сложность: medium
Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия:
- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"
Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как:
- "AAJF" с группировкой (1 1 10 6)
- "KJF" с группировкой (11 10 6)
Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06". Для данной строки s, содержащей только цифры, верните количество способов декодирования. Тестовые случаи сформированы таким образом, что ответ укладывается в 32-битное целое число.
Пример:
👨💻 Алгоритм:
1️⃣Входим в рекурсию с данной строкой, начиная с индекса 0.
2️⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов.
3️⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия:
- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"
Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как:
- "AAJF" с группировкой (1 1 10 6)
- "KJF" с группировкой (11 10 6)
Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06". Для данной строки s, содержащей только цифры, верните количество способов декодирования. Тестовые случаи сформированы таким образом, что ответ укладывается в 32-битное целое число.
Пример:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
👨💻 Алгоритм:
1️⃣Входим в рекурсию с данной строкой, начиная с индекса 0.
2️⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов.
3️⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.
😎 Решение:
class Solution(object):
def valid(self, s, start, length):
return length == 1 or (
s[start] != "0"
and (length < 3 or s[start : start + length] <= "255")
)
def helper(self, s, startIndex, dots, ans):
remainingLength = len(s) - startIndex
remainingNumberOfIntegers = 4 - len(dots)
if (
remainingLength > remainingNumberOfIntegers * 3
or remainingLength < remainingNumberOfIntegers
):
return
if len(dots) == 3:
if self.valid(s, startIndex, remainingLength):
temp = ""
last = 0
for dot in dots:
temp += s[last : last + dot] + "."
last += dot
temp += s[startIndex:]
ans.append(temp)
return
for curPos in range(1, min(4, remainingLength + 1)):
dots.append(curPos)
if self.valid(s, startIndex, curPos):
self.helper(s, startIndex + curPos, dots, ans)
dots.pop()
def restoreIpAddresses(self, s):
answer = []
self.helper(s, 0, [], answer)
return answer
Ставь 👍 и забирай 📚 Базу знаний
🔥1
Задача: 846. Hand of Straights
Сложность: medium
У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт.
Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае.
Пример:
👨💻 Алгоритм:
1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false.
2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand.
3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп:
Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount.
Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false.
Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт.
Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае.
Пример:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]
👨💻 Алгоритм:
1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false.
2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand.
3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп:
Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount.
Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false.
Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount.
😎 Решение:
from collections import Counter
class Solution:
def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
if len(hand) % groupSize != 0:
return False
cardCount = Counter(hand)
for card in sorted(hand):
if cardCount[card] == 0:
continue
for nextCard in range(card, card + groupSize):
if cardCount[nextCard] == 0:
return False
cardCount[nextCard] -= 1
return True
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1166. Design File System
Сложность: medium
Вам нужно разработать файловую систему, которая позволяет создавать новые пути и связывать их с различными значениями.
Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы.
Реализуйте класс FileSystem:
-
-
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте словарь или HashMap под названием paths, который будет использовать ключ в виде пути, переданного в нашу функцию create, и значение, переданное этой функции.
2⃣Для функции create выполняем три шага. Сначала выполняем базовую проверку валидности пути. Проверяем, является ли путь пустым, "/" или если путь уже существует в нашем словаре. Если любое из этих условий выполнено, просто возвращаем false. Затем получаем родительский путь предоставленного пути и проверяем его наличие в словаре. Если родительский путь не существует, возвращаем false, иначе продолжаем.
3⃣Наконец, вставляем предоставленный путь и значение в словарь и возвращаем true. Для функции get просто возвращаем значение по умолчанию -1, если путь не существует в словаре. В противном случае возвращаем фактическое значение.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам нужно разработать файловую систему, которая позволяет создавать новые пути и связывать их с различными значениями.
Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы.
Реализуйте класс FileSystem:
-
bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует.-
int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует.Пример:
Input:
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output:
[null,true,1]
Explanation:
FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1
👨💻 Алгоритм:
1⃣Инициализируйте словарь или HashMap под названием paths, который будет использовать ключ в виде пути, переданного в нашу функцию create, и значение, переданное этой функции.
2⃣Для функции create выполняем три шага. Сначала выполняем базовую проверку валидности пути. Проверяем, является ли путь пустым, "/" или если путь уже существует в нашем словаре. Если любое из этих условий выполнено, просто возвращаем false. Затем получаем родительский путь предоставленного пути и проверяем его наличие в словаре. Если родительский путь не существует, возвращаем false, иначе продолжаем.
3⃣Наконец, вставляем предоставленный путь и значение в словарь и возвращаем true. Для функции get просто возвращаем значение по умолчанию -1, если путь не существует в словаре. В противном случае возвращаем фактическое значение.
😎 Решение:
class FileSystem:
def __init__(self):
self.paths = {}
def createPath(self, path: str, value: int) -> bool:
if not path or (len(path) == 1 and path == "/") or path in self.paths:
return False
delim_index = path.rfind("/")
parent = path[:delim_index]
if len(parent) > 1 and parent not in self.paths:
return False
self.paths[path] = value
return True
def get(self, path: str) -> int:
return self.paths.get(path, -1)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 594. Longest Harmonious Subsequence
Сложность: easy
Мы определяем гармоничный массив как массив, в котором разница между его максимальным и минимальным значением составляет ровно 1.
Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.
Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов.
Пример:
👨💻 Алгоритм:
1⃣Пройдитесь по массиву, создавая словарь для подсчета частоты каждого элемента.
2⃣На каждой итерации проверьте, существуют ли в словаре элементы, отличающиеся на 1 от текущего, и обновите максимальную длину гармоничной подпоследовательности.
3⃣Верните максимальную длину гармоничной подпоследовательности.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Мы определяем гармоничный массив как массив, в котором разница между его максимальным и минимальным значением составляет ровно 1.
Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.
Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов.
Пример:
Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].
👨💻 Алгоритм:
1⃣Пройдитесь по массиву, создавая словарь для подсчета частоты каждого элемента.
2⃣На каждой итерации проверьте, существуют ли в словаре элементы, отличающиеся на 1 от текущего, и обновите максимальную длину гармоничной подпоследовательности.
3⃣Верните максимальную длину гармоничной подпоследовательности.
😎 Решение:
class Solution:
def findLHS(self, nums: List[int]) -> int:
count = {}
res = 0
for num in nums:
count[num] = count.get(num, 0) + 1
if num + 1 in count:
res = max(res, count[num] + count[num + 1])
if num - 1 in count:
res = max(res, count[num] + count[num - 1])
return res
Ставь 👍 и забирай 📚 Базу знаний
🔥1
Задача: 892. Surface Area of 3D Shapes
Сложность: easy
Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности.
Пример:
👨💻 Алгоритм:
1⃣Пройти по всей сетке и для каждой башни (ячейки) посчитать начальную площадь поверхности: добавить площадь верхней и нижней граней, а также четыре боковые грани.
2⃣Для каждой башни уменьшить площадь боковых граней, которые прилегают к соседним башням, с учетом высоты соседних башен.
3⃣Просуммировать все значения площадей для получения итоговой площади поверхности.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности.
Пример:
Input: grid = [[1,2],[3,4]]
Output: 34
👨💻 Алгоритм:
1⃣Пройти по всей сетке и для каждой башни (ячейки) посчитать начальную площадь поверхности: добавить площадь верхней и нижней граней, а также четыре боковые грани.
2⃣Для каждой башни уменьшить площадь боковых граней, которые прилегают к соседним башням, с учетом высоты соседних башен.
3⃣Просуммировать все значения площадей для получения итоговой площади поверхности.
😎 Решение:
def surfaceArea(grid):
n = len(grid)
area = 0
for i in range(n):
for j in range(n):
if grid[i][j] > 0:
area += (grid[i][j] * 4) + 2
if i > 0:
area -= min(grid[i][j], grid[i-1][j]) * 2
if j > 0:
area -= min(gri
Ставь 👍 и забирай 📚 Базу знаний
Задача: 215. Kth Largest Element in an Array
Сложность: medium
Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.
Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.
Пример:
👨💻 Алгоритм:
1️⃣ Отсортируйте массив в порядке убывания:
Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее.
2️⃣ Найдите k-й по величине элемент:
После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0).
3️⃣ Верните результат:
Возвратите найденное значение как результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.
Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.
Пример:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
👨💻 Алгоритм:
1️⃣ Отсортируйте массив в порядке убывания:
Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее.
2️⃣ Найдите k-й по величине элемент:
После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0).
3️⃣ Верните результат:
Возвратите найденное значение как результат.
😎 Решение:
class Solution:
def findKthLargest(self, nums, k):
nums.sort(reverse=True)
return nums[k - 1]
Ставь 👍 и забирай 📚 Базу знаний
Задача: 951. Flip Equivalent Binary Trees
Сложность: medium
Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.
Пример:
👨💻 Алгоритм:
1⃣Если оба дерева пусты, они эквивалентны, вернуть true. Если одно дерево пустое, а другое нет, они не эквивалентны, вернуть false.
2⃣Если значения корней деревьев не совпадают, вернуть false.
Проверить два условия:
Левое поддерево первого дерева эквивалентно левому поддереву второго дерева и правое поддерево первого дерева эквивалентно правому поддереву второго дерева.
Левое поддерево первого дерева эквивалентно правому поддереву второго дерева и правое поддерево первого дерева эквивалентно левому поддереву второго дерева.
3⃣Вернуть true, если выполняется хотя бы одно из этих условий.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.
Пример:
Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
👨💻 Алгоритм:
1⃣Если оба дерева пусты, они эквивалентны, вернуть true. Если одно дерево пустое, а другое нет, они не эквивалентны, вернуть false.
2⃣Если значения корней деревьев не совпадают, вернуть false.
Проверить два условия:
Левое поддерево первого дерева эквивалентно левому поддереву второго дерева и правое поддерево первого дерева эквивалентно правому поддереву второго дерева.
Левое поддерево первого дерева эквивалентно правому поддереву второго дерева и правое поддерево первого дерева эквивалентно левому поддереву второго дерева.
3⃣Вернуть true, если выполняется хотя бы одно из этих условий.
😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def flipEquiv(root1, root2):
if not root1 and not root2:
return True
if not root1 or not root2 or root1.val != root2.val:
return False
return (flipEquiv(root1.left, root2.left) and flipEquiv(root1.right, root2.right)) or \
(flipEquiv(root1.left, root2.right) and flipEquiv(root1.right, root2.left))
Ставь 👍 и забирай 📚 Базу знаний
Задача: 436. Find Right Interval
Сложность: medium
Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.
Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.
Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.
Пример:
👨💻 Алгоритм:
1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j.
2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже.
3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.
Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.
Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.
Пример:
Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.
👨💻 Алгоритм:
1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j.
2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже.
3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.
😎 Решение:
class Solution:
def findRightInterval(self, intervals):
endIntervals = intervals[:]
hash = {tuple(interval): i for i, interval in enumerate(intervals)}
intervals.sort(key=lambda x: x[0])
endIntervals.sort(key=lambda x: x[1])
j = 0
res = [-1] * len(intervals)
for i in range(len(endIntervals)):
while j < len(intervals) and intervals[j][0] < endIntervals[i][1]:
j += 1
res[hash[tuple(endIntervals[i])]] = -1 if j == len(intervals) else hash[tuple(intervals[j])]
return res
Ставь 👍 и забирай 📚 Базу знаний
Задача: 320. Generalized Abbreviation
Сложность: medium
Обобщенная аббревиатура слова может быть построена путем замены любых неперекрывающихся и несмежных подстрок на их соответствующие длины.
Например, "abcde" можно сократить следующим образом:
"a3e" ("bcd" заменено на "3")
"1bcd1" ("a" и "e" заменены на "1")
"5" ("abcde" заменено на "5")
"abcde" (без замены подстрок)
Однако следующие аббревиатуры недействительны:
"23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные.
"22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются.
Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке.
Пример:
👨💻 Алгоритм:
1⃣Создание битовых масок
Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.
2⃣Генерация аббревиатур
Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик.
3⃣Перебор всех комбинаций
Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Обобщенная аббревиатура слова может быть построена путем замены любых неперекрывающихся и несмежных подстрок на их соответствующие длины.
Например, "abcde" можно сократить следующим образом:
"a3e" ("bcd" заменено на "3")
"1bcd1" ("a" и "e" заменены на "1")
"5" ("abcde" заменено на "5")
"abcde" (без замены подстрок)
Однако следующие аббревиатуры недействительны:
"23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные.
"22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются.
Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке.
Пример:
Input: word = "a"
Output: ["1","a"]
👨💻 Алгоритм:
1⃣Создание битовых масок
Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.
2⃣Генерация аббревиатур
Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик.
3⃣Перебор всех комбинаций
Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.
😎 Решение:
class Solution:
def generateAbbreviations(self, word: str):
def abbr(word, x):
builder = []
k = 0
for i in range(len(word)):
if x & 1 == 0:
if k != 0:
builder.append(str(k))
k = 0
builder.append(word[i])
else:
k += 1
x >>= 1
if k != 0:
builder.append(str(k))
return ''.join(builder)
ans = []
for x in range(1 << len(word)):
ans.append(abbr(word, x))
return ans
Ставь 👍 и забирай 📚 Базу знаний
Завтра последний день!
Успей купить пожизненный easyoffer PRO - по цене 1 года
Покупаешь один раз — пользуешься всю жизнь.
👉 Акция до 31 марта: https://easyoffer.ru/pro
Успей купить пожизненный easyoffer PRO - по цене 1 года
Покупаешь один раз — пользуешься всю жизнь.
👉 Акция до 31 марта: https://easyoffer.ru/pro
Задача: 683. K Empty Slots
Сложность: hard
У вас есть n лампочек, расположенных в ряд и пронумерованных от 1 до n. Изначально все лампочки выключены. Каждый день мы включаем ровно одну лампочку, и через n дней все лампочки будут включены.
Вам дан массив bulbs длины n, где bulbs[i] = x означает, что в (i+1)-й день мы включим лампочку в позиции x, где i индексируется с 0, а x индексируется с 1.
Дано целое число k, верните минимальный номер дня, такой что существует две включенные лампочки, между которыми ровно k выключенных лампочек. Если такого дня не существует, верните -1.
Пример:
👨💻 Алгоритм:
1⃣Поддерживайте active, отсортированную структуру данных, содержащую каждую лампочку, которая в данный момент включена. Это позволит быстро находить соседей для вновь добавленных лампочек и проверять условия задачи.
2⃣Когда вы добавляете лампочку в active, проверьте ее нижних и верхних соседей. Для этого найдите ближайшие включенные лампочки с обеих сторон и проверьте количество выключенных лампочек между ними.
3⃣Если какой-то сосед удовлетворяет условию (ровно k выключенных лампочек между двумя включенными), значит, условие впервые произошло в этот день, и вы можете вернуть номер этого дня. Если такого дня не существует после включения всех лампочек, верните -1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
У вас есть n лампочек, расположенных в ряд и пронумерованных от 1 до n. Изначально все лампочки выключены. Каждый день мы включаем ровно одну лампочку, и через n дней все лампочки будут включены.
Вам дан массив bulbs длины n, где bulbs[i] = x означает, что в (i+1)-й день мы включим лампочку в позиции x, где i индексируется с 0, а x индексируется с 1.
Дано целое число k, верните минимальный номер дня, такой что существует две включенные лампочки, между которыми ровно k выключенных лампочек. Если такого дня не существует, верните -1.
Пример:
Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.
👨💻 Алгоритм:
1⃣Поддерживайте active, отсортированную структуру данных, содержащую каждую лампочку, которая в данный момент включена. Это позволит быстро находить соседей для вновь добавленных лампочек и проверять условия задачи.
2⃣Когда вы добавляете лампочку в active, проверьте ее нижних и верхних соседей. Для этого найдите ближайшие включенные лампочки с обеих сторон и проверьте количество выключенных лампочек между ними.
3⃣Если какой-то сосед удовлетворяет условию (ровно k выключенных лампочек между двумя включенными), значит, условие впервые произошло в этот день, и вы можете вернуть номер этого дня. Если такого дня не существует после включения всех лампочек, верните -1.
😎 Решение:
from sortedcontainers import SortedList
class Solution:
def kEmptySlots(self, flowers: List[int], k: int) -> int:
active = SortedList()
day = 0
for flower in flowers:
day += 1
active.add(flower)
idx = active.index(flower)
if idx > 0 and flower - active[idx - 1] - 1 == k:
return day
if idx < len(active) - 1 and active[idx + 1] - flower - 1 == k:
return day
return -1
Ставь 👍 и забирай 📚 Базу знаний
Задача: 941. Valid Mountain Array
Сложность: easy
Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Пример:
👨💻 Алгоритм:
1⃣Убедиться, что длина массива не меньше 3.
2⃣Найти вершину горы, которая удовлетворяет условиям горного массива.
Проверить, что все элементы слева от вершины строго возрастают.
Проверить, что все элементы справа от вершины строго убывают.
3⃣Вернуть true, если оба условия выполнены, иначе вернуть false.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Пример:
Input: arr = [2,1]
Output: false
👨💻 Алгоритм:
1⃣Убедиться, что длина массива не меньше 3.
2⃣Найти вершину горы, которая удовлетворяет условиям горного массива.
Проверить, что все элементы слева от вершины строго возрастают.
Проверить, что все элементы справа от вершины строго убывают.
3⃣Вернуть true, если оба условия выполнены, иначе вернуть false.
😎 Решение:
def validMountainArray(arr):
if len(arr) < 3:
return False
i = 1
while i < len(arr) and arr[i] > arr[i - 1]:
i += 1
if i == 1 or i == len(arr):
return False
while i < len(arr) and arr[i] < arr[i - 1]:
i += 1
return i == len(arr)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1263. Minimum Moves to Move a Box to Their Target Location
Сложность: hard
Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1.
Пример:
👨💻 Алгоритм:
1⃣Выполните поиск в ширину (BFS) для всех возможных позиций игрока и коробки, отслеживая количество толчков.
2⃣Используйте очередь для хранения состояний игрока и коробки, а также текущего количества толчков.
3⃣Для каждого состояния проверяйте все возможные движения игрока и перемещения коробки, обновляйте очередь и отмечайте посещенные состояния.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1.
Пример:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 3
👨💻 Алгоритм:
1⃣Выполните поиск в ширину (BFS) для всех возможных позиций игрока и коробки, отслеживая количество толчков.
2⃣Используйте очередь для хранения состояний игрока и коробки, а также текущего количества толчков.
3⃣Для каждого состояния проверяйте все возможные движения игрока и перемещения коробки, обновляйте очередь и отмечайте посещенные состояния.
😎 Решение:
from collections import deque
def minPushBox(grid):
m, n = len(grid), len(grid[0])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def valid(x, y):
return 0 <= x < m and 0 <= y < n and grid[x][y] != '#'
def bfs(start):
queue = deque([start])
visited = set([start])
while queue:
px, py, bx, by, pushes = queue.popleft()
if (bx, by) == target:
return pushes
for dx, dy in directions:
npx, npy = px + dx, py + dy
if valid(npx, npy) and (npx, npy, bx, by, pushes) not in visited:
if (npx, npy) == (bx, by):
nbx, nby = bx + dx, by + dy
if valid(nbx, nby) and (npx, npy, nbx, nby, pushes + 1) not in visited:
queue.append((npx, npy, nbx, nby, pushes + 1))
visited.add((npx, npy, nbx, nby, pushes + 1))
else:
queue.append((npx, npy, bx, by, pushes))
visited.add((npx, npy, bx, by, pushes))
return -1
for i in range(m):
for j in range(n):
if grid[i][j] == 'S':
player = (i, j)
elif grid[i][j] == 'B':
box = (i, j)
elif grid[i][j] == 'T':
target = (i, j)
return bfs((*player, *box, 0))
Ставь 👍 и забирай 📚 Базу знаний
🔥2👍1
Задача: 398. Random Pick Index
Сложность: medium
Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования.
2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным.
3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата.
Пример:
Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]
👨💻 Алгоритм:
1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования.
2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным.
3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса.
😎 Решение:
import random
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
def pick(self, target: int) -> int:
count = 0
result = -1
for i, num in enumerate(self.nums):
if num == target:
count += 1
if random.randint(1, count) == count:
result = i
return result
Ставь 👍 и забирай 📚 Базу знаний
Задача: 162. Find Peak Element
Сложность: medium
Пиковым элементом называется элемент, который строго больше своих соседей.
Для массива целых чисел nums с индексацией с нуля найдите пиковый элемент и верните его индекс. Если в массиве несколько пиков, верните индекс любого из пиков.
Вы можете представить, что nums[-1] = nums[n] = -∞. Другими словами, элемент всегда считается строго большим, чем сосед, находящийся за пределами массива.
Необходимо написать алгоритм, который работает за время O(log n).
Пример:
👨💻 Алгоритм:
1️⃣Начальная проверка:
Определяем средний элемент массива mid как mid = low + (high - low) / 2. Это помогает предотвратить возможное переполнение при больших значениях индексов.
2️⃣Определение направления поиска:
Сравниваем элемент nums[mid] с его правым соседом nums[mid + 1]. Если nums[mid] меньше nums[mid + 1], это указывает на наличие восходящей последовательности, и мы двигаемся вправо, устанавливая low = mid + 1. Это потому, что пик гарантированно находится в правой части.
Если nums[mid] больше nums[mid + 1], это указывает на наличие нисходящей последовательности, и пик находится либо в mid, либо слева от него, тогда устанавливаем high = mid.
3️⃣Завершение поиска:
Процесс продолжается до тех пор, пока low не станет равным high, что означает сужение поисковой области до одного элемента, который и является пиком, поскольку мы исключили все другие возможности.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Пиковым элементом называется элемент, который строго больше своих соседей.
Для массива целых чисел nums с индексацией с нуля найдите пиковый элемент и верните его индекс. Если в массиве несколько пиков, верните индекс любого из пиков.
Вы можете представить, что nums[-1] = nums[n] = -∞. Другими словами, элемент всегда считается строго большим, чем сосед, находящийся за пределами массива.
Необходимо написать алгоритм, который работает за время O(log n).
Пример:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
👨💻 Алгоритм:
1️⃣Начальная проверка:
Определяем средний элемент массива mid как mid = low + (high - low) / 2. Это помогает предотвратить возможное переполнение при больших значениях индексов.
2️⃣Определение направления поиска:
Сравниваем элемент nums[mid] с его правым соседом nums[mid + 1]. Если nums[mid] меньше nums[mid + 1], это указывает на наличие восходящей последовательности, и мы двигаемся вправо, устанавливая low = mid + 1. Это потому, что пик гарантированно находится в правой части.
Если nums[mid] больше nums[mid + 1], это указывает на наличие нисходящей последовательности, и пик находится либо в mid, либо слева от него, тогда устанавливаем high = mid.
3️⃣Завершение поиска:
Процесс продолжается до тех пор, пока low не станет равным high, что означает сужение поисковой области до одного элемента, который и является пиком, поскольку мы исключили все другие возможности.
😎 Решение:
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
return self.search(nums, 0, len(nums) - 1)
def search(self, nums: List[int], l: int, r: int) -> int:
if l == r:
return l
mid = (l + r) // 2
if nums[mid] > nums[mid + 1]:
return self.search(nums, l, mid)
return self.search(nums, mid + 1, r)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1474. Delete N Nodes After M Nodes of a Linked List
Сложность: easy
Вам дано начало связанного списка и два целых числа m и n.
Пройдите по связанному списку и удалите некоторые узлы следующим образом:
Начните с головы как текущего узла.
Сохраните первые m узлов, начиная с текущего узла.
Удалите следующие n узлов.
Продолжайте повторять шаги 2 и 3, пока не достигнете конца списка.
Верните голову изменённого списка после удаления указанных узлов.
Пример:
👨💻 Алгоритм:
1⃣Инициализация указателей:
Инициализируйте currentNode на голову связанного списка. Этот указатель будет использоваться для линейного прохода по каждому узлу списка.
Инициализируйте lastMNode на голову связанного списка.
2⃣Итерация по списку:
Итеративно удаляйте n узлов после m узлов, продолжая до конца списка.
Проходите m узлов, обновляя lastMNode на текущий узел. После m итераций lastMNode указывает на m-й узел.
Продолжайте итерацию по n узлам.
3⃣Удаление узлов:
Чтобы удалить n узлов, измените указатель next у lastMNode, чтобы он указывал на currentNode после пропуска n узлов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Вам дано начало связанного списка и два целых числа m и n.
Пройдите по связанному списку и удалите некоторые узлы следующим образом:
Начните с головы как текущего узла.
Сохраните первые m узлов, начиная с текущего узла.
Удалите следующие n узлов.
Продолжайте повторять шаги 2 и 3, пока не достигнете конца списка.
Верните голову изменённого списка после удаления указанных узлов.
Пример:
Input: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3
Output: [1,2,6,7,11,12]
Explanation: Keep the first (m = 2) nodes starting from the head of the linked List (1 ->2) show in black nodes.
Delete the next (n = 3) nodes (3 -> 4 -> 5) show in read nodes.
Continue with the same procedure until reaching the tail of the Linked List.
Head of the linked list after removing nodes is returned.
👨💻 Алгоритм:
1⃣Инициализация указателей:
Инициализируйте currentNode на голову связанного списка. Этот указатель будет использоваться для линейного прохода по каждому узлу списка.
Инициализируйте lastMNode на голову связанного списка.
2⃣Итерация по списку:
Итеративно удаляйте n узлов после m узлов, продолжая до конца списка.
Проходите m узлов, обновляя lastMNode на текущий узел. После m итераций lastMNode указывает на m-й узел.
Продолжайте итерацию по n узлам.
3⃣Удаление узлов:
Чтобы удалить n узлов, измените указатель next у lastMNode, чтобы он указывал на currentNode после пропуска n узлов.
😎 Решение:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
currentNode = head
lastMNode = head
while currentNode:
mCount, nCount = m, n
while currentNode and mCount > 0:
lastMNode = currentNode
currentNode = currentNode.next
mCount -= 1
while currentNode and nCount > 0:
currentNode = currentNode.next
nCount -= 1
lastMNode.next = currentNode
return head
Ставь 👍 и забирай 📚 Базу знаний
Задача: 733. Flood Fill
Сложность: easy
Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.
Пример:
👨💻 Алгоритм:
1⃣Получите цвет начального пикселя.
2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет.
3⃣Обновите изображение и верните его.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.
Пример:
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
👨💻 Алгоритм:
1⃣Получите цвет начального пикселя.
2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет.
3⃣Обновите изображение и верните его.
😎 Решение:
def floodFill(image, sr, sc, color):
original_color = image[sr][sc]
if original_color == color:
return image
def dfs(x, y):
if x < 0 or x >= len(image) or y < 0 or y >= len(image[0]) or image[x][y] != original_color:
return
image[x][y] = color
dfs(x + 1, y)
dfs(x - 1, y)
dfs(x, y + 1)
dfs(x, y - 1)
dfs(sr, sc)
return image
Ставь 👍 и забирай 📚 Базу знаний
🔥1
Задача: 635. Design Log Storage System
Сложность: medium
Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения.
int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать.
Пример:
👨💻 Алгоритм:
1⃣Инициализация и хранение журналов
Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения.
2⃣Формирование диапазона
Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity.
3⃣Фильтрация и возврат результатов
Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения.
int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать.
Пример:
Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]
👨💻 Алгоритм:
1⃣Инициализация и хранение журналов
Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения.
2⃣Формирование диапазона
Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity.
3⃣Фильтрация и возврат результатов
Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон.
😎 Решение:
class LogSystem:
def __init__(self):
self.logs = []
def put(self, id: int, timestamp: str) -> None:
self.logs.append((id, timestamp))
def retrieve(self, start: str, end: str, granularity: str) -> [int]:
index = {
'Year': 4,
'Month': 7,
'Day': 10,
'Hour': 13,
'Minute': 16,
'Second': 19
}[granularity]
start = start[:index]
end = end[:index]
result = []
for id, timestamp in self.logs:
if start <= timestamp[:index] <= end:
result.append(id)
return result
Ставь 👍 и забирай 📚 Базу знаний
Задача: 459. Repeated Substring Pattern
Сложность: easy
Дана строка s, проверьте, может ли она быть построена путем взятия подстроки и добавления нескольких копий этой подстроки друг за другом.
Пример:
👨💻 Алгоритм:
1⃣Создайте целочисленную переменную n, равную длине строки s.
2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2:
Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s.
Если pattern равен s, вернуть true.
3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дана строка s, проверьте, может ли она быть построена путем взятия подстроки и добавления нескольких копий этой подстроки друг за другом.
Пример:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
👨💻 Алгоритм:
1⃣Создайте целочисленную переменную n, равную длине строки s.
2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2:
Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s.
Если pattern равен s, вернуть true.
3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false.
😎 Решение:
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
for i in range(1, n // 2 + 1):
if n % i == 0:
pattern = s[:i] * (n // i)
if s == pattern:
return True
return False
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1473. Paint House III
Сложность: hard
Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.
Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.
Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.
Пример:
👨💻 Алгоритм:
1⃣Инициализация и базовые случаи:
Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1.
Создайте метод findMinCost, который проверяет базовые случаи:
- если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST.
- если количество соседств больше target, возвращайте MAX_COST.
Если результат уже вычислен, возвращайте его из memo.
2⃣Рекурсивное вычисление минимальной стоимости:
Если дом уже покрашен, обновите количество соседств и вызовите рекурсивный метод для следующего дома.
Если дом не покрашен, попробуйте покрасить его в каждый возможный цвет, обновите количество соседств и вызовите рекурсивный метод для следующего дома. Храните минимальную стоимость.
3⃣Метод minCost:
Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.
Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.
Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.
Пример:
Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.
👨💻 Алгоритм:
1⃣Инициализация и базовые случаи:
Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1.
Создайте метод findMinCost, который проверяет базовые случаи:
- если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST.
- если количество соседств больше target, возвращайте MAX_COST.
Если результат уже вычислен, возвращайте его из memo.
2⃣Рекурсивное вычисление минимальной стоимости:
Если дом уже покрашен, обновите количество соседств и вызовите рекурсивный метод для следующего дома.
Если дом не покрашен, попробуйте покрасить его в каждый возможный цвет, обновите количество соседств и вызовите рекурсивный метод для следующего дома. Храните минимальную стоимость.
3⃣Метод minCost:
Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1.
😎 Решение:
class Solution:
def __init__(self):
self.MAX_COST = 1000001
self.memo = {}
def findMinCost(self, houses, cost, targetCount, currIndex, neighborhoodCount, prevHouseColor):
if currIndex == len(houses):
return 0 if neighborhoodCount == targetCount else self.MAX_COST
if neighborhoodCount > targetCount:
return self.MAX_COST
if (currIndex, neighborhoodCount, prevHouseColor) in self.memo:
return self.memo[(currIndex, neighborhoodCount, prevHouseColor)]
minCost = self.MAX_COST
if houses[currIndex] != 0:
newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor)
minCost = self.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex])
else:
for color in range(1, len(cost[0]) + 1):
newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor)
currCost = cost[currIndex][color - 1] + self.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color)
minCost = min(minCost, currCost)
self.memo[(currIndex, neighborhoodCount, prevHouseColor)] = minCost
return minCost
def minCost(self, houses, cost, m, n, target):
answer = self.findMinCost(houses, cost, target, 0, 0, 0)
return -1 if answer == self.MAX_COST else answer
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1342. Number of Steps to Reduce a Number to Zero
Сложность: easy
Дано целое число num, вернуть количество шагов, необходимых для его сокращения до нуля.
На каждом шаге, если текущее число четное, его нужно разделить на 2, в противном случае, вы должны вычесть из него 1.
Пример:
👨💻 Алгоритм:
1⃣На каждом шаге проверяйте, четное ли текущее число, используя оператор остатка от деления (%). Если число четное (number % 2 == 0), разделите его на 2.
2⃣Если число нечетное (number % 2 == 1), вычтите из него 1.
3⃣После выполнения каждого из этих действий увеличивайте счетчик шагов на 1, чтобы в конце вернуть его значение.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дано целое число num, вернуть количество шагов, необходимых для его сокращения до нуля.
На каждом шаге, если текущее число четное, его нужно разделить на 2, в противном случае, вы должны вычесть из него 1.
Пример:
Input: num = 14
Output: 6
Explanation:
Step 1) 14 is even; divide by 2 and obtain 7.
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3.
Step 4) 3 is odd; subtract 1 and obtain 2.
Step 5) 2 is even; divide by 2 and obtain 1.
Step 6) 1 is odd; subtract 1 and obtain 0.
👨💻 Алгоритм:
1⃣На каждом шаге проверяйте, четное ли текущее число, используя оператор остатка от деления (%). Если число четное (number % 2 == 0), разделите его на 2.
2⃣Если число нечетное (number % 2 == 1), вычтите из него 1.
3⃣После выполнения каждого из этих действий увеличивайте счетчик шагов на 1, чтобы в конце вернуть его значение.
😎 Решение:
def numberOfSteps(num):
steps = 0
while num != 0:
if num % 2 == 0:
num //= 2
else:
num -= 1
steps += 1
return steps
Ставь 👍 и забирай 📚 Базу знаний