Forwarded from Идущий к IT
🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной
📺 Видео: https://youtu.be/G_FOwEGPwlw
Please open Telegram to view this post
VIEW IN TELEGRAM
🤔1
Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard
У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
👨💻 Алгоритм:
1⃣ Инициализируйте массив для хранения количества способов достижения каждого индекса на каждом шаге.
2⃣ Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге.
3⃣ Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: steps = 3, arrLen = 2
Output: 4
def numWays(steps, arrLen):
mod = 10**9 + 7
max_pos = min(arrLen - 1, steps)
dp = [0] * (max_pos + 1)
dp[0] = 1
for _ in range(steps):
new_dp = [0] * (max_pos + 1)
for i in range(max_pos + 1):
new_dp[i] = dp[i] % mod
if i > 0:
new_dp[i] = (new_dp[i] + dp[i - 1]) % mod
if i < max_pos:
new_dp[i] = (new_dp[i] + dp[i + 1]) % mod
dp = new_dp
return dp[0]
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥1
Задача: 907. Sum of Subarray Minimums
Сложность: medium
Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.
Пример:
👨💻 Алгоритм:
1⃣ Использовать монотонный стек для нахождения ближайшего меньшего элемента слева и справа для каждого элемента массива.
2⃣ Использовать эту информацию для вычисления количества подмассивов, где каждый элемент является минимальным.
3⃣ Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.
Пример:
Input: arr = [3,1,2,4]
Output: 17
def sumSubarrayMins(arr):
MOD = 10**9 + 7
n = len(arr)
left = [0] * n
right = [0] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
left[i] = i + 1 if not stack else i - stack[-1]
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
right[i] = n - i if not stack else stack[-1] - i
stack.append(i)
result = sum(a * l * r for a, l, r in zip(arr, left, right)) % MOD
return result
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 251. Flatten 2D Vector
Сложность: medium
Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.
Реализуйте класс Vector2D:
Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.
Пример:
👨💻 Алгоритм:
1️⃣ Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента.
2️⃣ Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае.
3️⃣ Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next().
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции 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
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)
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 901. Online Stock Span
Сложность: medium
Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня.
Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.
Пример:
👨💻 Алгоритм:
1⃣ Инициализировать стек для хранения пар значений (цена, размах) и переменную для текущего индекса.
2⃣ Для метода next:
Установить начальный размах текущего дня равным 1.
Пока стек не пуст и верхний элемент стека имеет цену меньше или равную текущей цене:
Добавить размах верхнего элемента стека к текущему размаху.
Удалить верхний элемент стека.
3⃣ Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня.
Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.
Пример:
Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]
Установить начальный размах текущего дня равным 1.
Пока стек не пуст и верхний элемент стека имеет цену меньше или равную текущей цене:
Добавить размах верхнего элемента стека к текущему размаху.
Удалить верхний элемент стека.
Вернуть текущий размах.
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price):
span = 1
while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1]
self.stack.append((price, span))
return span
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
👍1
Задача: 789. Escape The Ghosts
Сложность: medium
Вы играете в упрощенную игру PAC-MAN на бесконечной 2D-сетке. Вы начинаете в точке [0, 0], и у вас есть конечная точка target = [xtarget, ytarget], к которой вы пытаетесь добраться. На карте находятся несколько привидений, их начальные позиции заданы в виде двумерного массива ghosts, где ghosts[i] = [xi, yi] представляет начальную позицию i-го привидения. Все входные данные являются целочисленными координатами.
Каждый ход вы и все привидения можете независимо выбирать перемещение на 1 единицу в любом из четырех основных направлений: север, восток, юг или запад, или оставаться на месте. Все действия происходят одновременно.
Вы сможете сбежать, если и только если сможете достичь цели раньше, чем любое привидение достигнет вас. Если вы достигнете любой клетки (включая конечную точку) одновременно с привидением, это не считается побегом.
Верните true, если можно сбежать независимо от того, как движутся привидения, иначе верните false.
Пример:
👨💻 Алгоритм:
1⃣ Проверьте, что наше таксическое расстояние до цели меньше, чем расстояние от любого привидения до цели.
2⃣ Если это так, мы можем гарантированно добраться до цели раньше любого привидения.
3⃣ Если привидение может добраться до цели раньше нас или одновременно с нами, побег невозможен.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вы играете в упрощенную игру PAC-MAN на бесконечной 2D-сетке. Вы начинаете в точке [0, 0], и у вас есть конечная точка target = [xtarget, ytarget], к которой вы пытаетесь добраться. На карте находятся несколько привидений, их начальные позиции заданы в виде двумерного массива ghosts, где ghosts[i] = [xi, yi] представляет начальную позицию i-го привидения. Все входные данные являются целочисленными координатами.
Каждый ход вы и все привидения можете независимо выбирать перемещение на 1 единицу в любом из четырех основных направлений: север, восток, юг или запад, или оставаться на месте. Все действия происходят одновременно.
Вы сможете сбежать, если и только если сможете достичь цели раньше, чем любое привидение достигнет вас. Если вы достигнете любой клетки (включая конечную точку) одновременно с привидением, это не считается побегом.
Верните true, если можно сбежать независимо от того, как движутся привидения, иначе верните false.
Пример:
Input: ghosts = [[1,0],[0,3]], target = [0,1]
Output: true
Explanation: You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you.
class Solution:
def escapeGhosts(self, ghosts, target):
def taxi(P, Q):
return abs(P[0] - Q[0]) + abs(P[1] - Q[1])
return all(taxi([0, 0], target) < taxi(ghost, target)
for ghost in ghosts)
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 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.
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.
Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1.
Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2.
Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии.
Запустите функцию 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:])
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 944. Delete Columns to Make Sorted
Сложность: easy
Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.
Пример:
👨💻 Алгоритм:
1⃣ Инициализировать переменную count для отслеживания количества столбцов, которые нужно удалить.
2⃣ Пройти по каждому столбцу от 0 до длины строки.
Для каждого столбца проверить, отсортированы ли символы лексикографически.
Если столбец не отсортирован, увеличить count.
3⃣ Вернуть count.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.
Пример:
Input: strs = ["cba","daf","ghi"]
Output: 1
Для каждого столбца проверить, отсортированы ли символы лексикографически.
Если столбец не отсортирован, увеличить count.
def minDeletionSize(strs):
count = 0
for col in range(len(strs[0])):
for row in range(1, len(strs)):
if strs[row][col] < strs[row - 1][col]:
count += 1
break
return count
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥1
Задача: 1059. All Paths from Source Lead to Destination
Сложность: medium
Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination.
Пример:
👨💻 Алгоритм:
1⃣ Построение графа и проверка путей:
Построить граф на основе входных данных.
Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination.
2⃣ Проверка конечности путей:
Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination.
Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро.
3⃣ Рекурсивная проверка конечности путей:
Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination.
Пример:
Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false
Построить граф на основе входных данных.
Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination.
Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination.
Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро.
Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей.
def leadsToDestination(n, edges, source, destination):
from collections import defaultdict
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
visited = [0] * n
def dfs(node):
if visited[node] != 0:
return visited[node] == 2
if not graph[node]:
return node == destination
visited[node] = 1
for neighbor in graph[node]:
if not dfs(neighbor):
return False
visited[node] = 2
return True
return dfs(source)
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 537. Complex Number Multiplication
Сложность: medium
Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.
Пример:
👨💻 Алгоритм:
1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.
2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).
3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.
Пример:
Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.
class Solution:
def complexNumberMultiply(self, a: str, b: str) -> str:
x = a.split('+')
y = b.split('+')
a_real = int(x[0])
a_img = int(x[1][:-1])
b_real = int(y[0])
b_img = int(y[1][:-1])
real_part = a_real * b_real - a_img * b_img
imaginary_part = a_real * b_img + a_img * b_real
return f"{real_part}+{imaginary_part}i"
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
👍1
Задача: 998. Maximum Binary Tree II
Сложность: medium
Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).
Пример:
👨💻 Алгоритм:
1⃣ Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.
2⃣ Вставка нового узла:
Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки.
3⃣ Создание нового дерева:
После вставки нового узла убедитесь, что дерево сохраняет свои свойства максимального дерева.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).
Пример:
Input: n = 2, trust = [[1,2]]
Output: 2
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.
Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки.
После вставки нового узла убедитесь, что дерево сохраняет свои свойства максимального дерева.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def insertIntoMaxTree(self, root: TreeNode, val: int) -> TreeNode:
if not root or val > root.val:
return TreeNode(val, left=root)
root.right = self.insertIntoMaxTree(root.right, val)
return root
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: CodeTestcaseTest ResultTest Result1523. Count Odd Numbers in an Interval Range
Сложность: easy
### Условие задачи
Даны два неотрицательных целых числа low и high. Верните количество нечётных чисел между low и high (включительно).
Пример:
👨💻 Алгоритм:
1⃣ Проверьте, является ли число low нечётным. Это можно легко сделать с помощью оператора %, но мы используем побитовый оператор &, так как он более эффективен.
2⃣ Если low нечётное, увеличьте его на 1.
3⃣ Верните (high - low) / 2 + 1. Важный момент здесь - проверить, не стало ли low больше, чем high после увеличения. Это произойдёт, если low = high, и в этом случае следует вернуть 0.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
### Условие задачи
Даны два неотрицательных целых числа low и high. Верните количество нечётных чисел между low и high (включительно).
Пример:
Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].
class Solution:
def countOdds(self, low: int, high: int) -> int:
if (low & 1) == 0:
low += 1
return 0 if low > high else (high - low) // 2 + 1
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥1
Задача: 113. Path Sum II
Сложность: Medium
Дан корень бинарного дерева и целое число targetSum. Верните все пути от корня до листа, где сумма значений узлов в пути равна targetSum. Каждый путь должен быть возвращён как список значений узлов, а не ссылок на узлы.
Путь от корня до листа — это путь, начинающийся от корня и заканчивающийся на любом листовом узле. Лист — это узел без детей.
Пример:
👨💻 Алгоритм:
1️⃣ Определение функции recurseTree: Функция принимает текущий узел (node), оставшуюся сумму (remainingSum), которая необходима для продолжения поиска вниз по дереву, и список узлов (pathNodes), который содержит все узлы, встреченные до текущего момента на данной ветке.
2️⃣ Проверка условий: На каждом шаге проверяется, равна ли оставшаяся сумма значению текущего узла. Если это так и текущий узел является листом, текущий путь (pathNodes) добавляется в итоговый список путей, который должен быть возвращен.
3️⃣ Обработка всех ветвей: Учитывая, что значения узлов могут быть отрицательными, необходимо исследовать все ветви дерева до самых листьев, независимо от текущей суммы по пути.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: Medium
Дан корень бинарного дерева и целое число targetSum. Верните все пути от корня до листа, где сумма значений узлов в пути равна targetSum. Каждый путь должен быть возвращён как список значений узлов, а не ссылок на узлы.
Путь от корня до листа — это путь, начинающийся от корня и заканчивающийся на любом листовом узле. Лист — это узел без детей.
Пример:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
class TreeNode:
def __init__(self, x: int) -> None:
self.val = x
self.left = None
self.right = None
class Solution:
def recurseTree(
self,
node: TreeNode,
remainingSum: int,
pathNodes: List[int],
pathsList: List[List[int]],
) -> None:
if not node:
return
pathNodes.append(node.val)
if remainingSum == node.val and not node.left and not node.right:
pathsList.append(list(pathNodes))
else:
self.recurseTree(
node.left, remainingSum - node.val, pathNodes, pathsList
)
self.recurseTree(
node.right, remainingSum - node.val, pathNodes, pathsList
)
pathNodes.pop()
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
pathsList = []
self.recurseTree(root, sum, [], pathsList)
return pathsList
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 1469. Find All The Lonely Nodes
Сложность: easy
В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.
Дано корневое значение бинарного дерева. Верните массив, содержащий значения всех одиночных узлов в дереве. Верните список в любом порядке.
Пример:
👨💻 Алгоритм:
1⃣ Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции.
2⃣ Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL.
3⃣ Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.
Дано корневое значение бинарного дерева. Верните массив, содержащий значения всех одиночных узлов в дереве. Верните список в любом порядке.
Пример:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def DFS(self, root, isLonely, ans):
if root is None:
return
if isLonely:
ans.append(root.val)
self.DFS(root.left, root.right is None, ans)
self.DFS(root.right, root.left is None, ans)
def getLonelyNodes(self, root):
ans = []
self.DFS(root, False, ans)
return ans
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 526. Beautiful Arrangement
Сложность: medium
Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:
perm[i] делится на i.
i делится на perm[i].
Дано целое число n, верните количество красивых перестановок, которые вы можете создать.
Пример:
👨💻 Алгоритм:
1⃣ Инициализация и подготовка массива:
Создайте массив чисел от 1 до N и инициализируйте счетчик красивых перестановок.
Создайте функцию для перестановки элементов массива.
2⃣ Рекурсивное создание перестановок и проверка условий:
Напишите рекурсивную функцию для создания всех возможных перестановок массива, начиная с текущей позиции l.
На каждом шаге перестановки проверяйте, удовлетворяет ли текущий элемент условиям делимости. Если условие выполняется, продолжайте создание перестановок рекурсивно для следующей позиции.
3⃣ Возврат результата:
В основной функции вызовите рекурсивную функцию с начальной позицией 0 и верните значение счетчика красивых перестановок.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:
perm[i] делится на i.
i делится на perm[i].
Дано целое число n, верните количество красивых перестановок, которые вы можете создать.
Пример:
Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1,2]:
- perm[1] = 1 is divisible by i = 1
- perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
- perm[1] = 2 is divisible by i = 1
- i = 2 is divisible by perm[2] = 1
Создайте массив чисел от 1 до N и инициализируйте счетчик красивых перестановок.
Создайте функцию для перестановки элементов массива.
Напишите рекурсивную функцию для создания всех возможных перестановок массива, начиная с текущей позиции l.
На каждом шаге перестановки проверяйте, удовлетворяет ли текущий элемент условиям делимости. Если условие выполняется, продолжайте создание перестановок рекурсивно для следующей позиции.
В основной функции вызовите рекурсивную функцию с начальной позицией 0 и верните значение счетчика красивых перестановок.
class Solution:
def __init__(self):
self.count = 0
def countArrangement(self, N: int) -> int:
nums = list(range(1, N + 1))
self.permute(nums, 0)
return self.count
def permute(self, nums, l):
if l == len(nums):
self.count += 1
for i in range(l, len(nums)):
nums[i], nums[l] = nums[l], nums[i]
if nums[l] % (l + 1) == 0 or (l + 1) % nums[l] == 0:
self.permute(nums, l + 1)
nums[i], nums[l] = nums[l], nums[i]
Ставь 👍 и забирай 📚 Базу знаний
Please open Telegram to view this post
VIEW IN TELEGRAM