Задача: 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
Ставь 👍 и забирай 📚 Базу знаний