Задача: 907. Sum of Subarray Minimums
Сложность: medium
Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.
Пример:
👨💻 Алгоритм:
1⃣Использовать монотонный стек для нахождения ближайшего меньшего элемента слева и справа для каждого элемента массива.
2⃣Использовать эту информацию для вычисления количества подмассивов, где каждый элемент является минимальным.
3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.
Пример:
Input: arr = [3,1,2,4]
Output: 17
👨💻 Алгоритм:
1⃣Использовать монотонный стек для нахождения ближайшего меньшего элемента слева и справа для каждого элемента массива.
2⃣Использовать эту информацию для вычисления количества подмассивов, где каждый элемент является минимальным.
3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7.
😎 Решение:
def sumSubarrayMins(arr):
MOD = 10**9 + 7
n = len(arr)
left = [0] * n
right = [0] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
left[i] = i + 1 if not stack else i - stack[-1]
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
right[i] = n - i if not stack else stack[-1] - i
stack.append(i)
result = sum(a * l * r for a, l, r in zip(arr, left, right)) % MOD
return result
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1437. Check If All 1's Are at Least Length K Places Away
Сложность: easy
Дан бинарный массив nums и целое число k. Вернуть true, если все единицы находятся на расстоянии не менее k позиций друг от друга, в противном случае вернуть false.
Пример:
👨💻 Алгоритм:
1⃣Инициализировать счетчик нулей значением k для учета первого появления единицы.
2⃣Итерировать по массиву nums, проверяя, если текущий элемент равен 1. Если число нулей между единицами меньше k, вернуть false; иначе сбросить счетчик нулей на 0.
3⃣Если текущий элемент равен 0, увеличить счетчик нулей. В конце итерации вернуть true.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан бинарный массив nums и целое число k. Вернуть true, если все единицы находятся на расстоянии не менее k позиций друг от друга, в противном случае вернуть false.
Пример:
Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.
👨💻 Алгоритм:
1⃣Инициализировать счетчик нулей значением k для учета первого появления единицы.
2⃣Итерировать по массиву nums, проверяя, если текущий элемент равен 1. Если число нулей между единицами меньше k, вернуть false; иначе сбросить счетчик нулей на 0.
3⃣Если текущий элемент равен 0, увеличить счетчик нулей. В конце итерации вернуть true.
😎 Решение:
class Solution:
def kLengthApart(self, nums: List[int], k: int) -> bool:
count = k
for num in nums:
if num == 1:
if count < k:
return False
count = 0
else:
count += 1
return True
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1268. Search Suggestions System
Сложность: medium
Вам дан массив строк products и строка searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикографически минимальных продукта. Возвращается список списков предложенных продуктов после ввода каждого символа searchWord.
Пример:
👨💻 Алгоритм:
1⃣Отсортируйте массив продуктов.
2⃣Итерируйтесь по каждому символу в searchWord, находите все продукты, которые соответствуют текущему префиксу.
3⃣Сохраняйте не более трех лексикографически минимальных продуктов для каждого префикса.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дан массив строк products и строка searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикографически минимальных продукта. Возвращается список списков предложенных продуктов после ввода каждого символа searchWord.
Пример:
Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
👨💻 Алгоритм:
1⃣Отсортируйте массив продуктов.
2⃣Итерируйтесь по каждому символу в searchWord, находите все продукты, которые соответствуют текущему префиксу.
3⃣Сохраняйте не более трех лексикографически минимальных продуктов для каждого префикса.
😎 Решение:
def suggestedProducts(products, searchWord):
products.sort()
result = []
prefix = ""
for char in searchWord:
prefix += char
suggestions = [product for product in products if product.startswith(prefix)]
result.append(suggestions[:3])
return result
Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: 1434. Number of Ways to Wear Different Hats to Each Other
Сложность: hard
Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.
Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.
Вернуть количество способов, которыми n человек могут носить различные шляпы друг у друга.
Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7.
Пример:
👨💻 Алгоритм:
1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей.
2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп.
3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.
Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.
Вернуть количество способов, которыми n человек могут носить различные шляпы друг у друга.
Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7.
Пример:
Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions.
First person choose hat 3, Second person choose hat 4 and last one hat 5.
👨💻 Алгоритм:
1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей.
2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп.
3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп.
😎 Решение:
class Solution:
def numberWays(self, hats: List[List[int]]) -> int:
MOD = 1000000007
n = len(hats)
hatsToPeople = {}
for i, hatList in enumerate(hats):
for hat in hatList:
if hat not in hatsToPeople:
hatsToPeople[hat] = []
hatsToPeople[hat].append(i)
done = (1 << n) - 1
memo = [[-1] * done for _ in range(41)]
def dp(hat, mask):
if mask == done:
return 1
if hat > 40:
return 0
if memo[hat][mask] != -1:
return memo[hat][mask]
ans = dp(hat + 1, mask)
if hat in hatsToPeople:
for person in hatsToPeople[hat]:
if (mask & (1 << person)) == 0:
ans = (ans + dp(hat + 1, mask | (1 << person))) % MOD
memo[hat][mask] = ans
return ans
return dp(1, 0)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 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))
Ставь 👍 и забирай 📚 Базу знаний
Задача: 747. Largest Number At Least Twice of Others
Сложность: easy
Вам дан целочисленный массив nums, в котором наибольшее целое число уникально. Определите, является ли наибольший элемент массива по крайней мере в два раза больше всех остальных чисел в массиве. Если да, то верните индекс самого большого элемента, в противном случае верните -1.
Пример:
👨💻 Алгоритм:
1⃣Найдите максимальный элемент в массиве и его индекс.
2⃣Проверьте, является ли этот максимальный элемент по крайней мере в два раза больше всех остальных элементов массива.
3⃣Если условие выполняется, верните индекс максимального элемента, иначе верните -1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Вам дан целочисленный массив nums, в котором наибольшее целое число уникально. Определите, является ли наибольший элемент массива по крайней мере в два раза больше всех остальных чисел в массиве. Если да, то верните индекс самого большого элемента, в противном случае верните -1.
Пример:
Input: nums = [3,6,1,0]
Output: 1
👨💻 Алгоритм:
1⃣Найдите максимальный элемент в массиве и его индекс.
2⃣Проверьте, является ли этот максимальный элемент по крайней мере в два раза больше всех остальных элементов массива.
3⃣Если условие выполняется, верните индекс максимального элемента, иначе верните -1.
😎 Решение:
def dominantIndex(nums):
max_val = max(nums)
max_index = nums.index(max_val)
for num in nums:
if num != max_val and max_val < 2 * num:
return -1
return max_index
Ставь 👍 и забирай 📚 Базу знаний
Задача: 763. Partition Labels
Сложность: medium
Вам дана строка s. Мы хотим разбить строку на как можно больше частей так, чтобы каждая буква встречалась не более чем в одной части. Обратите внимание, что разбиение выполняется так, чтобы после конкатенации всех частей по порядку получилась строка s. Верните список целых чисел, представляющих размер этих частей.
Пример:
👨💻 Алгоритм:
1⃣Создайте словарь для хранения последней позиции каждой буквы в строке.
2⃣Пройдите по строке, отслеживая максимальную позицию текущей части.
3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дана строка s. Мы хотим разбить строку на как можно больше частей так, чтобы каждая буква встречалась не более чем в одной части. Обратите внимание, что разбиение выполняется так, чтобы после конкатенации всех частей по порядку получилась строка s. Верните список целых чисел, представляющих размер этих частей.
Пример:
Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
👨💻 Алгоритм:
1⃣Создайте словарь для хранения последней позиции каждой буквы в строке.
2⃣Пройдите по строке, отслеживая максимальную позицию текущей части.
3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую.
😎 Решение:
def partitionLabels(s):
last_pos = {char: idx for idx, char in enumerate(s)}
j, anchor = 0, 0
partitions = []
for i, char in enumerate(s):
j = max(j, last_pos[char])
if i == j:
partitions.append(i - anchor + 1)
anchor = i + 1
Ставь 👍 и забирай 📚 Базу знаний
💊1
Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium
Вам дан массив строк arr. Строка s образуется конкатенацией подпоследовательности arr, содержащей уникальные символы. Верните максимально возможную длину s. Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов.
Пример:
👨💻 Алгоритм:
1⃣Использование рекурсивного подхода:
Для каждой строки в массиве arr проверяем, можем ли мы добавить ее к текущей комбинации уникальных символов.
Если можем, добавляем ее и продолжаем рекурсивный вызов для следующей строки.
Если не можем, пропускаем текущую строку и переходим к следующей.
2⃣Проверка уникальности символов:
Для проверки уникальности символов используем множество (set). Если все символы строки уникальны и не пересекаются с символами текущей комбинации, мы можем добавить строку.
3⃣Поиск максимальной длины:
На каждом шаге обновляем максимальную длину, если текущая комбинация уникальных символов длиннее предыдущей максимальной длины.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дан массив строк arr. Строка s образуется конкатенацией подпоследовательности arr, содержащей уникальные символы. Верните максимально возможную длину s. Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов.
Пример:
Input: arr = ["un","iq","ue"]
Output: 4
👨💻 Алгоритм:
1⃣Использование рекурсивного подхода:
Для каждой строки в массиве arr проверяем, можем ли мы добавить ее к текущей комбинации уникальных символов.
Если можем, добавляем ее и продолжаем рекурсивный вызов для следующей строки.
Если не можем, пропускаем текущую строку и переходим к следующей.
2⃣Проверка уникальности символов:
Для проверки уникальности символов используем множество (set). Если все символы строки уникальны и не пересекаются с символами текущей комбинации, мы можем добавить строку.
3⃣Поиск максимальной длины:
На каждом шаге обновляем максимальную длину, если текущая комбинация уникальных символов длиннее предыдущей максимальной длины.
😎 Решение:
def maxLength(arr):
def is_unique(s):
return len(s) == len(set(s))
def backtrack(index, current):
if not is_unique(current):
return 0
max_length = len(current)
for i in range(index, len(arr)):
max_length = max(max_length, backtrack(i + 1, current + arr[i]))
return max_length
return backtrack(0, "")
Ставь 👍 и забирай 📚 Базу знаний
Задача: 826. Most Profit Assigning Work
Сложность: medium
У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где:
difficulty[i] и profit[i] — сложность и прибыль i-го задания,
worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]).
Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз.
Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0.
Верните максимальную прибыль, которую можно получить после распределения рабочих по заданиям.
Пример:
👨💻 Алгоритм:
1⃣Создание и сортировка профиля работы
Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности.
2⃣Обновление максимальной прибыли для каждой сложности
Обновите значение прибыли каждой сложности, чтобы оно было максимальным из текущего значения и предыдущего значения прибыли.
3⃣Вычисление максимальной прибыли
Для каждой способности рабочего используйте бинарный поиск, чтобы найти задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и верните ее.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где:
difficulty[i] и profit[i] — сложность и прибыль i-го задания,
worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]).
Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз.
Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0.
Верните максимальную прибыль, которую можно получить после распределения рабочих по заданиям.
Пример:
Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.
👨💻 Алгоритм:
1⃣Создание и сортировка профиля работы
Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности.
2⃣Обновление максимальной прибыли для каждой сложности
Обновите значение прибыли каждой сложности, чтобы оно было максимальным из текущего значения и предыдущего значения прибыли.
3⃣Вычисление максимальной прибыли
Для каждой способности рабочего используйте бинарный поиск, чтобы найти задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и верните ее.
😎 Решение:
class Solution:
def maxProfitAssignment(self, difficulty, profit, worker):
jobProfile = [(0, 0)]
for i in range(len(difficulty)):
jobProfile.append((difficulty[i], profit[i]))
jobProfile.sort()
for i in range(1, len(jobProfile)):
jobProfile[i] = (jobProfile[i][0], max(jobProfile[i][1], jobProfile[i-1][1]))
netProfit = 0
for ability in worker:
l, r = 0, len(jobProfile) - 1
jobProfit = 0
while l <= r:
mid = (l + r) // 2
if jobProfile[mid][0] <= ability:
jobProfit = max(jobProfit, jobProfile[mid][1])
l = mid + 1
else:
r = mid - 1
netProfit += jobPro
Ставь 👍 и забирай 📚 Базу знаний
Задача: 561. Array Partition
Сложность: easy
Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.
Пример:
👨💻 Алгоритм:
1⃣Отсортируйте массив nums в неубывающем порядке.
2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого).
3⃣Суммируйте выбранные элементы и верните эту сумму.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.
Пример:
Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.
👨💻 Алгоритм:
1⃣Отсортируйте массив nums в неубывающем порядке.
2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого).
3⃣Суммируйте выбранные элементы и верните эту сумму.
😎 Решение:
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
nums.sort()
return sum(nums[i] for i in range(0, len(nums), 2))
Ставь 👍 и забирай 📚 Базу знаний
Задача: 153. Find Minimum in Rotated Sorted Array
Сложность: Medium
Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать:
[4,5,6,7,0,1,2], если он был повернут 4 раза.
[0,1,2,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива.
Вы должны написать алгоритм, который работает за время O(log n).
Пример:
👨💻 Алгоритм:
1️⃣Нахождение середины массива: Определите элемент, находящийся посередине массива.
2️⃣Определение направления поиска: Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины. Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины.
3️⃣Остановка поиска при нахождении точки перегиба: Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий: nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом. nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: Medium
Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать:
[4,5,6,7,0,1,2], если он был повернут 4 раза.
[0,1,2,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива.
Вы должны написать алгоритм, который работает за время O(log n).
Пример:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
👨💻 Алгоритм:
1️⃣Нахождение середины массива: Определите элемент, находящийся посередине массива.
2️⃣Определение направления поиска: Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины. Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины.
3️⃣Остановка поиска при нахождении точки перегиба: Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий: nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом. nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом.
😎 Решение:
class Solution:
def findMin(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
left = 0
right = len(nums) - 1
if nums[right] > nums[0]:
return nums[0]
while right >= left:
mid = left + (right - left) // 2
if nums[mid] > nums[mid + 1]:
return nums[mid + 1]
if nums[mid - 1] > nums[mid]:
return nums[mid]
if nums[mid] > nums[0]:
left = mid + 1
else:
right = mid - 1
Ставь 👍 и забирай 📚 Базу знаний
Задача: 720. Longest Word in Dictionary
Сложность: medium
Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова.
Пример:
👨💻 Алгоритм:
1⃣Отсортируйте массив слов по длине и лексикографическому порядку.
2⃣Используйте множество для отслеживания слов, которые можно построить.
3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова.
Пример:
Input: words = ["w","wo","wor","worl","world"]
Output: "world"
👨💻 Алгоритм:
1⃣Отсортируйте массив слов по длине и лексикографическому порядку.
2⃣Используйте множество для отслеживания слов, которые можно построить.
3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве.
😎 Решение:
def longestWord(words):
words.sort()
valid_words = {""}
longest = ""
for word in words:
if word[:-1] in valid_words:
valid_words.add(word)
if len(word) > len(longest):
longest = word
return longest
Ставь 👍 и забирай 📚 Базу знаний
Задача: 537. Complex Number Multiplication
Сложность: medium
Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.
Пример:
👨💻 Алгоритм:
1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.
2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).
3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.
Пример:
Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.
👨💻 Алгоритм:
1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.
2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).
3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.
😎 Решение:
class Solution:
def complexNumberMultiply(self, a: str, b: str) -> str:
x = a.split('+')
y = b.split('+')
a_real = int(x[0])
a_img = int(x[1][:-1])
b_real = int(y[0])
b_img = int(y[1][:-1])
real_part = a_real * b_real - a_img * b_img
imaginary_part = a_real * b_img + a_img * b_real
return f"{real_part}+{imaginary_part}i"
Ставь 👍 и забирай 📚 Базу знаний
Задача: 221. Maximal Square
Сложность: medium
Дана бинарная матрица размером m x n, заполненная 0 и 1. Найдите наибольший квадрат, содержащий только 1, и верните его площадь.
Пример:
👨💻 Алгоритм:
1⃣Инициализировать 1D массив dp с нулями, чтобы хранить промежуточные результаты для каждого столбца, а также переменные maxsqlen для максимальной длины квадрата и prev для предыдущего значения.
2⃣Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением.
3⃣По завершении пройти по всем строкам и столбцам, вернуть квадрат maxsqlen как площадь наибольшего квадрата.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дана бинарная матрица размером m x n, заполненная 0 и 1. Найдите наибольший квадрат, содержащий только 1, и верните его площадь.
Пример:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
👨💻 Алгоритм:
1⃣Инициализировать 1D массив dp с нулями, чтобы хранить промежуточные результаты для каждого столбца, а также переменные maxsqlen для максимальной длины квадрата и prev для предыдущего значения.
2⃣Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением.
3⃣По завершении пройти по всем строкам и столбцам, вернуть квадрат maxsqlen как площадь наибольшего квадрата.
😎 Решение:
class Solution:
def maximalSquare(self, matrix):
rows = len(matrix)
cols = len(matrix[0]) if rows > 0 else 0
dp = [0] * (cols + 1)
maxsqlen = 0
prev = 0
for i in range(1, rows + 1):
for j in range(1, cols + 1):
temp = dp[j]
if matrix[i - 1][j - 1] == "1":
dp[j] = min(min(dp[j - 1], prev), dp[j]) + 1
maxsqlen = max(maxsqlen, dp[j])
else:
dp[j] = 0
prev = temp
return maxsqlen * maxsqlen
Ставь 👍 и забирай 📚 Базу знаний
Задача: 34. Find First and Last Position of Element in Sorted Array
Сложность: medium
Дан массив целых чисел nums, отсортированный в неубывающем порядке, найдите начальную и конечную позицию заданного целевого значения.
Если целевое значение не найдено в массиве, верните [-1, -1].
Вы должны написать алгоритм со временной сложностью O(log n).
Пример:
👨💻 Алгоритм:
1️⃣Определите функцию под названием findBound, которая принимает три аргумента: массив, целевое значение для поиска и булевое значение isFirst, указывающее, ищем ли мы первое или последнее вхождение цели.
Мы используем 2 переменные для отслеживания подмассива, который мы сканируем. Назовем их begin и end. Изначально begin устанавливается в 0, а end — в последний индекс массива.
2️⃣Мы итерируем, пока begin не станет больше, чем end.
На каждом шаге мы вычисляем средний элемент mid = (begin + end) / 2. Мы используем значение среднего элемента, чтобы решить, какую половину массива нам нужно искать.
Если nums[mid] == target:
Если isFirst true — это означает, что мы пытаемся найти первое вхождение элемента. Если mid == begin или nums[mid - 1] != target, тогда мы возвращаем mid как первое вхождение цели. В противном случае мы обновляем end = mid - 1.
Если isFirst false — это означает, что мы пытаемся найти последнее вхождение элемента. Если mid == end или nums[mid + 1] != target, тогда мы возвращаем mid как последнее вхождение цели. В противном случае мы обновляем begin = mid + 1.
3️⃣Если nums[mid] > target — мы обновляем end = mid - 1, так как мы должны отбросить правую сторону массива, поскольку средний элемент больше цели.
Если nums[mid] < target — мы обновляем begin = mid + 1, так как мы должны отбросить левую сторону массива, поскольку средний элемент меньше цели.
В конце нашей функции мы возвращаем значение -1, что указывает на то, что цель не найдена в массиве.
В основной функции searchRange мы сначала вызываем findBound с isFirst, установленным в true. Если это значение равно -1, мы можем просто вернуть [-1, -1]. В противном случае мы вызываем findBound с isFirst, установленным в false, чтобы получить последнее вхождение, а затем возвращаем результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив целых чисел nums, отсортированный в неубывающем порядке, найдите начальную и конечную позицию заданного целевого значения.
Если целевое значение не найдено в массиве, верните [-1, -1].
Вы должны написать алгоритм со временной сложностью O(log n).
Пример:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
👨💻 Алгоритм:
1️⃣Определите функцию под названием findBound, которая принимает три аргумента: массив, целевое значение для поиска и булевое значение isFirst, указывающее, ищем ли мы первое или последнее вхождение цели.
Мы используем 2 переменные для отслеживания подмассива, который мы сканируем. Назовем их begin и end. Изначально begin устанавливается в 0, а end — в последний индекс массива.
2️⃣Мы итерируем, пока begin не станет больше, чем end.
На каждом шаге мы вычисляем средний элемент mid = (begin + end) / 2. Мы используем значение среднего элемента, чтобы решить, какую половину массива нам нужно искать.
Если nums[mid] == target:
Если isFirst true — это означает, что мы пытаемся найти первое вхождение элемента. Если mid == begin или nums[mid - 1] != target, тогда мы возвращаем mid как первое вхождение цели. В противном случае мы обновляем end = mid - 1.
Если isFirst false — это означает, что мы пытаемся найти последнее вхождение элемента. Если mid == end или nums[mid + 1] != target, тогда мы возвращаем mid как последнее вхождение цели. В противном случае мы обновляем begin = mid + 1.
3️⃣Если nums[mid] > target — мы обновляем end = mid - 1, так как мы должны отбросить правую сторону массива, поскольку средний элемент больше цели.
Если nums[mid] < target — мы обновляем begin = mid + 1, так как мы должны отбросить левую сторону массива, поскольку средний элемент меньше цели.
В конце нашей функции мы возвращаем значение -1, что указывает на то, что цель не найдена в массиве.
В основной функции searchRange мы сначала вызываем findBound с isFirst, установленным в true. Если это значение равно -1, мы можем просто вернуть [-1, -1]. В противном случае мы вызываем findBound с isFirst, установленным в false, чтобы получить последнее вхождение, а затем возвращаем результат.
😎 Решение:
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
lower_bound = self.findBound(nums, target, True)
if lower_bound == -1:
return [-1, -1]
upper_bound = self.findBound(nums, target, False)
return [lower_bound, upper_bound]
def findBound(self, nums: List[int], target: int, isFirst: bool) -> int:
N = len(nums)
begin, end = 0, N - 1
while begin <= end:
mid = int((begin + end) / 2)
if nums[mid] == target:
if isFirst:
if mid == begin or nums[mid - 1] < target:
return mid
end = mid - 1
else:
if mid == end or nums[mid + 1] > target:
return mid
begin = mid + 1
elif nums[mid] > target:
end = mid - 1
else:
begin = mid + 1
return -1
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1464. Maximum Product of Two Elements in an Array
Сложность: easy
Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте biggest = 0 и secondBiggest = 0.
2⃣Итерируйте по каждому элементу массива nums:
Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент.
Иначе обновите secondBiggest, если текущий элемент больше secondBiggest.
3⃣Верните (biggest - 1) * (secondBiggest - 1).
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).
Пример:
Input: nums = [3,4,5,2]
Output: 12
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value,
that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.
👨💻 Алгоритм:
1⃣Инициализируйте biggest = 0 и secondBiggest = 0.
2⃣Итерируйте по каждому элементу массива nums:
Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент.
Иначе обновите secondBiggest, если текущий элемент больше secondBiggest.
3⃣Верните (biggest - 1) * (secondBiggest - 1).
😎 Решение:
class Solution:
def maxProduct(self, nums: List[int]) -> int:
biggest = 0
secondBiggest = 0
for num in nums:
if num > biggest:
secondBiggest = biggest
biggest = num
elif num > secondBiggest:
secondBiggest = num
return (biggest - 1) * (secondBiggest - 1)
Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: 923. 3Sum With Multiplicity
Сложность: medium
Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
Пример:
👨💻 Алгоритм:
1⃣Отсортировать массив arr.
2⃣Инициализировать счетчик для количества кортежей.
Пройти по массиву тремя указателями i, j, и k:
Для каждого i, установить j на i + 1, и k на конец массива.
Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target.
3⃣Вернуть результат по модулю 10^9 + 7.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
Пример:
Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
👨💻 Алгоритм:
1⃣Отсортировать массив arr.
2⃣Инициализировать счетчик для количества кортежей.
Пройти по массиву тремя указателями i, j, и k:
Для каждого i, установить j на i + 1, и k на конец массива.
Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target.
3⃣Вернуть результат по модулю 10^9 + 7.
😎 Решение:
def threeSumMulti(arr, target):
arr.sort()
MOD = 10**9 + 7
count = 0
for i in range(len(arr)):
j, k = i + 1, len(arr) - 1
while j < k:
sum_ = arr[i] + arr[j] + arr[k]
if sum_ == target:
if arr[j] == arr[k]:
count += (k - j + 1) * (k - j) // 2
break
else:
left, right = 1, 1
while j + 1 < k and arr[j] == arr[j + 1]:
left += 1
j += 1
while k - 1 > j and arr[k] == arr[k - 1]:
right += 1
k -= 1
count += left * right
j += 1
k -= 1
elif sum_ < target:
j += 1
else:
k -= 1
return count % MOD
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1382. Balance a Binary Search Tree
Сложность: medium
Дан корень бинарного дерева поиска. Верните сбалансированное бинарное дерево поиска с теми же значениями узлов. Если существует более одного ответа, верните любой из них.
Бинарное дерево поиска считается сбалансированным, если глубина двух поддеревьев каждого узла никогда не отличается более чем на 1.
Пример:
👨💻 Алгоритм:
1⃣Инициализация. Создайте пустой список inorder для хранения значений узлов после обхода в порядке возрастания.
2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.
3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан корень бинарного дерева поиска. Верните сбалансированное бинарное дерево поиска с теми же значениями узлов. Если существует более одного ответа, верните любой из них.
Бинарное дерево поиска считается сбалансированным, если глубина двух поддеревьев каждого узла никогда не отличается более чем на 1.
Пример:
Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.
👨💻 Алгоритм:
1⃣Инициализация. Создайте пустой список inorder для хранения значений узлов после обхода в порядке возрастания.
2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.
3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.
😎 Решение:
class Solution:
def balanceBST(self, root: TreeNode) -> TreeNode:
if not root:
return None
vineHead = TreeNode(0)
vineHead.right = root
current = vineHead
while current.right:
if current.right.left:
self.rightRotate(current, current.right)
else:
current = current.right
nodeCount = 0
current = vineHead.right
while current:
nodeCount += 1
current = current.right
m = 2 ** (nodeCount + 1).bit_length() - 1
self.makeRotations(vineHead, nodeCount - m)
while m > 1:
m //= 2
self.makeRotations(vineHead, m)
return vineHead.right
def rightRotate(self, parent, node):
tmp = node.left
node.left = tmp.right
tmp.right = node
parent.right = tmp
def leftRotate(self, parent, node):
tmp = node.right
node.right = tmp.left
tmp.left = node
parent.right = tmp
def makeRotations(self, vineHead, count):
current = vineHead
for _ in range(count):
tmp = current.right
self.leftRotate(current, tmp)
current = current.right
Ставь 👍 и забирай 📚 Базу знаний
Задача: 973. K Closest Points to Origin
Сложность: medium
Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0).
Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)).
Вы можете вернуть ответ в любом порядке. Гарантируется, что ответ будет уникальным (за исключением порядка).
Пример:
👨💻 Алгоритм:
1⃣Отсортируйте массив с помощью функции компаратора.
2⃣Функция компаратора будет использовать уравнение квадратного евклидова расстояния для сравнения двух точек.
3⃣Верните первые k элементов массива.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0).
Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)).
Вы можете вернуть ответ в любом порядке. Гарантируется, что ответ будет уникальным (за исключением порядка).
Пример:
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
👨💻 Алгоритм:
1⃣Отсортируйте массив с помощью функции компаратора.
2⃣Функция компаратора будет использовать уравнение квадратного евклидова расстояния для сравнения двух точек.
3⃣Верните первые k элементов массива.
😎 Решение:
class Solution:
def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
points.sort(key=self.squaredDistance)
return points[:k]
def squaredDistance(self, point: list[int]) -> int:
return point[0] ** 2 + point[1] ** 2
Ставь 👍 и забирай 📚 Базу знаний
Задача: 990. Satisfiability of Equality Equations
Сложность: medium
Дан массив строк equations, представляющий отношения между переменными, где каждая строка equations[i] имеет длину 4 и принимает одну из двух форм: "xi==yi" или "xi!=yi". Здесь xi и yi - это строчные буквы (не обязательно разные), представляющие имена переменных из одной буквы.
Верните true, если возможно назначить целые числа именам переменных таким образом, чтобы удовлетворить всем заданным уравнениям, или false в противном случае.
Пример:
👨💻 Алгоритм:
1⃣Создание графа для уравнений "==":
Создайте структуру данных для объединения (Union-Find) для обработки уравнений равенства.
Пройдите через массив equations и для каждого уравнения типа "xi==yi" объедините соответствующие переменные.
2⃣Проверка уравнений "!=":
Пройдите через массив equations и для каждого уравнения типа "xi!=yi" проверьте, принадлежат ли переменные к одной и той же группе в структуре объединения. Если принадлежат, верните false.
3⃣Возврат результата:
Если после проверки всех уравнений "xi!=yi" не было обнаружено противоречий, верните true.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив строк equations, представляющий отношения между переменными, где каждая строка equations[i] имеет длину 4 и принимает одну из двух форм: "xi==yi" или "xi!=yi". Здесь xi и yi - это строчные буквы (не обязательно разные), представляющие имена переменных из одной буквы.
Верните true, если возможно назначить целые числа именам переменных таким образом, чтобы удовлетворить всем заданным уравнениям, или false в противном случае.
Пример:
Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.
👨💻 Алгоритм:
1⃣Создание графа для уравнений "==":
Создайте структуру данных для объединения (Union-Find) для обработки уравнений равенства.
Пройдите через массив equations и для каждого уравнения типа "xi==yi" объедините соответствующие переменные.
2⃣Проверка уравнений "!=":
Пройдите через массив equations и для каждого уравнения типа "xi!=yi" проверьте, принадлежат ли переменные к одной и той же группе в структуре объединения. Если принадлежат, верните false.
3⃣Возврат результата:
Если после проверки всех уравнений "xi!=yi" не было обнаружено противоречий, верните true.
😎 Решение:
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
uf = UnionFind(26)
for eq in equations:
if eq[1] == '=':
x = ord(eq[0]) - ord('a')
y = ord(eq[3]) - ord('a')
uf.union(x, y)
for eq in equations:
if eq[1] == '!':
x = ord(eq[0]) - ord('a')
y = ord(eq[3]) - ord('a')
if uf.connected(x, y):
return False
return True
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
self.parent[rootX] = rootY
def connected(self, x, y):
return self.find(x) == self.find(y)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 543. Diameter of Binary Tree
Сложность: easy
Учитывая корень бинарного дерева, вернуть длину диаметра дерева.
Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.
Длина пути между двумя узлами представлена числом ребер между ними.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS.
2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1.
3⃣Вызвать longestPath с root.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Учитывая корень бинарного дерева, вернуть длину диаметра дерева.
Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.
Длина пути между двумя узлами представлена числом ребер между ними.
Пример:
Input: root = [1,2]
Output: 1
👨💻 Алгоритм:
1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS.
2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1.
3⃣Вызвать longestPath с root.
😎 Решение:
class Solution:
def __init__(self):
self.diameter = 0
def diameterOfBinaryTree(self, root):
self.diameter = 0
self.longestPath(root)
return self.diameter
def longestPath(self, node):
if not node:
return 0
leftPath = self.longestPath(node.left)
rightPath = self.longestPath(node.right)
self.diameter = max(self.diameter, leftPath + rightPath)
return max(leftPath, rightPath) + 1
Ставь 👍 и забирай 📚 Базу знаний