Задача: 1422. Maximum Score After Splitting a String
Сложность: easy
Дана строка s из нулей и единиц. Верните максимальное количество очков после разбиения строки на две непустые подстроки (т.е. левую подстроку и правую подстроку).
Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке.
Пример:
👨💻 Алгоритм:
1⃣Посчитайте количество единиц в строке и инициализируйте счётчики нулей и максимального значения.
2⃣Перебирайте символы строки до предпоследнего символа, обновляя счётчики нулей и единиц.
3⃣Обновляйте максимальное значение, если текущая сумма нулей и единиц больше предыдущего максимума.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дана строка s из нулей и единиц. Верните максимальное количество очков после разбиения строки на две непустые подстроки (т.е. левую подстроку и правую подстроку).
Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке.
Пример:
Input: s = "011101"
Output: 5
Explanation:
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5
left = "01" and right = "1101", score = 1 + 3 = 4
left = "011" and right = "101", score = 1 + 2 = 3
left = "0111" and right = "01", score = 1 + 1 = 2
left = "01110" and right = "1", score = 2 + 1 = 3
👨💻 Алгоритм:
1⃣Посчитайте количество единиц в строке и инициализируйте счётчики нулей и максимального значения.
2⃣Перебирайте символы строки до предпоследнего символа, обновляя счётчики нулей и единиц.
3⃣Обновляйте максимальное значение, если текущая сумма нулей и единиц больше предыдущего максимума.
😎 Решение:
class Solution:
def maxScore(self, s: str) -> int:
ones = s.count('1')
zeros = ans = 0
for i in range(len(s) - 1):
if s[i] == '1':
ones -= 1
else:
zeros += 1
ans = max(ans, zeros + ones)
return ans
Ставь 👍 и забирай 📚 Базу знаний
💊1
Задача: 752. Open the Lock
Сложность: medium
Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.
Пример:
👨💻 Алгоритм:
1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.
2⃣Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное.
3⃣Если очередь пуста и целевое состояние не найдено, верните -1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.
Пример:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
👨💻 Алгоритм:
1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.
2⃣Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное.
3⃣Если очередь пуста и целевое состояние не найдено, верните -1.
😎 Решение:
from collections import deque
def openLock(deadends, target):
def neighbors(node):
for i in range(4):
x = int(node[i])
for d in (-1, 1):
y = (x + d) % 10
yield node[:i] + str(y) + node[i+1:]
dead = set(deadends)
queue = deque([('0000', 0)])
visited = {'0000'}
while queue:
node, steps = queue.popleft()
if node == target:
return steps
if node in dead:
continue
for neighbor in neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, steps + 1))
return -1
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1441. Build an Array With Stack Operations
Сложность: medium
Вам дан целочисленный массив target и целое число n.
У вас есть пустой стек с двумя следующими операциями:
"Push": добавляет целое число на вершину стека.
"Pop": удаляет целое число с вершины стека.
Также у вас есть поток целых чисел в диапазоне [1, n].
Используйте две операции стека, чтобы сделать числа в стеке (от нижнего к верхнему) равными target. Вы должны следовать следующим правилам:
Если поток чисел не пуст, возьмите следующее целое число из потока и поместите его на вершину стека.
Если стек не пуст, извлеките целое число с вершины стека.
Если в любой момент элементы в стеке (от нижнего к верхнему) равны target, не берите новые числа из потока и не выполняйте больше операций со стеком.
Верните операции стека, необходимые для построения target согласно указанным правилам. Если существует несколько правильных ответов, верните любой из них.
Пример:
👨💻 Алгоритм:
1⃣Инициализировать пустой список ans и переменную i равной 0.
2⃣Для каждого элемента num в target:
Пока i < num - 1:
Добавить "Push" в ans.
Добавить "Pop" в ans.
Увеличить i.
Добавить "Push" в ans.
Увеличить i.
3⃣Вернуть ans.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дан целочисленный массив target и целое число n.
У вас есть пустой стек с двумя следующими операциями:
"Push": добавляет целое число на вершину стека.
"Pop": удаляет целое число с вершины стека.
Также у вас есть поток целых чисел в диапазоне [1, n].
Используйте две операции стека, чтобы сделать числа в стеке (от нижнего к верхнему) равными target. Вы должны следовать следующим правилам:
Если поток чисел не пуст, возьмите следующее целое число из потока и поместите его на вершину стека.
Если стек не пуст, извлеките целое число с вершины стека.
Если в любой момент элементы в стеке (от нижнего к верхнему) равны target, не берите новые числа из потока и не выполняйте больше операций со стеком.
Верните операции стека, необходимые для построения target согласно указанным правилам. Если существует несколько правильных ответов, верните любой из них.
Пример:
Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Pop the integer on the top of the stack. s = [1].
Read 3 from the stream and push it to the stack. s = [1,3].
👨💻 Алгоритм:
1⃣Инициализировать пустой список ans и переменную i равной 0.
2⃣Для каждого элемента num в target:
Пока i < num - 1:
Добавить "Push" в ans.
Добавить "Pop" в ans.
Увеличить i.
Добавить "Push" в ans.
Увеличить i.
3⃣Вернуть ans.
😎 Решение:
class Solution:
def buildArray(self, target: List[int], n: int) -> List[str]:
ans = []
i = 0
for num in target:
while i < num - 1:
ans.append("Push")
ans.append("Pop")
i += 1
ans.append("Push")
i += 1
return ans
Ставь 👍 и забирай 📚 Базу знаний
Задача: 835. Image Overlap
Сложность: medium
Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.
Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.
Верните максимальное возможное перекрытие.
Пример:
👨💻 Алгоритм:
1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.
2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).
3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.
Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.
Верните максимальное возможное перекрытие.
Пример:
Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.
👨💻 Алгоритм:
1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.
2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).
3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.
😎 Решение:
class Solution:
def shiftAndCount(self, xShift, yShift, M, R):
leftShiftCount = 0
rightShiftCount = 0
rRow = 0
for mRow in range(yShift, len(M)):
rCol = 0
for mCol in range(xShift, len(M)):
if M[mRow][mCol] == 1 and M[mRow][mCol] == R[rRow][rCol]:
leftShiftCount += 1
if M[mRow][rCol] == 1 and M[mRow][rCol] == R[rRow][mCol]:
rightShiftCount += 1
rCol += 1
rRow += 1
return max(leftShiftCount, rightShiftCount)
def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
maxOverlaps = 0
for yShift in range(len(A)):
for xShift in range(len(A)):
maxOverlaps = max(maxOverlaps, self.shiftAndCount(xShift, yShift, A, B))
maxOverlaps = m
Ставь 👍 и забирай 📚 Базу знаний
Задача: 384. Shuffle an Array
Сложность: medium
Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.
Реализуйте класс Solution:
Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.
Пример:
👨💻 Алгоритм:
1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива.
2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент.
3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.
Реализуйте класс Solution:
Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.
Пример:
Input: ransomNote = "a", magazine = "b"
Output: false
👨💻 Алгоритм:
1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива.
2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент.
3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие.
😎 Решение:
import random
class Solution:
def __init__(self, nums: list[int]):
self.array = nums[:]
self.original = nums[:]
def reset(self) -> list[int]:
self.array = self.original[:]
return self.original
def shuffle(self) -> list[int]:
for i in range(len(self.array)):
rand_index = random.randint(i, len(self.array) - 1)
self.array[i], self.array[rand_index] = self.array[rand_index], self.array[i]
return self.array
Ставь 👍 и забирай 📚 Базу знаний
Задача: 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
Ставь 👍 и забирай 📚 Базу знаний
Задача: 325. Maximum Size Subarray Sum Equals k
Сложность: medium
Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0.
Пример:
👨💻 Алгоритм:
1⃣Инициализация переменных
Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов.
2⃣Итерация по массиву
На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i.
3⃣Возврат результата
Верните значение longestSubarray.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0.
Пример:
Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.
👨💻 Алгоритм:
1⃣Инициализация переменных
Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов.
2⃣Итерация по массиву
На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i.
3⃣Возврат результата
Верните значение longestSubarray.
😎 Решение:
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
prefixSum = 0
longestSubarray = 0
indices = {}
for i, num in enumerate(nums):
prefixSum += num
if prefixSum == k:
longestSubarray = i + 1
if prefixSum - k in indices:
longestSubarray = max(longestSubarray, i - indices[prefixSum - k])
if prefixSum not in indices:
indices[prefixSum] = i
return longestSubarray
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1055. Shortest Way to Form String
Сложность: medium
Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.
Пример:
👨💻 Алгоритм:
1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.
2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.
3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.
Пример:
Input: source = "abc", target = "abcbc"
Output: 2
👨💻 Алгоритм:
1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.
2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.
3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.
😎 Решение:
def minSubsequences(source, target):
subsequences_count = 0
target_index = 0
while target_index < len(target):
source_index = 0
subsequences_count += 1
start_index = target_index
while source_index < len(source) and target_index < len(target):
if source[source_index] == target[target_index]:
target_index += 1
source_index += 1
if target_index == start_index:
return -1
return subsequences_count
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1027. Longest Arithmetic Subsequence
Сложность: medium
Если задан массив nums целых чисел, верните длину самой длинной арифметической подпоследовательности в nums. Примечание: Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Последовательность seq является арифметической, если seq[i + 1] - seq[i] имеют одинаковое значение (для 0 <= i < seq.length - 1).
Пример:
👨💻 Алгоритм:
1⃣Инициализация переменных:
Создайте массив словарей dp, где dp[i][d] будет хранить длину самой длинной арифметической подпоследовательности, заканчивающейся на элементе i с разностью d.
2⃣Заполнение массива dp:
Пройдитесь по каждому элементу массива nums.
Для каждого элемента nums[j] (где j идет от 0 до i-1), вычислите разность d = nums[i] - nums[j].
Обновите dp[i][d] на основе значения dp[j][d].
3⃣Поиск максимальной длины:
Пройдите по массиву dp и найдите максимальное значение среди всех значений dp[i][d].
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Если задан массив nums целых чисел, верните длину самой длинной арифметической подпоследовательности в nums. Примечание: Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Последовательность seq является арифметической, если seq[i + 1] - seq[i] имеют одинаковое значение (для 0 <= i < seq.length - 1).
Пример:
Input: nums = [3,6,9,12]
Output: 4
👨💻 Алгоритм:
1⃣Инициализация переменных:
Создайте массив словарей dp, где dp[i][d] будет хранить длину самой длинной арифметической подпоследовательности, заканчивающейся на элементе i с разностью d.
2⃣Заполнение массива dp:
Пройдитесь по каждому элементу массива nums.
Для каждого элемента nums[j] (где j идет от 0 до i-1), вычислите разность d = nums[i] - nums[j].
Обновите dp[i][d] на основе значения dp[j][d].
3⃣Поиск максимальной длины:
Пройдите по массиву dp и найдите максимальное значение среди всех значений dp[i][d].
😎 Решение:
class Solution:
def longestArithSeqLength(self, nums: List[int]) -> int:
if not nums:
return 0
dp = [{} for _ in range(len(nums))]
max_length = 0
for i in range(len(nums)):
for j in range(i):
diff = nums[i] - nums[j]
if diff in dp[j]:
dp[i][diff] = dp[j][diff] + 1
else:
dp[i][diff] = 2 # Start a new sequence
max_length = max(max_length, dp[i][diff])
return max_length
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1376. Time Needed to Inform All Employees
Сложность: medium
В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.
У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.
Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости.
i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).
Верните количество минут, необходимых для того, чтобы сообщить всем сотрудникам о срочной новости.
Пример:
👨💻 Алгоритм:
1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.
2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.
3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.
У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.
Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости.
i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).
Верните количество минут, необходимых для того, чтобы сообщить всем сотрудникам о срочной новости.
Пример:
Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.
👨💻 Алгоритм:
1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.
2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.
3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.
😎 Решение:
class Solution:
def __init__(self):
self.maxTime = float('-inf')
def DFS(self, adjList, informTime, curr, time):
self.maxTime = max(self.maxTime, time)
for adjacent in adjList[curr]:
self.DFS(adjList, informTime, adjacent, time + informTime[curr])
def numOfMinutes(self, n, headID, manager, informTime):
adjList = [[] for _ in range(n)]
for i in range(n):
if manager[i] != -1:
adjList[manager[i]].append(i)
self.DFS(adjList, informTime, headID, 0)
return self.maxTime
Ставь 👍 и забирай 📚 Базу знаний