Python | LeetCode
Ir al canal en Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Mostrar más
8 924
Suscriptores
-1024 horas
-427 días
-12730 días
Archivo de publicaciones
8 922
#medium
Задача: 399. Evaluate Division
Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.
Пример:
Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]👨💻 Алгоритм: 1⃣Создание графа: Представьте каждую переменную как узел в графе. Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]). Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]). 2⃣Поиск пути: Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj. Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj. Если путь не найден, верните -1.0. 3⃣Обработка запросов: Пройдитесь по всем запросам и используйте граф для вычисления результатов каждого запроса. 😎 Решение:
from collections import defaultdict, deque
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = defaultdict(dict)
for (A, B), value in zip(equations, values):
graph[A][B] = value
graph[B][A] = 1 / value
def bfs(start, end):
if start not in graph or end not in graph:
return -1.0
queue = deque([(start, 1.0)])
visited = set()
while queue:
current, cur_product = queue.popleft()
if current == end:
return cur_product
visited.add(current)
for neighbor, value in graph[current].items():
if neighbor not in visited:
queue.append((neighbor, cur_product * value))
return -1.0
results = []
for C, D in queries:
results.append(bfs(C, D))
return results8 922
#medium
Задача: 398. Random Pick Index
Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата.
Пример:
Input ["Solution", "pick", "pick", "pick"] [[[1, 2, 3, 3, 3]], [3], [1], [3]] Output [null, 4, 0, 2]👨💻 Алгоритм: 1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования. 2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным. 3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса. 😎 Решение:
import random
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
def pick(self, target: int) -> int:
count = 0
result = -1
for i, num in enumerate(self.nums):
if num == target:
count += 1
if random.randint(1, count) == count:
result = i
return result8 922
Мастер-класс по Python для школьников. Бесплатно!
Онлайн-урок от ведущего ИТ ВУЗа страны - Университета Иннополис для учеников 6-11 классов.
👍Бесплатно!
✅Познакомим с профессией тестировщика.
✅Научим проверять программы, находить баги.
✅На практике отработаем использование инструментов и методов тестирования.
⚡Ваш ребёнок за один час создаст автоматический тест на языке программирования Python и сможет использовать полученные знания в дальнейшем!
Для участия важно знание основ программирования на Python.
Помогите ребёнку освоить востребованную профессию.
Регистрируйтесь!
Зарегистрироваться
#реклама 16+
progmatica.innopolis.university
О рекламодателе
8 922
😎 База IT собеседований – твоё секретное оружие для успешного прохождения этапов отбора! Собеседования от реальных компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и многие другие! 🏢 Мы собрали 230 собесов, чтобы ты мог подготовиться к интервью с уверенностью и успехом.
🎯 Присоединяйся к базе и прокачай свои шансы на успешное трудоустройство!
8 922
#medium
Задача: 397. Integer Replacement
К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1.
Пример:
Input: n = 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1👨💻 Алгоритм: 1⃣Начните с данного числа n и выполните одну из следующих операций: Если n четное, замените n на n / 2. Если n нечетное, замените n на n + 1 или n - 1. 2⃣Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов. 3⃣Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат. 😎 Решение:
class Solution:
def integerReplacement(self, n: int) -> int:
def helper(n, memo):
if n == 1:
return 0
if n in memo:
return memo[n]
if n % 2 == 0:
memo[n] = 1 + helper(n // 2, memo)
else:
memo[n] = 1 + min(helper(n + 1, memo), helper(n - 1, memo))
return memo[n]
return helper(n, {})8 922
#hard
Задача: 305. Number of Islands II
Дан пустой двумерный бинарный массив
grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.
Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.
Пример:
Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]class UnionFind:
def __init__(self, size): self.parent = [-1] * size; self.rank = [0] * size; self.count = 0
def addLand(self, x): if self.parent[x] < 0: self.parent[x] = x; self.count += 1
def isLand(self, x): return self.parent[x] >= 0
def numberOfIslands(self): return self.count
def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]); return self.parent[x]
def unionSet(self, x, y): xset, yset = self.find(x), self.find(y); if xset == yset: return
if self.rank[xset] < self.rank[yset]: self.parent[xset] = yset
else: self.parent[yset] = xset; if self.rank[xset] == self.rank[yset]: self.rank[xset] += 1
self.count -= 1
class Solution:
def numIslands2(self, m, n, positions):
dsu, answer, dirs, dirc = UnionFind(m * n), [], [-1, 1, 0, 0], [0, 0, -1, 1]
for pos in positions:
land = pos[0] * n + pos[1]
dsu.addLand(land)
for i in range(4):
x, y = pos[0] + dirs[i], pos[1] + dirc[i]
neighbor = x * n + y
if 0 <= x < m and 0 <= y < n and dsu.isLand(neighbor):
dsu.unionSet(land, neighbor)
answer.append(dsu.numberOfIslands())
return answer8 922
Школьник + бесплатные курсы по ИТ = новые возможности
Хотите прокачать мышление, научиться решать задачи по математике и информатике и познакомиться с ИТ? Бесплатные курсы для школьников в этом помогут. Занятия включают теорию и практические задачи, а само обучение не будет отнимать много времени - нужно 2-3 часа в неделю. После успешного прохождения одного из курсов вам выдадут сертификат - им можно пополнить портфолио.
Чтобы начать учиться, выберите подходящую программу и оставьте заявку на сайте Т-Образования.
Подать заявку
#реклама 16+
education.tbank.ru
О рекламодателе
8 922
#medium
Задача: 542. 01 Matrix
Дана бинарная матрица размера 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.n8 922
#hard
Задача: 588. Design In-Memory File System
Спроектируйте структуру данных, которая симулирует файловую систему в памяти.
Реализуйте класс FileSystem:
FileSystem() Инициализирует объект системы.
List<String> ls(String path)
Если path является путем к файлу, возвращает список, содержащий только имя этого файла.
Если path является путем к директории, возвращает список имен файлов и директорий в этой директории.
Ответ должен быть в лексикографическом порядке.
void mkdir(String path) Создает новую директорию согласно заданному пути. Заданная директория не существует. Если промежуточные директории в пути не существуют, вы также должны создать их.
void addContentToFile(String filePath, String content)
Если filePath не существует, создает файл, содержащий заданный контент.
Если filePath уже существует, добавляет заданный контент к исходному содержимому.
String readContentFromFile(String filePath) Возвращает содержимое файла по пути filePath.
Пример:
Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]
Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/"); // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/"); // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"
👨💻 Алгоритм:
1⃣ Инициализация файловой системы:
Создайте класс FileSystem, который будет содержать вложенный класс File. Класс File будет представлять либо файл, либо директорию, содержать флаг isfile, словарь files и строку content.
2⃣ Обработка команд:
Реализуйте метод ls, который возвращает список файлов и директорий в указанном пути, либо имя файла, если указанный путь является файлом.
Реализуйте метод mkdir, который создаёт директории по указанному пути. Если промежуточные директории не существуют, создайте их.
Реализуйте метод addContentToFile, который добавляет содержимое в файл по указанному пути. Если файл не существует, создайте его.
Реализуйте метод readContentFromFile, который возвращает содержимое файла по указанному пути.
3⃣ Обработка путей и работа с файлами/директориями:
Используйте метод split для разделения пути на составляющие и навигации по дереву директорий и файлов.
Для каждой команды выполняйте соответствующие операции по созданию, чтению или записи содержимого файлов и директорий.
😎 Решение:
class FileSystem:
class File:
def __init__(self):
self.isfile = False
self.files = {}
self.content = ""
def __init__(self):
self.root = self.File()
def ls(self, path: str) -> list:
t = self._navigate(path)
if t.isfile:
return [path.split("/")[-1]]
return sorted(t.files.keys())
def mkdir(self, path: str) -> None:
self._navigate(path)
def addContentToFile(self, filePath: str, content: str) -> None:
t = self._navigate(filePath)
t.isfile = True
t.content += content
def readContentFromFile(self, filePath: str) -> str:
return self._navigate(filePath).content
def _navigate(self, path: str) -> 'File':
t = self.root
if path != "/":
for dir in path.split("/"):
if dir:
if dir not in t.files:
t.files[dir] = self.File()
t = t.files[dir]
return t8 922
Скидка 15% на корпоративное такси. Яндекс Go для бизнеса
Скидка 15% на первые три месяца.
Возврат НДС до 20% на все рабочие поездки. Контроль маршрутов и расходов в одном кабинете.
Быстрая подача авто от 5 минут. Удобное онлайн-подключение без визита в офис.
Узнать больше
#реклама
business.go.yandex
О рекламодателе
8 922
#medium
Задача: 304. Range Sum Query 2D - Immutable
Дана двумерная матрица matrix. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2).
Реализуйте класс NumMatrix:
- NumMatrix(int[][] matrix) Инициализирует объект целочисленной матрицей matrix.- int sumRegion(int row1, int col1, int row2, int col2) Возвращает сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2).
Необходимо разработать алгоритм, где метод sumRegion работает за O(1) по времени.
Пример:
Input ["NumMatrix", "sumRegion", "sumRegion", "sumRegion"] [[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]👨💻 Алгоритм: 1⃣Инициализация: Создайте двумерный массив sums размером (m + 1) x (n + 1), где m и n — размеры исходной матрицы matrix. Заполните этот массив нулями. 2⃣Предварительное вычисление сумм: Заполните массив sums, где каждый элемент sums[i][j] будет содержать сумму всех элементов матрицы от начала до позиции (i-1, j-1) включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов внутри прямоугольника, определенного его углами (row1, col1) и (row2, col2), используйте предварительно вычисленный массив sums для получения результата за O(1) времени. 😎 Решение:
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
if not matrix or not matrix[0]:
self.dp = []
return
m, n = len(matrix), len(matrix[0])
self.dp = [[0] * (n + 1) for _ in range(m + 1)]
for r in range(m):
for c in range(n):
self.dp[r + 1][c + 1] = self.dp[r + 1][c] + self.dp[r][c + 1] + matrix[r][c] - self.dp[r][c]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return self.dp[row2 + 1][col2 + 1] - self.dp[row1][col2 + 1] - self.dp[row2 + 1][col1] + self.dp[row1][col1]8 922
#hard
Задача: 587. Erect the Fence
Вам дан массив trees, где trees[i] = [xi, yi] представляет местоположение дерева в саду.
Оградите весь сад с использованием минимальной длины веревки, так как это дорого. Сад хорошо огорожен только в том случае, если все деревья окружены.
Верните координаты деревьев, которые находятся точно на периметре ограды. Вы можете вернуть ответ в любом порядке.
Пример:
Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]] Output: [[1,1],[2,0],[4,2],[3,3],[2,4]] Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.👨💻 Алгоритм: 1⃣ Сортировка точек и построение нижней оболочки: Отсортируйте точки по их x-координатам, а в случае совпадения x-координат, по y-координатам. Постройте нижнюю оболочку, добавляя точки к оболочке и удаляя последние точки, если они не образуют против часовой стрелки поворот. 2⃣ Построение верхней оболочки: Пройдитесь по точкам в обратном порядке, чтобы построить верхнюю оболочку. Добавляйте точки к оболочке и удаляйте последние точки, если они не образуют против часовой стрелки поворот. 3⃣ Удаление дублирующих элементов и возврат результата: Используйте HashSet, чтобы удалить дублирующиеся точки из стека. Преобразуйте результат в массив и верните его. 😎 Решение:
class Solution:
def orientation(self, p, q, r):
return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
def outerTrees(self, points):
points.sort(key=lambda x: (x[0], x[1]))
hull = []
for point in points:
while len(hull) >= 2 and self.orientation(hull[-2], hull[-1], point) > 0:
hull.pop()
hull.append(point)
hull.pop()
for point in reversed(points):
while len(hull) >= 2 and self.orientation(hull[-2], hull[-1], point) > 0:
hull.pop()
hull.append(point)
return list(set(map(tuple, hull)))8 922
Запустите рекламу в телеграм-каналах с Яндекс Директом
Перфоманс-реклама теперь в телеграм-каналах ⚡
Яндекс Директ знает, как привлечь целевую аудиторию 💰👌
Попробовать
#реклама
yandex.ru
О рекламодателе
8 922
#medium
Задача: 583. Delete Operation for Two Strings
Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.
На одном шаге можно удалить ровно один символ в любой строке.
Пример:
Input: word1 = "sea", word2 = "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".👨💻 Алгоритм: 1⃣ Инициализация массива: Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2. 2⃣ Заполнение массива: Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки. 3⃣ Обновление и результат: Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений. 😎 Решение:
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [0] * (n + 1)
for i in range(m + 1):
temp = [0] * (n + 1)
for j in range(n + 1):
if i == 0 or j == 0:
temp[j] = i + j
elif word1[i - 1] == word2[j - 1]:
temp[j] = dp[j - 1]
else:
temp[j] = 1 + min(dp[j], temp[j - 1])
dp = temp
return dp[n]8 922
#medium
Задача: 537. Complex Number Multiplication
Комплексное число можно представить в виде строки в формате "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.👨💻 Алгоритм: 1⃣ Извлечение реальной и мнимой частей: Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'. 2⃣ Вычисление произведения: Переведите извлечённые части в целые числа. Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay). 3⃣ Формирование строки результата: Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её. 😎 Решение:
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"8 922
Тот самый канал Яндекс Маркета
Тут топовые подборки, конкурсы с самыми крутыми призами и, конечно, мемы. Подписывайтесь и радуйтесь покупкам по низким ценам!
Подписаться
#реклама
О рекламодателе
8 922
#easy
Задача: 303. Range Sum Query - Immutable
Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).
Пример:
Input ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] Output [null, 1, -1, -3]👨💻 Алгоритм: 1⃣Инициализация: Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums. 2⃣Предварительное вычисление сумм: Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат. 😎 Решение:
class NumArray:
def __init__(self, nums: List[int]):
self.sum = [0] * (len(nums) + 1)
for i in range(len(nums)):
self.sum[i + 1] = self.sum[i] + nums[i]
def sumRange(self, i: int, j: int) -> int:
return self.sum[j + 1] - self.sum[i]8 922
#medium
Задача: 536. Construct Binary Tree from String
Вам нужно построить бинарное дерево из строки, состоящей из круглых скобок и целых чисел.
Весь ввод представляет собой бинарное дерево. Он содержит целое число, за которым следуют ноль, одна или две пары круглых скобок. Целое число представляет значение корня, а пара круглых скобок содержит дочернее бинарное дерево с той же структурой.
Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует.
Пример:
Input: s = "4(2(3)(1))(6(5))" Output: [4,2,6,3,1,5]👨💻 Алгоритм: 1⃣ Извлечение числа: Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть. 2⃣ Построение поддерева: Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки. Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют. 3⃣ Основная функция: Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево. 😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def str2tree(self, s: str) -> TreeNode:
def getNumber(s, index):
isNegative = False
if s[index] == '-':
isNegative = True
index += 1
number = 0
while index < len(s) and s[index].isdigit():
number = number * 10 + int(s[index])
index += 1
return (-number if isNegative else number, index)
def str2treeInternal(s, index):
if index == len(s):
return None, index
value, index = getNumber(s, index)
node = TreeNode(value)
if index < len(s) and s[index] == '(':
node.left, index = str2treeInternal(s, index + 1)
if index < len(s) and s[index] == '(':
node.right, index = str2treeInternal(s, index + 1)
return node, index + 1 if index < len(s) and s[index] == ')' else index
return str2treeInternal(s, 0)[0]8 922
ТОП-4 Курса по Программированию
⚡Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов.
✅Хотите стать программистом, но не знаете с какого языка начать?
Помогаем разобраться в самых популярных и востребованных языках программирования.
Подарок в конце подборки!
Выбрать
#реклама 16+
tutortop.ru
О рекламодателе
8 922
#medium
Задача: 535. Encode and Decode TinyURL
Спроектируйте класс для кодирования URL и декодирования короткого URL.
Нет ограничений на то, как ваш алгоритм кодирования/декодирования должен работать. Вам просто нужно убедиться, что URL может быть закодирован в короткий URL, а короткий URL может быть декодирован в исходный URL.
Реализуйте класс Solution:
Solution() Инициализирует объект системы.
String encode(String longUrl) Возвращает короткий URL для данного longUrl.
String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом.
Пример:
Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"
Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.import random
import string
class Codec:
def __init__(self):
self.alphabet = string.ascii_letters + string.digits
self.map = {}
self.key = self.get_rand()
def get_rand(self):
return ''.join(random.choice(self.alphabet) for _ in range(6))
def encode(self, longUrl: str) -> str:
while self.key in self.map:
self.key = self.get_rand()
self.map[self.key] = longUrl
return "http://tinyurl.com/" + self.key
def decode(self, shortUrl: str) -> str:
key = shortUrl.replace("http://tinyurl.com/", "")
return self.map.get(key, "")