Задача: 1057. Campus Bikes
Сложность: medium
В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
👨💻 Алгоритм:
1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.
2⃣Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда.
Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы.
3⃣Заполни и верни массив назначений.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]
👨💻 Алгоритм:
1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.
2⃣Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда.
Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы.
3⃣Заполни и верни массив назначений.
😎 Решение:
def assignBikes(workers, bikes):
pairs = []
for i, (wx, wy) in enumerate(workers):
for j, (bx, by) in enumerate(bikes):
distance = abs(wx - bx) + abs(wy - by)
pairs.append((distance, i, j))
pairs.sort()
result = [-1] * len(workers)
bike_taken = [False] * len(bikes)
worker_assigned = [False] * len(workers)
for distance, worker_idx, bike_idx in pairs:
if not worker_assigned[worker_idx] and not bike_taken[bike_idx]:
result[worker_idx] = bike_idx
bike_taken[bike_idx] = True
worker_assigned[worker_idx] = True
return result
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1248. Count Number of Nice Subarrays
Сложность: medium
Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.
Пример:
👨💻 Алгоритм:
1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.
2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц.
3⃣Подсчитайте количество таких подмассивов и верните этот результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.
Пример:
Input: arr = [1,2]
Output: 2
👨💻 Алгоритм:
1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.
2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц.
3⃣Подсчитайте количество таких подмассивов и верните этот результат.
😎 Решение:
def numberOfSubarrays(nums, k):
def atMost(nums, k):
count = 0
left = 0
res = 0
for right in range(len(nums)):
if nums[right] % 2 == 1:
count += 1
while count > k:
if nums[left] % 2 == 1:
count -= 1
left += 1
res += right - left + 1
return res
return atMost(nums, k) - atMost(nums, k - 1)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 867. Transpose Matrix
Сложность: easy
Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.
Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк.
2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c].
3⃣Верните матрицу ans.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.
Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.
Пример:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]
👨💻 Алгоритм:
1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк.
2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c].
3⃣Верните матрицу ans.
😎 Решение:
class Solution:
def transpose(self, A):
return [[A[r][c] for r in range(len(A))] for c in range(len(A[0]))]
Ставь 👍 и забирай 📚 Базу знаний
💊2
Задача: 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.
👨💻 Алгоритм:
1⃣Рекурсивное решение (solve):
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.
2⃣Рассчёт состояний:
Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1.
Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2.
Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии.
3⃣Минимальное количество камер:
Запустите функцию 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:])
Ставь 👍 и забирай 📚 Базу знаний
🔥1
Задача: 300. Longest Increasing Subsequence
Сложность: medium
Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.
2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).
3⃣Верните максимальное значение из dp.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.
Пример:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
👨💻 Алгоритм:
1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.
2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).
3⃣Верните максимальное значение из dp.
😎 Решение:
class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1209. Remove All Adjacent Duplicates in String II
Сложность: medium
Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе.
Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать.
Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален.
Пример:
👨💻 Алгоритм:
1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов.
2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.
3⃣Вернуть первые j символов строки.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе.
Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать.
Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален.
Пример:
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation:
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"
👨💻 Алгоритм:
1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов.
2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.
3⃣Вернуть первые j символов строки.
😎 Решение:
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
counts = []
sa = list(s)
j = 0
for i in range(len(sa)):
sa[j] = sa[i]
if j == 0 or sa[j] != sa[j - 1]:
counts.append(1)
else:
incremented = counts.pop() + 1
if incremented == k:
j -= k
else:
counts.append(incremented)
j += 1
return "".join(sa[:j])
Ставь 👍 и забирай 📚 Базу знаний
Задача: 827. Making A Large Island
Сложность: hard
Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.
Верните размер самого большого острова в grid после выполнения этой операции.
Остров — это группа 1, соединенных в 4 направлениях.
Пример:
👨💻 Алгоритм:
1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер.
2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1.
3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.
Верните размер самого большого острова в grid после выполнения этой операции.
Остров — это группа 1, соединенных в 4 направлениях.
Пример:
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
👨💻 Алгоритм:
1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер.
2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1.
3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.
😎 Решение:
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
def dfs(r, c, index):
ans = 1
grid[r][c] = index
for nr, nc in neighbors(r, c):
if grid[nr][nc] == 1:
grid[nr][nc] = index
ans += dfs(nr, nc, index)
return ans
def neighbors(r, c):
for dr, dc in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N:
yield nr, nc
N = len(grid)
index = 2
area = [0] * (N * N + 2)
for r in range(N):
for c in range(N):
if grid[r][c] == 1:
area[index] = dfs(r, c, index)
index += 1
ans = max(area)
for r in range(N):
for c in range(N):
if grid[r][c] == 0:
seen = {grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1}
ans = max(a
Ставь 👍 и забирай 📚 Базу знаний
Задача: 987. Vertical Order Traversal of a Binary Tree
Сложность: medium
Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.
Верните пересечение этих двух списков интервалов.
Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.
Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].
Пример:
👨💻 Алгоритм:
1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).
2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).
3⃣Возврат результата:
Отсортировать ключи словаря по col и затем по row.
Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.
Верните пересечение этих двух списков интервалов.
Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.
Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].
Пример:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
👨💻 Алгоритм:
1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).
2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).
3⃣Возврат результата:
Отсортировать ключи словаря по col и затем по row.
Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список.
😎 Решение:
from collections import defaultdict, deque
class Solution:
def verticalTraversal(self, root):
col_table = defaultdict(list)
queue = deque([(root, 0, 0)])
while queue:
node, row, col = queue.popleft()
if node:
col_table[col].append((row, node.val))
queue.append((node.left, row + 1, col - 1))
queue.append((node.right, row + 1, col + 1))
result = []
for col in sorted(col_table.keys()):
col_table[col].sort()
result.append([val for row, val in col_table[col]])
return result
Ставь 👍 и забирай 📚 Базу знаний
Задача: 971. Flip Binary Tree To Match Preorder Traversal
Сложность: medium
Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.
Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:
Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.
Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].
Пример:
👨💻 Алгоритм:
1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1].
2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка.
3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.
Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:
Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.
Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].
Пример:
Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.
👨💻 Алгоритм:
1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1].
2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка.
3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage.
😎 Решение:
class Solution:
def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:
self.flipped = []
self.index = 0
self.voyage = voyage
self.dfs(root)
if self.flipped and self.flipped[0] == -1:
return [-1]
return self.flipped
def dfs(self, node):
if node:
if node.val != self.voyage[self.index]:
self.flipped = [-1]
return
self.index += 1
if self.index < len(self.voyage) and node.left and node.left.val != self.voyage[self.index]:
self.flipped.append(node.val)
self.dfs(node.right)
self.dfs(node.left)
else:
self.dfs(node.left)
self.dfs(node.right)
Ставь 👍 и забирай 📚 Базу знаний
Задача: 423. Reconstruct Original Digits from English
Сложность: medium
Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания.
Пример:
👨💻 Алгоритм:
1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа.
2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры.
3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания.
Пример:
Input: s = "owoztneoer"
Output: "012"
👨💻 Алгоритм:
1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа.
2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры.
3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат.
😎 Решение:
class Solution:
def originalDigits(self, s: str) -> str:
count = collections.Counter(s)
out = [0] * 10
out[0] = count['z']
out[2] = count['w']
out[4] = count['u']
out[6] = count['x']
out[8] = count['g']
out[3] = count['h'] - out[8]
out[5] = count['f'] - out[4]
out[7] = count['s'] - out[6]
out[9] = count['i'] - out[5] - out[6] - out[8]
out[1] = count['n'] - out[7] - 2 * out[9]
output = ''.join(str(i) * out[i] for i in range(10))
return output
Ставь 👍 и забирай 📚 Базу знаний