Задача: 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
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1137. N-th Tribonacci Number
Сложность: easy
Трибоначчи последовательность Tn определяется следующим образом:
T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0.
Дано n, вернуть значение Tn.
Пример:
👨💻 Алгоритм:
1⃣Если n < 3, вернуть значение n-го терма, как указано в описании задачи.
2⃣Инициализировать a, b и c как базовые случаи. Установить a = 0, b = 1, c = 1.
3⃣Для следующих n - 2 шагов обновлять a, b, c следующим образом: a = b, b = c, c = a + b + c. Вернуть c.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Трибоначчи последовательность Tn определяется следующим образом:
T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0.
Дано n, вернуть значение Tn.
Пример:
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
👨💻 Алгоритм:
1⃣Если n < 3, вернуть значение n-го терма, как указано в описании задачи.
2⃣Инициализировать a, b и c как базовые случаи. Установить a = 0, b = 1, c = 1.
3⃣Для следующих n - 2 шагов обновлять a, b, c следующим образом: a = b, b = c, c = a + b + c. Вернуть c.
😎 Решение:
class Solution:
def tribonacci(self, n: int) -> int:
if n < 3:
return 1 if n > 0 else 0
a, b, c = 0, 1, 1
for _ in range(n - 2):
a, b, c = b, c, a + b + c
return c
Ставь 👍 и забирай 📚 Базу знаний
Задача: 26. Remove Duplicates from Sorted Array
Сложность: easy
Учитывая целочисленный массив чисел, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов в числах.
Считайте, что количество уникальных элементов чисел равно k. Чтобы вас приняли, вам нужно сделать следующее:
- Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, как и размер nums.
- Вернуть k.
Пример:
👨💻 Алгоритм:
1️⃣Используем два указателя: один для уникальных элементов, другой для прохода по массиву.
2️⃣Перебираем массив, добавляя уникальные элементы на место.
3️⃣Возвращаем количество уникальных элементов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Учитывая целочисленный массив чисел, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов в числах.
Считайте, что количество уникальных элементов чисел равно k. Чтобы вас приняли, вам нужно сделать следующее:
- Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, как и размер nums.
- Вернуть k.
Пример:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
👨💻 Алгоритм:
1️⃣Используем два указателя: один для уникальных элементов, другой для прохода по массиву.
2️⃣Перебираем массив, добавляя уникальные элементы на место.
3️⃣Возвращаем количество уникальных элементов.
😎 Решение:
from typing import List
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
while i < len(nums) - 1:
if nums[i] == nums[i + 1]:
nums.pop(i + 1)
else:
i += 1
return len(nums)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 934. Shortest Bridge
Сложность: medium
Вам дана двоичная матричная сетка n x n, где 1 обозначает сушу, а 0 - воду. Остров - это 4-направленно связанная группа из 1, не соединенная ни с одной другой 1. В сетке ровно два острова. Вы можете поменять 0 на 1, чтобы соединить два острова в один. Верните наименьшее количество 0, которое нужно перевернуть, чтобы соединить два острова.
Пример:
👨💻 Алгоритм:
1⃣Найти все клетки, принадлежащие первому острову, используя DFS/BFS, и добавить их в очередь для последующего расширения.
2⃣Использовать BFS для расширения из каждой клетки первого острова, чтобы найти кратчайший путь к клетке второго острова.
3⃣Вернуть длину кратчайшего пути.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дана двоичная матричная сетка n x n, где 1 обозначает сушу, а 0 - воду. Остров - это 4-направленно связанная группа из 1, не соединенная ни с одной другой 1. В сетке ровно два острова. Вы можете поменять 0 на 1, чтобы соединить два острова в один. Верните наименьшее количество 0, которое нужно перевернуть, чтобы соединить два острова.
Пример:
Input: grid = [[0,1],[1,0]]
Output: 1
👨💻 Алгоритм:
1⃣Найти все клетки, принадлежащие первому острову, используя DFS/BFS, и добавить их в очередь для последующего расширения.
2⃣Использовать BFS для расширения из каждой клетки первого острова, чтобы найти кратчайший путь к клетке второго острова.
3⃣Вернуть длину кратчайшего пути.
😎 Решение:
from collections import deque
def shortestBridge(grid):
n = len(grid)
def neighbors(x, y):
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
if 0 <= x + dx < n and 0 <= y + dy < n:
yield x + dx, y + dy
def bfs(queue):
visited = set(queue)
steps = 0
while queue:
new_queue = []
for x, y in queue:
for nx, ny in neighbors(x, y):
if (nx, ny) not in visited:
if grid[nx][ny] == 1:
return steps
visited.add((nx, ny))
new_queue.append((nx, ny))
queue = new_queue
steps += 1
def find_first_island():
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
queue = deque([(i, j)])
grid[i][j] = -1
island = [(i, j)]
while queue:
x, y = queue.popleft()
for nx, ny in neighbors(x, y):
if grid[nx][ny] == 1:
grid[nx][ny] = -1
queue.append((nx, ny))
island.append((nx, ny))
return island
island = find_first_island()
return bfs(island)
Ставь 👍 и забирай 📚 Базу знаний