Python | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
إظهار المزيد
الشبكة:9 165
المشتركون
-724 ساعات
-187 أيام
-7030 أيام
أرشيف المشاركات
9 165
Задача: 668. Kth Smallest Number in Multiplication Table
Сложность: hard
Почти каждый использовал таблицу умножения. Таблица умножения размером m x n - это целочисленная матрица mat, где mat[i][j] == i * j (индексация начинается с 1).
Даны три целых числа m, n и k. Верните k-й наименьший элемент в таблице умножения размером m x n.
Пример:
Input: m = 3, n = 3, k = 5 Output: 3 Explanation: The 5th smallest number is 3.👨💻 Алгоритм: 1⃣Установка границ поиска: Установите нижнюю границу left равной 1 и верхнюю границу right равной m * n. 2⃣Бинарный поиск: Используйте бинарный поиск, чтобы найти k-й наименьший элемент. Для каждого среднего значения mid, посчитайте количество элементов в таблице умножения, которые меньше или равны mid. 3⃣Проверка количества элементов: Если количество элементов меньше k, увеличьте нижнюю границу (left). Если количество элементов больше или равно k, уменьшите верхнюю границу (right). 😎 Решение:
class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
def count_less_equal(x):
count = 0
for i in range(1, m + 1):
count += min(x // i, n)
return count
left, right = 1, m * n
while left < right:
mid = (left + right) // 2
if count_less_equal(mid) < k:
left = mid + 1
else:
right = mid
return left9 165
Задача: 1038. Binary Search Tree to Greater Sum Tree
Сложность: medium
Получив корень двоичного дерева поиска (BST), преобразуйте его в большее дерево таким образом, чтобы каждый ключ исходного BST был заменен на исходный ключ плюс сумма всех ключей, превышающих исходный ключ в BST. Напомним, что двоичное дерево поиска - это дерево, удовлетворяющее следующим ограничениям: левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла. Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла. И левое, и правое поддеревья должны быть двоичными деревьями поиска.
Пример:
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]👨💻 Алгоритм: 1⃣Обратный обход in-order: Пройдите по дереву в порядке "правый, корень, левый" (обратный in-order обход). Это обеспечит посещение узлов в порядке убывания их значений. 2⃣Накопление суммы: Во время обхода поддерживайте переменную для хранения накопленной суммы. На каждом узле добавляйте значение узла к накопленной сумме и обновляйте значение узла этой накопленной суммой. 3⃣Преобразование узлов: Преобразуйте значение каждого узла в накопленную сумму. 😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def bstToGst(self, root: TreeNode) -> TreeNode:
self.sum = 0
def reverse_inorder(node):
if not node:
return
reverse_inorder(node.right)
self.sum += node.val
node.val = self.sum
reverse_inorder(node.left)
reverse_inorder(root)
return root9 165
Задача: 1025. Divisor Game
Сложность: easy
Алиса и Боб играют в игру по очереди, причем Алиса начинает первой. Изначально на доске мелом написано число n. В свой ход каждый игрок делает ход, состоящий из: выбора любого x при 0 < x < n и n % x == 0. Замены числа n на доске на n - x. Также, если игрок не может сделать ход, он проигрывает игру. Возвращается true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально.
Пример:
Input: n = 2
Output: trueclass Solution:
def divisorGame(self, n: int) -> bool:
return n % 2 == 09 165
Задача: 261. Graph Valid Tree
Сложность: medium
У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе.
Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае.
Пример:
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true👨💻 Алгоритм: 1️⃣Проверьте, что количество рёбер равно n - 1. Если нет, верните false. 2️⃣Используйте итеративный обход в глубину (DFS) для проверки связности графа и отсутствия циклов. Создайте стек для хранения узлов для посещения и множество для отслеживания посещённых узлов. Начните с узла 0. 3️⃣Если все узлы посещены и циклы не обнаружены, верните true. В противном случае, верните false. 😎 Решение:
import collections
from typing import List
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False
adj_list = [[] for _ in range(n)]
for A, B in edges:
adj_list[A].append(B)
adj_list[B].append(A)
parent = {0: -1}
queue = collections.deque([0])
while queue:
node = queue.popleft()
for neighbour in adj_list[node]:
if neighbour == parent[node]:
continue
if neighbour in parent:
return False
parent[neighbour] = node
queue.append(neighbour)
return len(parent) == n9 165
Задача: 384. Shuffle an Array
Сложность: medium
Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.
Реализуйте класс Solution:
Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.
Пример:
Input: ransomNote = "a", magazine = "b" Output: false👨💻 Алгоритм: 1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива. 2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент. 3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие. 😎 Решение:
import random
class Solution:
def __init__(self, nums: list[int]):
self.array = nums[:]
self.original = nums[:]
def reset(self) -> list[int]:
self.array = self.original[:]
return self.original
def shuffle(self) -> list[int]:
for i in range(len(self.array)):
rand_index = random.randint(i, len(self.array) - 1)
self.array[i], self.array[rand_index] = self.array[rand_index], self.array[i]
return self.array9 165
Зарабатывайте на установках Яндекс Браузера
Партнёрская программа для сервисных центров, магазинов компьютерной техники, сайтов для скачивания файлов и авторов статей.
Вы можете предлагать его своим клиентам и аудитории — и зарабатывать на новых установках.
Выплаты до 500₽ за каждую установку Яндекс Браузера.
Подать заявку
#реклама 0+
partner.browser.yandex.ru
О рекламодателе
9 165
Задача: 718. Maximum Length of Repeated Subarray
Сложность: medium
Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.
Пример:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] Output: 3👨💻 Алгоритм: 1⃣Создайте двумерный массив для хранения длин общих подмассивов. 2⃣Используйте динамическое программирование для нахождения максимальной длины общего подмассива. 3⃣Итеративно обновляйте массив, сравнивая элементы обоих массивов и обновляя максимальную длину подмассива. 😎 Решение:
def findLength(nums1, nums2):
dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
max_len = 0
for i in range(len(nums1) - 1, -1, -1):
for j in range(len(nums2) - 1, -1, -1):
if nums1[i] == nums2[j]:
dp[i][j] = dp[i + 1][j + 1] + 1
max_len = max(max_len, dp[i][j])
return max_len9 165
🔥 Бесплатный интенсив по ChatGPT и созданию НЕЙРОСТРУДНИКОВ без опыта программирования🔥
Вы узнаете, как использовать ChatGPT в профессиональных целях, создавать нейросотрудников на заказ и зарабатывать на ИИ от 150.000р в месяц.
Простое понимание основ, без сложного кода!
Что будет на интенсиве?
🧬 Теория: как создаются нейро-сотрудники с GPT на Python
🧬 Практика: мы создадим нейро-консультанта, нейро-HR, нейро-маркетолога и др.
Интенсив - максимально простой и доступный, без какого-либо сложного программирования.
Ведущий интенсива - Senior AI-разработчик нейросетей с 2003 года и основатель Университета искусственного интеллекта - Дмитрий Романов.
🤖 Присоединяйтесь к нашему бесплатному интенсиву и разберитесь в этой увлекательной теме с нами!
9 165
Задача: 36. Valid Sudoku
Сложность: medium
Определите, является ли доска Судоку размером 9 на 9 валидной. Необходимо проверить только заполненные ячейки согласно следующим правилам:
Каждая строка должна содержать цифры от 1 до 9 без повторений.
Каждый столбец должен содержать цифры от 1 до 9 без повторений.
Каждая из девяти подзон размером 3 на 3 в сетке должна содержать цифры от 1 до 9 без повторений.
Пример:
Input: board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] Output: true👨💻 Алгоритм: 1️⃣Инициализируйте список из 9 хеш-множеств, где хеш-множество с индексом r будет использоваться для хранения ранее увиденных чисел в строке r судоку. Аналогично инициализируйте списки из 9 хеш-множеств для отслеживания столбцов и блоков. 2️⃣Итерируйтесь по каждой позиции (r, c) в судоку. На каждой итерации, если на текущей позиции есть число: Проверьте, существует ли это число в хеш-множестве для текущей строки, столбца или блока. Если да, верните false, потому что это второе появление числа в текущей строке, столбце или блоке. 3️⃣В противном случае обновите множество, отвечающее за отслеживание ранее увиденных чисел в текущей строке, столбце и блоке. Индекс текущего блока рассчитывается как (r / 3) * 3 + (c / 3), где / означает деление нацело. Если дубликаты не были найдены после посещения каждой позиции на доске судоку, то судоку валидно, поэтому верните true. 😎 Решение:
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
N = 9
rows = [set() for _ in range(N)]
cols = [set() for _ in range(N)]
boxes = [set() for _ in range(N)]
for r in range(N):
for c in range(N):
val = board[r][c]
if val == ".":
continue
if val in rows[r]:
return False
rows[r].add(val)
if val in cols[c]:
return False
cols[c].add(val)
idx = (r // 3) * 3 + c // 3
if val in boxes[idx]:
return False
boxes[idx].add(val)
return True9 165
Университет искусственного интеллекта приглашает
💰 Стоимость вебинара:
Бесплатно!
Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях.
💻 Программа вебинара:
1) Классификация входящих/выходящих из автобуса людей
2) Классификация отзывов на Tesla
3) Оценка выброса CO2 по параметрам машины
4) Прогнозирование тренда цены доллара
5) Сегментация изображения для робота-доставщика
6) Обнаружение людей без касок на стройке/производстве
7) Трекинг людей на видео
8) Распознавание речи
9) Генерация изображения с помощью Stable Diffusion
Хочешь отучиться на передовой научного прогресса? Тогда скорее регистрируйся!
Зарегистрироваться
#реклама 16+
neural-university.ru
О рекламодателе
9 165
Задача: 1015. Smallest Integer Divisible by K
Сложность: medium
Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число.
Пример:
Input: k = 1 Output: 1👨💻 Алгоритм: 1⃣Использование остатка для нахождения числа с цифрами 1: Создайте переменную num и установите ее равной 1. Создайте переменную length и установите ее равной 1 для отслеживания длины числа. 2⃣Итеративное нахождение числа: Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k. Увеличивайте length на 1 в каждой итерации. Если в какой-то итерации num % k == 0, верните length. 3⃣Проверка бесконечного цикла: Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует. 😎 Решение:
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
num, length = 1, 1
seen = set()
while num % k != 0:
if num % k in seen:
return -1
seen.add(num % k)
num = (num * 10 + 1) % k
length += 1
return length9 165
Задача: 65. Valid Number
Сложность: hard
Учитывая строку s, определите, является ли s валидным числом.
Например, все следующие строки являются действительными числами: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789". В то время как следующие строки не являются валидными числами: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".
Формально, валидное число определяется с использованием одного из следующих определений:
Целое число с необязательным показателем степени.
Десятичное число с необязательным показателем степени.
Целое число определяется необязательным знаком '-' или '+' за которым следуют цифры.
Десятичное число определяется необязательным знаком '-' или '+' и одним из следующих определений:
Цифры, за которыми следует точка '.'.
Цифры, за которыми следует точка '.', за которой следуют цифры.
Точка '.', за которой следуют цифры.
Показатель степени определяется с помощью обозначения показателя степени 'e' или 'E', за которым следует целое число.
Цифры определяются как одна или более цифр.
Пример:
Input: s = "0" Output: true👨💻 Алгоритм: 1️⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true. 2️⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число. 3️⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры. 😎 Решение:
class Solution:
def isNumber(self, s: str) -> bool:
seen_digit = seen_exponent = seen_dot = False
for i, c in enumerate(s):
if c.isdigit():
seen_digit = True
elif c in ["+", "-"]:
if i > 0 and s[i - 1] != "e" and s[i - 1] != "E":
return False
elif c in ["e", "E"]:
if seen_exponent or not seen_digit:
return False
seen_exponent = True
seen_digit = False
elif c == ".":
if seen_dot or seen_exponent:
return False
seen_dot = True
else:
return False
return seen_digit9 165
Мечтаешь стать дизайнером?
Начни с dsgn sense — мультисенсорной олимпиады по дизайну от Школы дизайна Центрального университета для учеников 10-11-х классов.
Познакомься с профессиями графического, продуктового и промышленного дизайнера! Реши кейс от компаний-партнеров и создай проект, в котором зрение, слух, осязание, вкус и обоняние станут основой уникального дизайн-решения.
Призеры и победители получат:
— Два проекта в портфолио.
— Финал в наукограде Дубне с бесплатным проживанием, питанием и насыщенной программой.
— Крутой мерч и призы от компаний.
— Шанс выиграть грант до 100% на обучение в бакалавриате ЦУ.
Тебе не нужны специальные навыки: достаточно любопытства и желания экспериментировать.
Регистрируйся до 16 февраля по ссылке:
Зарегистрироваться
Есть противопоказания. Посоветуйтесь с врачом.
#реклама 16+
event.cu.ru
О рекламодателе
9 165
Задача: 1271. Hexspeak
Сложность: easy
Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".
Пример:
Input: num = "257" Output: "IOI"👨💻 Алгоритм: 1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре. 2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I' 3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR". 😎 Решение:
def toHexString(num):
hex_str = hex(int(num))[2:].upper().replace('0', 'O').replace('1', 'I')
for char in hex_str:
if char not in 'ABCDEFIO':
return "ERROR"
return hex_str9 165
Задача: 997. Find the Town Judge
Сложность: easy
В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае.
Пример:
Input: n = 2, trust = [[1,2]] Output: 2👨💻 Алгоритм: 1⃣Создание счетчиков доверия: Инициализируйте массив для подсчета количества людей, которым доверяет каждый человек, и массив для подсчета количества людей, которые доверяют каждому человеку. 2⃣Подсчет доверия: Пройдитесь по каждому элементу в массиве trust и обновите счетчики: увеличьте количество доверий для того, кто доверяет, и увеличьте количество доверенных людей для того, кому доверяют. 3⃣Проверка условий судьи: Пройдитесь по массиву людей и найдите того, кто никому не доверяет (количество доверий равно 0) и кому доверяют все остальные (количество доверенных людей равно n-1). Верните метку этого человека. Если такого человека нет, верните -1. 😎 Решение:
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
if not trust and n == 1:
return 1
trust_count = [0] * (n + 1)
trusted_by = [0] * (n + 1)
for a, b in trust:
trust_count[a] += 1
trusted_by[b] += 1
for i in range(1, n + 1):
if trust_count[i] == 0 and trusted_by[i] == n - 1:
return i
return -19 165
Задача: 1243. Array Transformation
Сложность: easy
Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.
Пример:
Input: arr = [6,2,3,4] Output: [6,3,3,4]👨💻 Алгоритм: 1⃣Инициализация нового массива с такими же значениями, как у исходного массива. Циклически изменяем массив в соответствии с правилами, пока он не перестанет меняться. 2⃣Для каждого элемента массива проверяем, изменяется ли он в зависимости от его левого и правого соседей. Если элемент меньше своего левого и правого соседей, увеличиваем его. Если элемент больше своего левого и правого соседей, уменьшаем его. 3⃣Первый и последний элементы массива остаются неизменными. 😎 Решение:
def transformArray(arr):
while True:
new_arr = arr[:]
changed = False
for i in range(1, len(arr) - 1):
if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
new_arr[i] += 1
changed = True
elif arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
new_arr[i] -= 1
changed = True
if not changed:
break
arr = new_arr
return arr9 165
Реклама для бизнеса любого уровня в Яндекс Директе
Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌
Начните прямо сейчас ⚡
Зарегистрироваться
#реклама
direct.yandex.ru
О рекламодателе
9 165
Задача: 542. 01 Matrix
Сложность: medium
Дана бинарная матрица размера m x n, верните расстояние до ближайшего нуля для каждой ячейки.
Расстояние между двумя соседними ячейками равно 1.
Пример:
Input: mat = [[0,0,0],[0,1,0],[0,0,0]] Output: [[0,0,0],[0,1,0],[0,0,0]]👨💻 Алгоритм: 1⃣Создайте копию матрицы mat, назовем её matrix. Используйте структуру данных seen для пометки уже посещенных узлов и очередь для выполнения BFS. Поместите все узлы с 0 в очередь и отметьте их в seen. 2⃣Выполните BFS: Пока очередь не пуста, извлекайте текущие row, col, steps из очереди. Итеративно пройдите по четырем направлениям. Для каждой nextRow, nextCol проверьте, находятся ли они в пределах границ и не были ли они уже посещены в seen. 3⃣Если так, установите matrix[nextRow][nextCol] = steps + 1 и поместите nextRow, nextCol, steps + 1 в очередь. Также отметьте nextRow, nextCol в seen. Верните matrix. 😎 Решение:
from collections import deque
class Solution:
def __init__(self):
self.m = 0
self.n = 0
self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def updateMatrix(self, mat):
self.m = len(mat)
self.n = len(mat[0])
matrix = [[0] * self.n for _ in range(self.m)]
seen = [[False] * self.n for _ in range(self.m)]
queue = deque()
for row in range(self.m):
for col in range(self.n):
matrix[row][col] = mat[row][col]
if matrix[row][col] == 0:
queue.append((row, col, 0))
seen[row][col] = True
while queue:
row, col, steps = queue.popleft()
for dr, dc in self.directions:
nextRow, nextCol = row + dr, col + dc
if self.valid(nextRow, nextCol) and not seen[nextRow][nextCol]:
seen[nextRow][nextCol] = True
queue.append((nextRow, nextCol, steps + 1))
matrix[nextRow][nextCol] = steps + 1
return matrix
def valid(self, row, col):
return 0 <= row < self.m and 0 <= col < self.n9 165
Бесплатный курс по дизайну: веб, графический и UX/UI
Научись создавать дизайн сайтов и приложений, инфографику для карточек на маркетплейсах и работать в Figma!
Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰
Этот курс для тебя, если ты:
✅ мечтаешь о новой профессии в digital, но не знаешь, с чего начать;
✅ чувствуешь, что хочешь большего — свободы, самореализации, творчества;
✅ полный новичок и хочешь систему, а не хаос;
✅ хочешь начать зарабатывать удалённо.
Зарегистрироваться
#реклама 16+
ydaev.ru
О рекламодателе
9 165
Задача: 655. Print Binary Tree
Сложность: medium
Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.
Пример:
Input: root = [1,2] Output: [["","1",""], ["2","",""]]👨💻 Алгоритм: 1⃣Найдите высоту дерева и определите размер матрицы (m x n). 2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла. 3⃣Верните заполненную матрицу. 😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def findHeight(root):
if not root:
return -1
return 1 + max(findHeight(root.left), findHeight(root.right))
def fill(res, root, r, c, height):
if not root:
return
res[r][c] = str(root.val)
if root.left:
fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height)
if root.right:
fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height)
def printTree(root):
height = findHeight(root)
m = height + 1
n = (1 << (height + 1)) - 1
res = [["" for _ in range(n)] for _ in range(m)]
fill(res, root, 0, (n - 1) // 2, height)
return res