Задача: 901. Online Stock Span
Сложность: medium
Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня.
Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.
Пример:
👨💻 Алгоритм:
1⃣Инициализировать стек для хранения пар значений (цена, размах) и переменную для текущего индекса.
2⃣Для метода next:
Установить начальный размах текущего дня равным 1.
Пока стек не пуст и верхний элемент стека имеет цену меньше или равную текущей цене:
Добавить размах верхнего элемента стека к текущему размаху.
Удалить верхний элемент стека.
3⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня.
Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.
Пример:
Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]
👨💻 Алгоритм:
1⃣Инициализировать стек для хранения пар значений (цена, размах) и переменную для текущего индекса.
2⃣Для метода next:
Установить начальный размах текущего дня равным 1.
Пока стек не пуст и верхний элемент стека имеет цену меньше или равную текущей цене:
Добавить размах верхнего элемента стека к текущему размаху.
Удалить верхний элемент стека.
3⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.
😎 Решение:
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price):
span = 1
while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1]
self.stack.append((price, span))
return span
Ставь 👍 и забирай 📚 Базу знаний
Задача: 753. Cracking the Safe
Сложность: medium
Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.
Пример:
👨💻 Алгоритм:
1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].
2⃣Используйте алгоритм Эйлерова пути или цикла для нахождения пути, который проходит через каждое ребро ровно один раз.
3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.
Пример:
Input: n = 1, k = 2
Output: "10"
👨💻 Алгоритм:
1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].
2⃣Используйте алгоритм Эйлерова пути или цикла для нахождения пути, который проходит через каждое ребро ровно один раз.
3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.
😎 Решение:
def crackSafe(n, k):
seen = set()
result = []
def dfs(node):
for x in range(k):
neighbor = node + str(x)
if neighbor not in seen:
seen.add(neighbor)
dfs(neighbor[1:])
result.append(str(x))
start_node = '0' * (n - 1)
dfs(start_node)
return start_node + ''.join(result)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1423. Maximum Points You Can Obtain from Cards
Сложность: medium
Есть несколько карт, расположенных в ряд, и у каждой карты есть определенное количество очков. Очки представлены в виде целочисленного массива cardPoints.
За один шаг вы можете взять одну карту либо с начала, либо с конца ряда. Вы должны взять ровно k карт.
Ваш результат - это сумма очков взятых карт.
Дан целочисленный массив cardPoints и целое число k, верните максимальное количество очков, которое вы можете получить.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте два массива размера k + 1, frontSetOfCards и rearSetOfCards, чтобы хранить суммы очков, полученных при выборе первых i карт и последних i карт в массиве.
2⃣Рассчитайте префиксные суммы для первых k карт и последних k карт.
3⃣Итерируйте от 0 до k и вычисляйте возможное количество очков, выбирая i карт с начала массива и k - i карт с конца, обновляя максимальный результат при необходимости.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Есть несколько карт, расположенных в ряд, и у каждой карты есть определенное количество очков. Очки представлены в виде целочисленного массива cardPoints.
За один шаг вы можете взять одну карту либо с начала, либо с конца ряда. Вы должны взять ровно k карт.
Ваш результат - это сумма очков взятых карт.
Дан целочисленный массив cardPoints и целое число k, верните максимальное количество очков, которое вы можете получить.
Пример:
Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.
👨💻 Алгоритм:
1⃣Инициализируйте два массива размера k + 1, frontSetOfCards и rearSetOfCards, чтобы хранить суммы очков, полученных при выборе первых i карт и последних i карт в массиве.
2⃣Рассчитайте префиксные суммы для первых k карт и последних k карт.
3⃣Итерируйте от 0 до k и вычисляйте возможное количество очков, выбирая i карт с начала массива и k - i карт с конца, обновляя максимальный результат при необходимости.
😎 Решение:
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
n = len(cardPoints)
frontSetOfCards = [0] * (k + 1)
rearSetOfCards = [0] * (k + 1)
for i in range(k):
frontSetOfCards[i + 1] = cardPoints[i] + frontSetOfCards[i]
rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i]
maxScore = 0
for i in range(k + 1):
currentScore = frontSetOfCards[i] + rearSetOfCards[k - i]
maxScore = max(maxScore, currentScore)
return maxScore
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1470. Shuffle the Array
Сложность: easy
Дан массив nums, состоящий из 2n элементов в форме [x1, x2, ..., xn, y1, y2, ..., yn].
Верните массив в форме [x1, y1, x2, y2, ..., xn, yn].
Пример:
👨💻 Алгоритм:
1⃣Создайте массив result размером 2 * n.
2⃣Итеративно пройдите по массиву nums от 0 до n - 1:
Сохраните элемент xi+1, то есть nums[i], в индекс 2 * i массива result.
Сохраните элемент yi+1, то есть nums[i + n], в индекс 2 * i + 1 массива result.
3⃣Верните массив result.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан массив nums, состоящий из 2n элементов в форме [x1, x2, ..., xn, y1, y2, ..., yn].
Верните массив в форме [x1, y1, x2, y2, ..., xn, yn].
Пример:
Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7]
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].
👨💻 Алгоритм:
1⃣Создайте массив result размером 2 * n.
2⃣Итеративно пройдите по массиву nums от 0 до n - 1:
Сохраните элемент xi+1, то есть nums[i], в индекс 2 * i массива result.
Сохраните элемент yi+1, то есть nums[i + n], в индекс 2 * i + 1 массива result.
3⃣Верните массив result.
😎 Решение:
class Solution:
def shuffle(self, nums, n):
result = [0] * (2 * n)
for i in range(n):
result[2 * i] = nums[i]
result[2 * i + 1] = nums[n + i]
return result
Ставь 👍 и забирай 📚 Базу знаний
Задача: 201. Bitwise AND of Numbers Range
Сложность: medium
Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно.
Пример:
👨💻 Алгоритм:
1️⃣Сдвигать left и right вправо, пока они не станут равными.
2️⃣Подсчитать количество сдвигов.
3️⃣Сдвинуть left влево на количество сдвигов и вернуть результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно.
Пример:
Input: left = 5, right = 7
Output: 4
👨💻 Алгоритм:
1️⃣Сдвигать left и right вправо, пока они не станут равными.
2️⃣Подсчитать количество сдвигов.
3️⃣Сдвинуть left влево на количество сдвигов и вернуть результат.
😎 Решение:
class Solution:
def rangeBitwiseAnd(self, m: int, n: int) -> int:
shift = 0
while m < n:
m = m >> 1
n = n >> 1
shift += 1
return m << shift
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1424. Diagonal Traverse II
Сложность: medium
Дан двумерный целочисленный массив nums, верните все элементы nums в диагональном порядке.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте очередь с (0, 0) и список ответов ans.
2⃣Пока очередь не пуста:
Извлеките (row, col) из очереди.
Добавьте nums[row][col] в ans.
Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь.
Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь.
3⃣Верните ans.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан двумерный целочисленный массив nums, верните все элементы nums в диагональном порядке.
Пример:
Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
👨💻 Алгоритм:
1⃣Инициализируйте очередь с (0, 0) и список ответов ans.
2⃣Пока очередь не пуста:
Извлеките (row, col) из очереди.
Добавьте nums[row][col] в ans.
Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь.
Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь.
3⃣Верните ans.
😎 Решение:
from collections import deque
class Solution:
def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
queue = deque([(0, 0)])
ans = []
while queue:
row, col = queue.popleft()
ans.append(nums[row][col])
if col == 0 and row + 1 < len(nums):
queue.append((row + 1, col))
if col + 1 < len(nums[row]):
queue.append((row, col + 1))
return ans
Ставь 👍 и забирай 📚 Базу знаний
Задача: 953. Verifying an Alien Dictionary
Сложность: hard
В инопланетном языке, как ни странно, тоже используются английские строчные буквы, но, возможно, в другом порядке. Порядок алфавита - это некоторая перестановка строчных букв. Учитывая последовательность слов, написанных на инопланетном языке, и порядок алфавита, верните true тогда и только тогда, когда данные слова отсортированы лексикографически на этом инопланетном языке.
Пример:
👨💻 Алгоритм:
1⃣Создать словарь для хранения порядка каждой буквы в инопланетном языке.
Пройти по каждому слову и сравнить его с последующим словом.
2⃣Для каждого слова, сравнить буквы, используя созданный словарь порядка.
Если обнаружена пара слов, нарушающая порядок, вернуть false.
3⃣Если все слова отсортированы правильно, вернуть true.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
В инопланетном языке, как ни странно, тоже используются английские строчные буквы, но, возможно, в другом порядке. Порядок алфавита - это некоторая перестановка строчных букв. Учитывая последовательность слов, написанных на инопланетном языке, и порядок алфавита, верните true тогда и только тогда, когда данные слова отсортированы лексикографически на этом инопланетном языке.
Пример:
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
👨💻 Алгоритм:
1⃣Создать словарь для хранения порядка каждой буквы в инопланетном языке.
Пройти по каждому слову и сравнить его с последующим словом.
2⃣Для каждого слова, сравнить буквы, используя созданный словарь порядка.
Если обнаружена пара слов, нарушающая порядок, вернуть false.
3⃣Если все слова отсортированы правильно, вернуть true.
😎 Решение:
def isAlienSorted(words, order):
order_map = {char: i for i, char in enumerate(order)}
def compare(word1, word2):
for c1, c2 in zip(word1, word2):
if order_map[c1] < order_map[c2]:
return True
elif order_map[c1] > order_map[c2]:
return False
return len(word1) <= len(word2)
for i in range(len(words) - 1):
if not compare(words[i], words[i + 1]):
return False
return True
Ставь 👍 и забирай 📚 Базу знаний
Задача: 238. Product of Array Except Self
Сложность: medium
Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i].
Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число.
Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления.
Пример:
👨💻 Алгоритм:
1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1].
2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево.
3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i].
Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число.
Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления.
Пример:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
👨💻 Алгоритм:
1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1].
2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево.
3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его.
😎 Решение:
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
length = len(nums)
L = [1] * length
R = [1] * length
answer = [1] * length
for i in range(1, length):
L[i] = nums[i - 1] * L[i - 1]
for i in range(length - 2, -1, -1):
R[i] = nums[i + 1] * R[i + 1]
for i in range(length):
answer[i] = L[i] * R[i]
return answer
Ставь 👍 и забирай 📚 Базу знаний
Задача: 32. Longest Valid Parentheses
Сложность: hard
Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками.
Пример:
👨💻 Алгоритм:
1️⃣В этом подходе мы рассматриваем каждую возможную непустую подстроку чётной длины из заданной строки и проверяем, является ли она корректной строкой скобок. Для проверки корректности мы используем метод стека.
2️⃣Каждый раз, когда мы встречаем символ ‘(’, мы кладём его в стек. Для каждого встреченного символа ‘)’ мы извлекаем из стека символ ‘(’. Если символ ‘(’ недоступен в стеке для извлечения в любой момент или если в стеке остались элементы после обработки всей подстроки, подстрока скобок является некорректной.
3️⃣Таким образом, мы повторяем процесс для каждой возможной подстроки и продолжаем сохранять длину самой длинной найденной корректной строки.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками.
Пример:
Input: s = "(()"
Output: 2
👨💻 Алгоритм:
1️⃣В этом подходе мы рассматриваем каждую возможную непустую подстроку чётной длины из заданной строки и проверяем, является ли она корректной строкой скобок. Для проверки корректности мы используем метод стека.
2️⃣Каждый раз, когда мы встречаем символ ‘(’, мы кладём его в стек. Для каждого встреченного символа ‘)’ мы извлекаем из стека символ ‘(’. Если символ ‘(’ недоступен в стеке для извлечения в любой момент или если в стеке остались элементы после обработки всей подстроки, подстрока скобок является некорректной.
3️⃣Таким образом, мы повторяем процесс для каждой возможной подстроки и продолжаем сохранять длину самой длинной найденной корректной строки.
😎 Решение:
def is_valid(s: str) -> bool:
stack = []
for char in s:
if char == '(':
stack.append('(')
elif stack and stack[-1] == '(':
stack.pop()
else:
return False
return len(stack) == 0
def longest_valid_parentheses(s: str) -> int:
maxlen = 0
for i in range(len(s)):
for j in range(i + 2, len(s) + 1, 2):
substring = s[i:j]
if is_valid(substring):
maxlen = max(maxlen, j - i)
return maxlen
Ставь 👍 и забирай 📚 Базу знаний
🔥1🤔1
Задача: 993. Cousins in Binary Tree
Сложность: easy
Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.
Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей.
Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.
Пример:
👨💻 Алгоритм:
1⃣Поиск глубины и родителя для каждого узла:
Используйте поиск в глубину (DFS) для обхода дерева.
Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y.
2⃣Проверка условий на кузенов:
Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.
3⃣Возврат результата:
Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.
Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей.
Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.
Пример:
Input: root = [1,2,3,4], x = 4, y = 3
Output: false
👨💻 Алгоритм:
1⃣Поиск глубины и родителя для каждого узла:
Используйте поиск в глубину (DFS) для обхода дерева.
Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y.
2⃣Проверка условий на кузенов:
Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.
3⃣Возврат результата:
Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false.
😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
parent_x, parent_y = None, None
depth_x, depth_y = -1, -1
def dfs(node, parent, depth):
nonlocal parent_x, parent_y, depth_x, depth_y
if not node:
return
if node.val == x:
parent_x, depth_x = parent, depth
elif node.val == y:
parent_y, depth_y = parent, depth
else:
dfs(node.left, node, depth + 1)
dfs(node.right, node, depth + 1)
dfs(root, None, 0)
return depth_x == depth_y and parent_x != parent_y
Ставь 👍 и забирай 📚 Базу знаний
Задача: 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
Ставь 👍 и забирай 📚 Базу знаний