Задача: 418. Sentence Screen Fitting
Сложность: medium
Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом.
Пример:
👨💻 Алгоритм:
1⃣Преобразуйте предложение в единую строку с пробелами между словами и пробелом в конце.
2⃣Инициализируйте переменную для отслеживания текущей позиции в строке предложения. Для каждой строки экрана добавляйте количество символов, равное числу столбцов.
3⃣Если следующая позиция является пробелом, увеличивайте счетчик. Если нет, уменьшайте счетчик, пока не найдете пробел, чтобы избежать разрыва слова.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом.
Пример:
Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1
👨💻 Алгоритм:
1⃣Преобразуйте предложение в единую строку с пробелами между словами и пробелом в конце.
2⃣Инициализируйте переменную для отслеживания текущей позиции в строке предложения. Для каждой строки экрана добавляйте количество символов, равное числу столбцов.
3⃣Если следующая позиция является пробелом, увеличивайте счетчик. Если нет, уменьшайте счетчик, пока не найдете пробел, чтобы избежать разрыва слова.
😎 Решение:
def wordsTyping(sentence, rows, cols):
sentence_str = " ".join(sentence) + " "
length = len(sentence_str)
pos = 0
for _ in range(rows):
pos += cols
if sentence_str[pos % length] == " ":
pos += 1
else:
while pos > 0 and sentence_str[(pos - 1) % length] != " ":
pos -= 1
return pos // length
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1057. Campus Bikes
Сложность: medium
В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
👨💻 Алгоритм:
1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.
2⃣Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда.
Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы.
3⃣Заполни и верни массив назначений.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]
👨💻 Алгоритм:
1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.
2⃣Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда.
Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы.
3⃣Заполни и верни массив назначений.
😎 Решение:
def assignBikes(workers, bikes):
pairs = []
for i, (wx, wy) in enumerate(workers):
for j, (bx, by) in enumerate(bikes):
distance = abs(wx - bx) + abs(wy - by)
pairs.append((distance, i, j))
pairs.sort()
result = [-1] * len(workers)
bike_taken = [False] * len(bikes)
worker_assigned = [False] * len(workers)
for distance, worker_idx, bike_idx in pairs:
if not worker_assigned[worker_idx] and not bike_taken[bike_idx]:
result[worker_idx] = bike_idx
bike_taken[bike_idx] = True
worker_assigned[worker_idx] = True
return result
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1248. Count Number of Nice Subarrays
Сложность: medium
Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.
Пример:
👨💻 Алгоритм:
1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.
2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц.
3⃣Подсчитайте количество таких подмассивов и верните этот результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.
Пример:
Input: arr = [1,2]
Output: 2
👨💻 Алгоритм:
1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.
2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц.
3⃣Подсчитайте количество таких подмассивов и верните этот результат.
😎 Решение:
def numberOfSubarrays(nums, k):
def atMost(nums, k):
count = 0
left = 0
res = 0
for right in range(len(nums)):
if nums[right] % 2 == 1:
count += 1
while count > k:
if nums[left] % 2 == 1:
count -= 1
left += 1
res += right - left + 1
return res
return atMost(nums, k) - atMost(nums, k - 1)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 867. Transpose Matrix
Сложность: easy
Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.
Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк.
2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c].
3⃣Верните матрицу ans.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.
Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.
Пример:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]
👨💻 Алгоритм:
1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк.
2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c].
3⃣Верните матрицу ans.
😎 Решение:
class Solution:
def transpose(self, A):
return [[A[r][c] for r in range(len(A))] for c in range(len(A[0]))]
Ставь 👍 и забирай 📚 Базу знаний
💊2
Задача: 968. Binary Tree Cameras
Сложность: hard
Вам дан корень бинарного дерева. Мы устанавливаем камеры на узлы дерева, где каждая камера на узле может наблюдать за своим родителем, собой и своими непосредственными детьми.
Верните минимальное количество камер, необходимых для наблюдения за всеми узлами дерева.
Пример:
👨💻 Алгоритм:
1⃣Рекурсивное решение (solve):
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.
2⃣Рассчёт состояний:
Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1.
Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2.
Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии.
3⃣Минимальное количество камер:
Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Вам дан корень бинарного дерева. Мы устанавливаем камеры на узлы дерева, где каждая камера на узле может наблюдать за своим родителем, собой и своими непосредственными детьми.
Верните минимальное количество камер, необходимых для наблюдения за всеми узлами дерева.
Пример:
Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.
👨💻 Алгоритм:
1⃣Рекурсивное решение (solve):
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.
2⃣Рассчёт состояний:
Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1.
Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2.
Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии.
3⃣Минимальное количество камер:
Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2.
😎 Решение:
class Solution:
def minCameraCover(self, root: TreeNode) -> int:
def solve(node):
if not node:
return 0, 0, float('inf')
L = solve(node.left)
R = solve(node.right)
mL12 = min(L[1], L[2])
mR12 = min(R[1], R[2])
d0 = L[1] + R[1]
d1 = min(L[2] + mR12, R[2] + mL12)
d2 = 1 + min(L[0], mL12) + min(R[0], mR12)
return d0, d1, d2
return min(solve(root)[1:])
Ставь 👍 и забирай 📚 Базу знаний
🔥1
Задача: 300. Longest Increasing Subsequence
Сложность: medium
Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.
2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).
3⃣Верните максимальное значение из dp.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.
Пример:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
👨💻 Алгоритм:
1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.
2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).
3⃣Верните максимальное значение из dp.
😎 Решение:
class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1209. Remove All Adjacent Duplicates in String II
Сложность: medium
Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе.
Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать.
Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален.
Пример:
👨💻 Алгоритм:
1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов.
2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.
3⃣Вернуть первые j символов строки.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе.
Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать.
Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален.
Пример:
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation:
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"
👨💻 Алгоритм:
1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов.
2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.
3⃣Вернуть первые j символов строки.
😎 Решение:
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
counts = []
sa = list(s)
j = 0
for i in range(len(sa)):
sa[j] = sa[i]
if j == 0 or sa[j] != sa[j - 1]:
counts.append(1)
else:
incremented = counts.pop() + 1
if incremented == k:
j -= k
else:
counts.append(incremented)
j += 1
return "".join(sa[:j])
Ставь 👍 и забирай 📚 Базу знаний
Задача: 827. Making A Large Island
Сложность: hard
Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.
Верните размер самого большого острова в grid после выполнения этой операции.
Остров — это группа 1, соединенных в 4 направлениях.
Пример:
👨💻 Алгоритм:
1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер.
2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1.
3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.
Верните размер самого большого острова в grid после выполнения этой операции.
Остров — это группа 1, соединенных в 4 направлениях.
Пример:
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
👨💻 Алгоритм:
1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер.
2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1.
3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.
😎 Решение:
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
def dfs(r, c, index):
ans = 1
grid[r][c] = index
for nr, nc in neighbors(r, c):
if grid[nr][nc] == 1:
grid[nr][nc] = index
ans += dfs(nr, nc, index)
return ans
def neighbors(r, c):
for dr, dc in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N:
yield nr, nc
N = len(grid)
index = 2
area = [0] * (N * N + 2)
for r in range(N):
for c in range(N):
if grid[r][c] == 1:
area[index] = dfs(r, c, index)
index += 1
ans = max(area)
for r in range(N):
for c in range(N):
if grid[r][c] == 0:
seen = {grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1}
ans = max(a
Ставь 👍 и забирай 📚 Базу знаний
Задача: 987. Vertical Order Traversal of a Binary Tree
Сложность: medium
Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.
Верните пересечение этих двух списков интервалов.
Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.
Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].
Пример:
👨💻 Алгоритм:
1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).
2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).
3⃣Возврат результата:
Отсортировать ключи словаря по col и затем по row.
Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.
Верните пересечение этих двух списков интервалов.
Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.
Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].
Пример:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
👨💻 Алгоритм:
1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).
2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).
3⃣Возврат результата:
Отсортировать ключи словаря по col и затем по row.
Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список.
😎 Решение:
from collections import defaultdict, deque
class Solution:
def verticalTraversal(self, root):
col_table = defaultdict(list)
queue = deque([(root, 0, 0)])
while queue:
node, row, col = queue.popleft()
if node:
col_table[col].append((row, node.val))
queue.append((node.left, row + 1, col - 1))
queue.append((node.right, row + 1, col + 1))
result = []
for col in sorted(col_table.keys()):
col_table[col].sort()
result.append([val for row, val in col_table[col]])
return result
Ставь 👍 и забирай 📚 Базу знаний
Задача: 971. Flip Binary Tree To Match Preorder Traversal
Сложность: medium
Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.
Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:
Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.
Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].
Пример:
👨💻 Алгоритм:
1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1].
2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка.
3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.
Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:
Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.
Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].
Пример:
Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.
👨💻 Алгоритм:
1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1].
2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка.
3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage.
😎 Решение:
class Solution:
def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:
self.flipped = []
self.index = 0
self.voyage = voyage
self.dfs(root)
if self.flipped and self.flipped[0] == -1:
return [-1]
return self.flipped
def dfs(self, node):
if node:
if node.val != self.voyage[self.index]:
self.flipped = [-1]
return
self.index += 1
if self.index < len(self.voyage) and node.left and node.left.val != self.voyage[self.index]:
self.flipped.append(node.val)
self.dfs(node.right)
self.dfs(node.left)
else:
self.dfs(node.left)
self.dfs(node.right)
Ставь 👍 и забирай 📚 Базу знаний