اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
Python | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+20tRfhrwPpM4NDQy Вопросы собесов t.me/+cnJC0_ZeZ_I0OGY6 Вакансии t.me/+cXGKkrOY2-w3ZTky
نمایش بیشتر9 394
مشترکین
-524 ساعت
-147 روز
-5930 روز
آرشیو پست ها
9 394
#easy
Задача: 222. Count Complete Tree Nodes
Учитывая корень полного двоичного дерева, верните количество узлов в дереве.
Согласно Википедии, в полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. Он может содержать от 1 до 2 в степени n узлов включительно на последнем уровне n.
Разработайте алгоритм, который выполняется за время, меньшее, чем O(n).
Пример:
Input: root = [1,2,3,4,5,6] Output: 6👨💻 Алгоритм: 1️⃣ Инициализация и проверка пустоты дерева Если дерево пустое, вернуть 0. Рассчитать глубину дерева d. 2️⃣ Поиск узлов на последнем уровне Использовать двоичный поиск, чтобы найти количество узлов на последнем уровне. Функция exists используется для проверки наличия узла по индексу. 3️⃣ Вычисление общего количества узлов Вернуть сумму узлов на всех уровнях, кроме последнего, и узлов на последнем уровне. 😎 Решение:
class Solution:
def compute_depth(self, node: TreeNode) -> int:
d = 0
while node.left:
node = node.left
d += 1
return d
def exists(self, idx: int, d: int, node: TreeNode) -> bool:
left, right = 0, 2**d - 1
for _ in range(d):
pivot = left + (right - left) // 2
if idx <= pivot:
node = node.left
right = pivot
else:
node = node.right
left = pivot + 1
return node is not None
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
d = self.compute_depth(root)
if d == 0:
return 1
left, right = 1, 2**d - 1
while left <= right:
pivot = left + (right - left) // 2
if self.exists(pivot, d, root):
left = pivot + 1
else:
right = pivot - 1
return (2**d - 1) + left9 394
😮 Добавлена новая база слитых курсов на 800ГБ:
Python:
https://t.me/+QPSH2IcGu4w5ODky
Frontend и Web:
https://t.me/+MiJVQSyUlDNjODky
Программирование:
https://t.me/+opj2LZT23ddiZDli
Графика и дизайн:
https://t.me/+vrZ8dhdUEXM3YmQy
9 394
#medium
Задача: 221. Maximal Square
Дана бинарная матрица размером 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 * maxsqlen9 394
⚡ Когда говорят, что Python слишком простой язык, на сцену выходит канал Python Learning
Здесь легко научиться:
▪️Превращать текст в голос
▪️Определять локацию по IP
▪️Писать телеграм-ботов
▪️Создавать 3D-игры
Самый необычный канал про Python, подписывайся – @Python_per_month
9 394
#hard
Задача: 220. Contains Duplicate III
Вам дан массив целых чисел nums и два целых числа indexDiff и valueDiff.
Найдите пару индексов (i, j) таких, что:
i != j,
abs(i - j) <= indexDiff,
abs(nums[i] - nums[j]) <= valueDiff.
Верните true, если такая пара существует, или false в противном случае.
Пример:
Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0 Output: true Explanation: We can choose (i, j) = (0, 3). We satisfy the three conditions: i != j --> 0 != 3 abs(i - j) <= indexDiff --> abs(0 - 3) <= 3 abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0👨💻 Алгоритм: 1️⃣ Инициализация и вычисление корзин: Рассчитать ширину корзины w = t + 1. Инициализировать пустой хэш-таблицей buckets. Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w. 2️⃣ Итерация и проверка корзин: Перебрать все элементы массива nums. Для каждого элемента nums[i]: Определить его корзину с помощью getID. Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true. Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true. Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину. Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна. 3️⃣ Завершение: Если ни одна пара "почти дубликатов" не найдена, вернуть false. 😎 Решение:
class Solution:
def containsNearbyAlmostDuplicate(self, nums, k, t):
if t < 0: return False
buckets = {}
w = t + 1
for i in range(len(nums)):
bucket = nums[i] // w if nums[i] >= 0 else (nums[i] + 1) // w - 1
if bucket in buckets: return True
if bucket - 1 in buckets and abs(nums[i] - buckets[bucket - 1]) < w: return True
if bucket + 1 in buckets and abs(nums[i] - buckets[bucket + 1]) < w: return True
buckets[bucket] = nums[i]
if i >= k:
del buckets[nums[i - k] // w if nums[i - k] >= 0 else (nums[i - k] + 1) // w - 1]
return False9 394
#hard
Задача: 315. Count of Smaller Numbers After Self
Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].
Пример:
Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.👨💻 Алгоритм: 1️⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4. 2️⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия: Смещайте число на num + offset. Запросите количество элементов в дереве отрезков, которые меньше текущего числа. Обновите счетчик текущего числа в дереве отрезков. 3️⃣Верните результат. 😎 Решение:
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
def update(index, value, tree, size):
index += size
tree[index] += value
while index > 1:
index //= 2
tree[index] = tree[index * 2] + tree[index * 2 + 1]
def query(left, right, tree, size):
result = 0
left += size
right += size
while left < right:
if left % 2 == 1:
result += tree[left]
left += 1
left //= 2
if right % 2 == 1:
right -= 1
result += tree[right]
right //= 2
return result
offset = 10**4
size = 2 * 10**4 + 1
tree = [0] * (2 * size)
result = []
for num in reversed(nums):
smaller_count = query(0, num + offset, tree, size)
result.append(smaller_count)
update(num + offset, 1, tree, size)
return reversed(result)9 394
#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())]9 394
#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 False9 394
#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 onePostBack9 394
#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 answer9 394
#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 False9 394
#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 - left9 394
#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 k9 394
#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 results9 394
#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]9 394
#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()9 394
#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 ""9 394
#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)9 394
Ментор поможет сэкономить время и быстрее зайти в IT
https://easyoffer.ru/mentor
9 394
#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 closest