Python | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
إظهار المزيد
8 922
المشتركون
-524 ساعات
-477 أيام
-12930 أيام
أرشيف المشاركات
8 922
#medium
Задача: 314. Binary Tree Vertical Order Traversal
Дан корень бинарного дерева, верните вертикальный порядок обхода значений его узлов (т.е. сверху вниз, столбец за столбцом).
Если два узла находятся в одной строке и столбце, порядок должен быть слева направо.
Пример:
Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]]👨💻 Алгоритм: 1️⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов. 2️⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь. 3️⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам. 😎 Решение:
from collections import defaultdict
class Solution:
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
columnTable = defaultdict(list)
queue = deque([(root, 0)])
while queue:
node, column = queue.popleft()
if node is not None:
columnTable[column].append(node.val)
queue.append((node.left, column - 1))
queue.append((node.right, column + 1))
return [columnTable[x] for x in sorted(columnTable.keys())]8 922
#easy
Задача: 219. Contains Duplicate II
Дан массив целых чисел nums и целое число k. Верните true, если в массиве существуют два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k.
Пример:
Input: nums = [1,2,3,1,2,3], k = 2 Output: false👨💻 Алгоритм: 1️⃣ Создайте пустое множество set. 2️⃣ Пройдитесь по массиву nums: Если текущий элемент уже есть в множестве, верните true. Добавьте текущий элемент в множество. Если размер множества больше k, удалите элемент, который был добавлен k шагов назад. 3️⃣ Если не найдены дублирующиеся элементы на расстоянии k или менее, верните false. 😎 Решение:
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
seen = set()
for i, num in enumerate(nums):
if num in seen:
return True
seen.add(num)
if len(seen) > k:
seen.remove(nums[i - k])
return False8 922
#medium
Задача: 276. Paint Fence
Вы красите забор из n столбцов, используя k различных цветов. Вы должны красить столбы, следуя этим правилам:
Каждый столб должен быть окрашен в один цвет.
Не может быть трех или более подряд идущих столбцов одного цвета.
Учитывая два целых числа n и k, верните количество способов покрасить забор.
Пример:
Input: n = 3, k = 2 Output: 6 Explanation: All the possibilities are shown. Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.👨💻 Алгоритм: 1️⃣Инициализация и определение вспомогательной функции: Определить хеш-таблицу memo, где memo[i] представляет количество способов покрасить i столбцов. Определить функцию totalWays, которая будет определять количество способов покрасить i столбцов. 2️⃣Реализация базы и проверка кэша: В функции totalWays проверить базовые случаи: вернуть k, если i == 1, и вернуть k * k, если i == 2. Проверить, рассчитан ли аргумент i и сохранен ли в memo. Если да, вернуть memo[i]. 3️⃣Расчет с использованием рекуррентного соотношения: В противном случае использовать рекуррентное соотношение для вычисления memo[i], сохранить результат в memo[i] и вернуть его. Вызвать и вернуть totalWays(n). 😎 Решение:
class Solution:
def numWays(self, n: int, k: int) -> int:
if n == 1:
return k
twoPostsBack = k
onePostBack = k * k
for i in range(3, n + 1):
curr = (k - 1) * (onePostBack + twoPostsBack)
twoPostsBack = onePostBack
onePostBack = curr
return onePostBack8 922
#hard
Задача: 218. The Skyline Problem
Горизонт города — это внешний контур силуэта, образованного всеми зданиями в этом городе, когда они видны издалека. Учитывая расположения и высоты всех зданий, верните горизонт, образованный этими зданиями в совокупности.
Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:
lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.
Пример:
Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]] Explanation: Figure A shows the buildings of the input. Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.👨💻 Алгоритм: 1️⃣ Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights. 2️⃣ Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex). 3️⃣ Пройдитесь по обновленным высотам и добавьте все позиции, где высота меняется, в answer в качестве ключевых точек горизонта. Верните answer как результат. 😎 Решение:
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
positions = sorted(list(set([x for building in buildings for x in building[:2]])))
edge_index_map = {x : i for i, x in enumerate(positions)}
heights = [0] * len(positions)
for left, right, height in buildings:
left_idx = edge_index_map[left]
right_idx = edge_index_map[right]
for i in range(left_idx, right_idx):
heights[i] = max(heights[i], height)
answer = []
for i in range(len(heights)):
curr_height = heights[i]
curr_x = positions[i]
if not answer or answer[-1][1] != curr_height:
answer.append([curr_x, curr_height])
return answer8 922
#easy
Задача: 217. Contains Duplicate
Дан массив целых чисел nums. Верните true, если любое значение появляется в массиве хотя бы дважды, и верните false, если каждый элемент уникален.
Пример:
Input: nums = [1,2,3,4] Output: false👨💻 Алгоритм: 1️⃣ Отсортируйте массив nums по возрастанию. 2️⃣ Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим. 3️⃣ Если любое число совпадает с следующим, верните true. Если цикл завершится без совпадений, верните false. 😎 Решение:
def containsDuplicate(nums):
nums.sort()
for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
return True
return False8 922
#medium
Задача: 275. H-Index II
Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.
Пример:
Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.👨💻 Алгоритм: 1️⃣Найти середину массива: Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n]. 2️⃣Сравнить количество статей с цитированиями больше или равными citations[mid]: Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть. Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n]. Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1]. 3️⃣Возвращение результата: Продолжать процесс, пока не будет найден h-индекс. Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid]. 😎 Решение:
class Solution:
def hIndex(self, citations: List[int]) -> int:
n = len(citations)
left, right = 0, n - 1
while left <= right:
mid = left + (right - left) // 2
if citations[mid] == n - mid:
return n - mid
elif citations[mid] < n - mid:
left = mid + 1
else:
right = mid - 1
return n - left8 922
#medium
Задача: 274. H-Index
Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Пример:
Input: citations = [3,0,6,1,5] Output: 3 Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.👨💻 Алгоритм: 1️⃣Отсортировать массив цитирований по убыванию: Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива. 2️⃣Найти наибольшее значение i, для которого citations[i] > i: Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i. Это значение будет индексом, при котором количество цитирований статьи больше индекса. 3️⃣Рассчитать h-индекс: h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге. 😎 Решение:
class Solution:
def hIndex(self, citations: List[int]) -> int:
n = len(citations)
papers = [0] * (n + 1)
for c in citations:
papers[min(n, c)] += 1
k = n
s = papers[n]
while k > s:
k -= 1
s += papers[k]
return k8 922
#medium
Задача: 216. Combination Sum III
Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:
Используются только числа от 1 до 9.
Каждое число используется не более одного раза.
Верните список всех возможных допустимых комбинаций. Список не должен содержать одинаковые комбинации, и комбинации могут возвращаться в любом порядке.
Пример:
Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.👨💻 Алгоритм: 1️⃣ Инициализация и запуск рекурсивной функции: Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов. Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов. Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов. 2️⃣ Рекурсивная обработка: В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов. Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки. Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата. 3️⃣ Возвращение результатов: По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций. 😎 Решение:
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
results = []
def backtrack(remain, comb, next_start):
if remain == 0 and len(comb) == k:
results.append(list(comb))
return
elif remain < 0 or len(comb) == k:
return
for i in range(next_start, 9):
comb.append(i + 1)
backtrack(remain - i - 1, comb, i + 1)
comb.pop()
backtrack(n, [], 0)
return results8 922
#medium
Задача: 215. Kth Largest Element in an Array
Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.
Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.
Пример:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4👨💻 Алгоритм: 1️⃣ Отсортируйте массив в порядке убывания: Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее. 2️⃣ Найдите k-й по величине элемент: После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0). 3️⃣ Верните результат: Возвратите найденное значение как результат. 😎 Решение:
class Solution:
def findKthLargest(self, nums, k):
nums.sort(reverse=True)
return nums[k - 1]8 922
#hard
Задача: 273. Integer to English Words
Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.
Пример:
Input: num = 123 Output: "One Hundred Twenty Three"👨💻 Алгоритм: 1️⃣Обработка чисел до 20 и кратных 10 до 90: Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90. Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление. 2️⃣Обработка сотен, тысяч, миллионов и миллиардов: Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды). Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999. 3️⃣Формирование окончательного результата: Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды). Соединить все части в одну строку, удалив лишние пробелы. 😎 Решение:
class Solution:
def numberToWords(self, num: int) -> str:
if num == 0:
return "Zero"
def helper(n):
if n == 0:
return ""
elif n < 20:
return below_twenty[n] + " "
elif n < 100:
return tens[n // 10] + " " + helper(n % 10)
else:
return below_twenty[n // 100] + " Hundred " + helper(n % 100)
below_twenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
thousands = ["", "Thousand", "Million", "Billion"]
result = ""
i = 0
while num > 0:
if num % 1000 != 0:
result = helper(num % 1000) + thousands[i] + " " + result
num //= 1000
i += 1
return result.strip()8 922
#hard
Задача: 214. Shortest Palindrome
Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки.
Верните самый короткий палиндром, который можно получить, выполняя это преобразование.
Пример:
Input: s = "aacecaaa" Output: "aaacecaaa"👨💻 Алгоритм: 1️⃣Создайте обратную строку от исходной строки s, назовем ее rev. Она будет использована для сравнения, чтобы найти наибольший палиндромный сегмент с начала строки. 2️⃣ Итеративно перемещайтесь по переменной i от 0 до size(s) - 1: Если s[0:n−i] == rev[i:] (т.е. подстрока s от 0 до n−i равна подстроке rev от i до конца строки). Это по сути означает, что подстрока от 0 до n−i является палиндромом, так как rev является обратной строкой s. 3️⃣ Так как мы находим сначала большие палиндромы, можем вернуть обратную строку от наибольшего палиндрома + s, как только найдем его. 😎 Решение:
class Solution:
def shortestPalindrome(self, s: str) -> str:
n = len(s)
rev = s[::-1]
for i in range(n):
if s[: n - i] == rev[i:]:
return rev[:i] + s
return ""8 922
#hard
Задача: 272. Closest Binary Search Tree Value II
Дано корень бинарного дерева поиска, целевое значение и целое число k. Верните k значений в дереве, которые ближе всего к целевому значению. Вы можете вернуть ответ в любом порядке.
Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2 Output: [4,3]👨💻 Алгоритм: 1️⃣Выполнить обход дерева в глубину (DFS) и собрать все значения в массив: Пройти по дереву в глубину, добавляя каждое значение узла в массив. 2️⃣Отсортировать массив по расстоянию от целевого значения: Использовать пользовательский компаратор, чтобы отсортировать массив по абсолютному значению разности между элементом массива и целевым значением. 3️⃣Вернуть первые k значений из отсортированного массива: Извлечь первые k элементов из отсортированного массива и вернуть их. 😎 Решение:
class Solution:
def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
arr = []
self.dfs(root, arr)
arr.sort(key=lambda x: abs(x - target))
return arr[:k]
def dfs(self, node: TreeNode, arr: List[int]):
if not node:
return
arr.append(node.val)
self.dfs(node.left, arr)
self.dfs(node.right, arr)
8 922
#easy
Задача: 270. Closest Binary Search Tree Value
Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286 Output: 4👨💻 Алгоритм: 1️⃣Построить массив с помощью inorder обхода: Выполнить inorder обход дерева и собрать элементы в отсортированный массив. 2️⃣Найти ближайший элемент: Пройти по массиву и определить элемент, наиболее близкий к целевому значению. 3️⃣Выбрать наименьший из ближайших элементов: Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них. 😎 Решение:
class Solution:
def closestValue(self, root: TreeNode, target: float) -> int:
closest = root.val
while root:
closest = min(root.val, closest, key=lambda x: (abs(target - x), x))
root = root.left if target < root.val else root.right
return closest8 922
#hard
Задача: 269. Alien Dictionary
Есть новый инопланетный язык, который использует английский алфавит. Однако порядок букв в нем неизвестен.
Вам дан список строк words из словаря инопланетного языка. Утверждается, что строки в words отсортированы лексикографически по правилам этого нового языка.
Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "".
В противном случае верните строку из уникальных букв нового инопланетного языка, отсортированных в лексикографическом порядке по правилам нового языка. Если существует несколько решений, верните любое из них.
Пример:
Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"👨💻 Алгоритм: 1️⃣Извлечение отношений порядка и создание списков смежности: Извлечь отношения порядка между буквами из слов. Вставить их в список смежности, обрабатывая случаи, когда одно слово является префиксом другого. 2️⃣Подсчет числа входящих ребер: Подсчитать количество входящих ребер (in-degree) для каждой буквы. Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы. 3️⃣Обход в ширину (BFS): Инициализировать очередь буквами с нулевым in-degree. Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым. Продолжать до тех пор, пока очередь не станет пустой. Проверить наличие циклов и вернуть результат. 😎 Решение:
from collections import defaultdict, Counter, deque
def alienOrder(self, words: List[str]) -> str:
adj_list = defaultdict(set)
in_degree = Counter({c: 0 for word in words for c in word})
for first_word, second_word in zip(words, words[1:]):
for c, d in zip(first_word, second_word):
if c != d:
if d not in adj_list[c]:
adj_list[c].add(d)
in_degree[d] += 1
break
else:
if len(second_word) < len(first_word):
return ""
output = []
queue = deque([c for c in in_degree if in_degree[c] == 0])
while queue:
c = queue.popleft()
output.append(c)
for d in adj_list[c]:
in_degree[d] -= 1
if in_degree[d] == 0:
queue.append(d)
if len(output) < len(in_degree):
return ""
return "".join(output)8 922
#easy
Задача: 268. Missing Number
Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.
Пример:
Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.👨💻 Алгоритм: 1️⃣Сначала отсортируйте массив nums. 2️⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце. 3️⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число. 😎 Решение:
class Solution:
def missingNumber(self, nums):
nums.sort()
if nums[-1] != len(nums):
return len(nums)
elif nums[0] != 0:
return 0
for i in range(1, len(nums)):
expected_num = nums[i - 1] + 1
if nums[i] != expected_num:
return expected_num
return -18 922
#medium
Задача: 251. Flatten 2D Vector
Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.
Реализуйте класс Vector2D:
Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.
Пример:
Input ["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"] [[[[1, 2], [3], [4]]], [], [], [], [], [], [], []] Output [null, 1, 2, 3, true, true, 4, false] Explanation Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]); vector2D.next(); // return 1 vector2D.next(); // return 2 vector2D.next(); // return 3 vector2D.hasNext(); // return True vector2D.hasNext(); // return True vector2D.next(); // return 4 vector2D.hasNext(); // return False👨💻 Алгоритм: 1️⃣Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента. 2️⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае. 3️⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next(). 😎 Решение:
class Vector2D:
def __init__(self, v):
self.nums = [num for inner_list in v for num in inner_list]
self.position = -1
def next(self):
self.position += 1
return self.nums[self.position]
def hasNext(self):
return self.position + 1 < len(self.nums)8 922
#medium
Задача: 250. Count Univalue Subtrees
Дан корень бинарного дерева, верните количество поддеревьев с одинаковыми значениями.
Поддерево с одинаковыми значениями означает, что все узлы поддерева имеют одно и то же значение.
Пример:
Input: root = [5,1,5,5,5,null,5] Output: 4👨💻 Алгоритм: 1️⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0. 2️⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе: Если узел равен null, верните true. Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left). Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right). Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true. В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false. 3️⃣Верните count. 😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self):
self.count = 0
def dfs(self, node):
if not node:
return True
isLeftUniValue = self.dfs(node.left)
isRightUniValue = self.dfs(node.right)
if isLeftUniValue and isRightUniValue:
if node.left and node.left.val != node.val:
return False
if node.right and node.right.val != node.val:
return False
self.count += 1
return True
return False
def countUnivalSubtrees(self, root):
self.dfs(root)
return self.count8 922
👾 1096 собесов на Python Developer
🔒 База реальных собесов
🔒 База тестовых заданий
👾 Список менторов
🖥 Python на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Тесты для самопроверки
Список менторов
🖥 Frontend на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
👩💻 С/С++ на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
👩💻 Kotlin на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
👩💻 С# на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
👩💻 Java на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
👩💻 Swift на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
👩💻 PHP на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
🖥 Тестировщик на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Тесты для самопроверки
Список менторов
🖥 Data Science на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Тесты для самопроверки
Список менторов
👩💻 DevOps на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Тесты для самопроверки
Список менторов
👣 Golang на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
⚙ Backend на каждый день
Вопросы с собеседований
Список менторов
