Python | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
显示更多
网络:9 165
订阅者
-624 小时
-197 天
-7230 天
帖子存档
9 165
Задача: 990. Satisfiability of Equality Equations
Сложность: medium
Дан массив строк equations, представляющий отношения между переменными, где каждая строка equations[i] имеет длину 4 и принимает одну из двух форм: "xi==yi" или "xi!=yi". Здесь xi и yi - это строчные буквы (не обязательно разные), представляющие имена переменных из одной буквы.
Верните true, если возможно назначить целые числа именам переменных таким образом, чтобы удовлетворить всем заданным уравнениям, или false в противном случае.
Пример:
Input: equations = ["b==a","a==b"] Output: true Explanation: We could assign a = 1 and b = 1 to satisfy both equations.👨💻 Алгоритм: 1⃣Создание графа для уравнений "==": Создайте структуру данных для объединения (Union-Find) для обработки уравнений равенства. Пройдите через массив equations и для каждого уравнения типа "xi==yi" объедините соответствующие переменные. 2⃣Проверка уравнений "!=": Пройдите через массив equations и для каждого уравнения типа "xi!=yi" проверьте, принадлежат ли переменные к одной и той же группе в структуре объединения. Если принадлежат, верните false. 3⃣Возврат результата: Если после проверки всех уравнений "xi!=yi" не было обнаружено противоречий, верните true. 😎 Решение:
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
uf = UnionFind(26)
for eq in equations:
if eq[1] == '=':
x = ord(eq[0]) - ord('a')
y = ord(eq[3]) - ord('a')
uf.union(x, y)
for eq in equations:
if eq[1] == '!':
x = ord(eq[0]) - ord('a')
y = ord(eq[3]) - ord('a')
if uf.connected(x, y):
return False
return True
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
self.parent[rootX] = rootY
def connected(self, x, y):
return self.find(x) == self.find(y)9 165
Бесплатная защита от DDoS-атак
📱 DDoS-атаки способны замедлить сайт или полностью вывести его из строя. Особенно это критично в пиковые сезоны или во время распродаж, когда каждая минута простоя сайта равна потерянным клиентам.
👍 AntiDDoS от Solar Space — облачное решение для защиты сайта от DDoS-атак. Бесплатный тариф подходит для небольших ресурсов: сайтов-визиток, сайтов экспертов и корпоративных порталов.
✅ Решение не требует сложных настроек: после активации сервис сразу начинает фильтровать трафик и подавлять атаки.
👌 Подключение занимает всего 20 минут в личном кабинете. Никаких карт, подписок и скрытых платежей.
Попробовать
#реклама 16+
rt-solar.ru
О рекламодателе
9 165
![Задача: 473. Matchsticks to Square Сложность: medium Дано целочисленный массив спичек, где matchsticks[i] — это длина i-й спи](data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDACgcHiMeGSgjISMtKygwPGRBPDc3PHtYXUlkkYCZlo+AjIqgtObDoKrarYqMyP/L2u71////m8H////6/+b9//j/2wBDASstLTw1PHZBQXb4pYyl+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj/wAARCAAoACgDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwDXd1jUsxwB7Zpnnx/7f/fDf4Ul0CYhg4+YD8+P61MBgetAEDXUajJ3fipH86BdRlcnIGM9M/yqcjIwajlAEEmAB8poAeCGAIOQaKbD/qU/3RRQAy5YLEM/3h+hz/SpgcgEd6hucCHngbl/mKU3ESjJbj1AJFAEtR3BxA/0xR58R/5aL/31TJ5ImhYF0I64yOfagB9ucwIfbFFEC7YlGMd8elFAEhGRg1EYIyMbcD0BwKKKAF8mL/nmv5Uvkx/881/KiigB9FFFAH//2Q==)
Задача: 473. Matchsticks to Square
Сложность: medium
Дано целочисленный массив спичек, где matchsticks[i] — это длина i-й спички. Необходимо использовать все спички для создания одного квадрата. Нельзя ломать никакую спичку, но можно соединять их, при этом каждая спичка должна быть использована ровно один раз.
Вернуть true, если можно составить квадрат, и false в противном случае.
Пример:
Input: matchsticks = [1,1,2,2,2] Output: true Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.👨💻 Алгоритм: 1⃣Определяем рекурсивную функцию, которая принимает текущий индекс обрабатываемой спички и количество сторон квадрата, которые уже полностью сформированы. Базовый случай для рекурсии: если все спички использованы и сформировано 4 стороны, возвращаем True. 2⃣Для текущей спички рассматриваем 4 варианта: она может быть частью любой из сторон квадрата. Пробуем каждый из 4 вариантов, вызывая рекурсию для них. 3⃣Если какой-либо из рекурсивных вызовов возвращает True, возвращаем True, в противном случае возвращаем False. 😎 Решение:
class Solution:
def __init__(self):
self.sums = [0] * 4
self.possibleSquareSide = 0
def dfs(self, index):
if index == len(self.nums):
return self.sums[0] == self.sums[1] == self.sums[2] == self.sums[3]
element = self.nums[index]
for i in range(4):
if self.sums[i] + element <= self.possibleSquareSide:
self.sums[i] += element
if self.dfs(index + 1):
return True
self.sums[i] -= element
return False
def makesquare(self, nums):
if not nums:
return False
perimeter = sum(nums)
self.possibleSquareSide = perimeter // 4
if self.possibleSquareSide * 4 != perimeter:
return False
self.nums = sorted(nums, reverse=True)
return self.dfs(0)9 165
Задача: 927. Three Equal Parts
Сложность: hard
Вам дан массив arr, состоящий только из нулей и единиц. Разделите массив на три непустые части так, чтобы все эти части представляли одно и то же двоичное значение. Если это возможно, верните любой [i, j] с i + 1 < j, такой что: arr[0], arr[1], ..., arr[i] - это первая часть, arr[i + 1], arr[i + 2], ...., arr[j - 1] - вторая часть, и arr[j], arr[j + 1], ..., arr[arr.length - 1] - третья часть. Все три части имеют одинаковые двоичные значения. Если это невозможно, верните [-1, -1]. Обратите внимание, что вся часть используется при рассмотрении того, какое двоичное значение она представляет. Например, [1,1,0] представляет 6 в десятичной системе, а не 3. Кроме того, допускаются ведущие нули, поэтому [0,1,1] и [1,1] представляют одно и то же значение.
Пример:
Input: arr = [1,0,1,0,1] Output: [0,3]👨💻 Алгоритм: 1⃣Подсчитать количество единиц в массиве. 2⃣Если количество единиц не делится на три, вернуть [-1, -1]. Найти индексы начала каждой части, игнорируя ведущие нули. Использовать эти индексы для проверки, могут ли три части быть одинаковыми. 3⃣Если три части одинаковы, вернуть соответствующие индексы, иначе вернуть [-1, -1]. 😎 Решение:
def threeEqualParts(arr):
ones = sum(arr)
if ones % 3 != 0:
return [-1, -1]
if ones == 0:
return [0, len(arr) - 1]
part_ones = ones // 3
first = second = third = cnt = 0
for i, val in enumerate(arr):
if val == 1:
if cnt == 0:
first = i
elif cnt == part_ones:
second = i
elif cnt == 2 * part_ones:
third = i
cnt += 1
while third < len(arr) and arr[first] == arr[second] == arr[third]:
first += 1
second += 1
third += 1
if third == len(arr):
return [first - 1, second]
return [-1, -1]9 165
Задача: 929. Unique Email Addresses
Сложность: easy
Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.
Пример:
Input: emails = ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"] Output: 2👨💻 Алгоритм: 1⃣Создать множество для хранения уникальных обработанных адресов электронной почты. 2⃣Для каждого адреса в emails: Разделить адрес на локальное и доменное имя по символу '@'. Обработать локальное имя: Удалить все точки '.'. Обрезать часть после символа '+'. Объединить обработанное локальное имя и доменное имя. Добавить результат в множество уникальных адресов. 3⃣Вернуть количество уникальных адресов в множестве. 😎 Решение:
def numUniqueEmails(emails):
unique_emails = set()
for email in emails:
local, domain = email.split('@')
local = local.split('+')[0].replace('.', '')
unique_emails.add(f"{local}@{domain}")
return len(unique_emails)9 165
Задача: 1245. Tree Diameter
Сложность: medium
Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.
Пример:
Input: edges = [[0,1],[0,2]] Output: 2👨💻 Алгоритм: 1⃣Построение графа: Используем представление графа в виде списка смежности. 2⃣Поиск самой удаленной вершины (DFS1): Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее. 3⃣Поиск диаметра (DFS2): Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:
def treeDiameter(edges):
if not edges:
return 0
from collections import defaultdict
def dfs(node, parent):
max_depth = 0
for neighbor in graph[node]:
if neighbor != parent:
depth = dfs(neighbor, node)
if depth + 1 > max_depth:
max_depth = depth + 1
farthest_node[0] = neighbor
return max_depth
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
farthest_node = [0]
dfs(0, -1)
start_node = farthest_node[0]
farthest_node = [0]
diameter = dfs(start_node, -1)
return diameter9 165
Задача: 256. Paint House
Сложность: medium
Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет.
Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3.
Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее...
Верните минимальную стоимость покраски всех домов.
Пример:
Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10.👨💻 Алгоритм: 1️⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2]. 2️⃣Для каждого дома i от 1 до n-1 обновите значения массива dp: dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]) 3️⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]). 😎 Решение:
class Solution:
def minCost(self, costs: List[List[int]]) -> int:
n = len(costs)
dp = [[0] * 3 for _ in range(n)]
dp[0] = costs[0]
for i in range(1, n):
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])
return min(dp[n-1][0], dp[n-1][1], dp[n-1][2])9 165
9 165
Задача: 861. Score After Flipping Matrix
Сложность: hard
Дан целочисленный массив nums и целое число k. Верните длину самой короткой непустой подмассива nums, сумма которого составляет как минимум k. Если такого подмассива нет, верните -1.
Подмассив — это непрерывная часть массива.
Пример:
Input: nums = [1], k = 1
Output: 1class Solution:
def shortestSubarray(self, A: List[int], K: int) -> int:
N = len(A)
P = [0] * (N + 1)
for i in range(N):
P[i+1] = P[i] + A[i]
ans = N + 1
monoq = deque()
for y in range(len(P)):
while monoq and P[y] <= P[monoq[-1]]:
monoq.pop()
while monoq and P[y] >= P[monoq[0]] + K:
ans = min(ans, y - monoq.popleft())
monoq.append(y)
return ans if ans < N + 1 else -19 165
Задача: 39. Combination Sum
Сложность: medium
Дан массив уникальных целых чисел candidates и целевое целое число target. Верните список всех уникальных комбинаций из candidates, где выбранные числа в сумме дают target. Комбинации можно возвращать в любом порядке.
Одно и то же число может быть выбрано из массива candidates неограниченное количество раз. Две комбинации считаются уникальными, если частота хотя бы одного из выбранных чисел отличается.
Тестовые случаи сгенерированы таким образом, что количество уникальных комбинаций, дающих в сумме target, меньше 150 комбинаций для данного ввода.
Пример:
Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]👨💻 Алгоритм: 1️⃣Как видно, вышеописанный алгоритм обратного отслеживания разворачивается как обход дерева в глубину (DFS - Depth-First Search), который часто реализуется с помощью рекурсии. Здесь мы определяем рекурсивную функцию backtrack(remain, comb, start) (на Python), которая заполняет комбинации, начиная с текущей комбинации (comb), оставшейся суммы для выполнения (remain) и текущего курсора (start) в списке кандидатов. Следует отметить, что сигнатура рекурсивной функции немного отличается в Java, но идея остается той же. 2️⃣Для первого базового случая рекурсивной функции, если remain == 0, то есть мы достигаем желаемой целевой суммы, поэтому мы можем добавить текущую комбинацию в итоговый список. Как другой базовый случай, если remain < 0, то есть мы превышаем целевое значение, мы прекращаем исследование на этом этапе. 3️⃣Помимо вышеупомянутых двух базовых случаев, мы затем продолжаем исследовать подсписок кандидатов, начиная с [start ... n]. Для каждого из кандидатов мы вызываем рекурсивную функцию саму с обновленными параметрами. Конкретно, мы добавляем текущего кандидата в комбинацию. С добавленным кандидатом у нас теперь меньше суммы для выполнения, то есть remain - candidate. Для следующего исследования мы все еще начинаем с текущего курсора start. В конце каждого исследования мы делаем откат, удаляя кандидата из комбинации. 😎 Решение:
class Solution:
def combinationSum(self, candidates, target):
results = []
def backtrack(remain, comb, start):
if remain == 0:
results.append(list(comb))
return
elif remain < 0:
return
for i in range(start, len(candidates)):
comb.append(candidates[i])
backtrack(remain - candidates[i], comb, i)
comb.pop()
backtrack(target, [], 0)
return results9 165
Задача: 994. Rotting Oranges
Сложность: medium
Дан m x n сетка, где каждая ячейка может иметь одно из трех значений:
0, представляющее пустую ячейку,
1, представляющее свежий апельсин,
2, представляющее гнилой апельсин.
Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым.
Верните минимальное количество минут, которые должны пройти, пока в ячейке не останется свежих апельсинов. Если это невозможно, верните -1.
Пример:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.👨💻 Алгоритм: 1⃣Инициализация очереди и подсчет апельсинов: Пройдите по всей сетке, добавьте все гнилые апельсины в очередь и подсчитайте общее количество свежих апельсинов. Если нет свежих апельсинов, верните 0. 2⃣Использование BFS для распространения гнили: Выполняйте BFS, начиная с всех гнилых апельсинов, добавленных в очередь. Каждый раз, когда апельсин становится гнилым, уменьшайте счетчик свежих апельсинов. Если свежих апельсинов больше не осталось, верните текущее количество минут. 3⃣Проверка оставшихся свежих апельсинов: Если после завершения BFS все еще остаются свежие апельсины, верните -1. 😎 Решение:
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
queue = deque()
fresh_count = 0
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 2:
queue.append((i, j))
elif grid[i][j] == 1:
fresh_count += 1
if fresh_count == 0:
return 0
minutes = 0
while queue:
for _ in range(len(queue)):
i, j = queue.popleft()
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]) and grid[ni][nj] == 1:
grid[ni][nj] = 2
fresh_count -= 1
queue.append((ni, nj))
if queue:
minutes += 1
return minutes if fresh_count == 0 else -19 165
Задача: 316. Remove Duplicate Letters
Сложность: medium
Дана строка
s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов.
Пример:
Input: s = "bcabc" Output: "abc"👨💻 Алгоритм: 1⃣Инициализация стека Создайте стек, который будет хранить результат, построенный по мере итерации строки. 2⃣Итерация по строке На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок. 3⃣Удаление символов Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека. 😎 Решение:
class Solution:
def removeDuplicateLetters(self, s) -> str:
stack = []
seen = set()
last_occurrence = {c: i for i, c in enumerate(s)}
for i, c in enumerate(s):
if c not in seen:
while stack and c < stack[-1] and i < last_occurrence[stack[-1]]:
seen.discard(stack.pop())
seen.add(c)
stack.append(c)
return ''.join(stack)9 165
Задача: 359. Logger Rate Limiter
Сложность: easy
Создайте систему логирования, которая получает поток сообщений вместе с их временными метками. Каждое уникальное сообщение должно печататься не чаще, чем раз в 10 секунд (то есть, сообщение, напечатанное во временной метке t, предотвратит печать других идентичных сообщений до временной метки t + 10).
Все сообщения будут приходить в хронологическом порядке. Несколько сообщений могут поступить в одно и то же время.
Реализуйте класс Logger:
Logger() Инициализирует объект логгера.
bool shouldPrintMessage(int timestamp, string message) Возвращает true, если сообщение должно быть напечатано в данной временной метке, в противном случае возвращает false.
Пример:
Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]
Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo"); // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar"); // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo"); // 3 < 11, return false
logger.shouldPrintMessage(8, "bar"); // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21class Logger:
def __init__(self):
self.msg_dict = {}
def should_print_message(self, timestamp: int, message: str) -> bool:
if message not in self.msg_dict or timestamp - self.msg_dict[message] >= 10:
self.msg_dict[message] = timestamp
return True
return False9 165
CRM, которая работает сама
Вам не надо вести базу клиентов вручную. Битрикс24 сам заполняет карточки, напоминает, расшифровывает звонки, находит повторные сделки. Меньше рутины, больше прибыли. Есть бесплатный тариф.
Попробовать
#реклама 16+
bitrix24.ru
О рекламодателе
9 165
Задача: 1160. Find Words That Can Be Formed by Characters
Сложность: easy
Вам дан массив строк words и строка chars.
Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз).
Верните сумму длин всех хороших строк в words.
Пример:
Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
counts = collections.Counter(chars)
ans = 0
for word in words:
wordCount = collections.Counter(word)
good = True
for c, freq in wordCount.items():
if counts[c] < freq:
good = False
break
if good:
ans += len(word)
return ans9 165
Задача: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Сложность: easy
Даны два бинарных дерева: original и cloned, а также ссылка на узел target в оригинальном дереве.
Дерево cloned является копией оригинального дерева.
Верните ссылку на тот же узел в дереве cloned.
Обратите внимание, что вам не разрешается изменять какое-либо из двух деревьев или узел target, и ответ должен быть ссылкой на узел в дереве cloned.
Пример:
Input: tree = [7,4,3,null,null,6,19], target = 3 Output: 3 Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.👨💻 Алгоритм: 1⃣Добавьте корень в очередь. 2⃣Пока очередь не пуста, извлекайте узел из очереди. Если узел является целевым, завершите выполнение. Добавьте сначала левый, затем правый дочерний узел в очередь. 3⃣Верните ссылку на найденный целевой узел. 😎 Решение:
class Solution:
def getTargetCopy(self, original, cloned, target):
queue_o = [original]
queue_c = [cloned]
while queue_o:
node_o = queue_o.pop(0)
node_c = queue_c.pop(0)
if node_o is target:
return node_c
if node_o.left:
queue_o.append(node_o.left)
queue_c.append(node_c.left)
if node_o.right:
queue_o.append(node_o.right)
queue_c.append(node_c.right)
return None9 165
⚡️ В сети начали массово сливать курсы и книги известных онлайн школ по айти
Вот отсортированная база с тонной материала (постепенно пополняется):
(363 видео, 87 книги) — Python
(415 видео, 68 книги) — Frontend
(143 видео, 33 книги) — ИБ/Хакинг
(352 видео, 89 книги) — С/С++/C#
(343 видео, 87 книги) — Java/QA
(176 видео, 32 книги) — Git/Linux
(174 видео, 91 книги) — DevOps
(167 видео, 53 книги) — PHP/1С
(227 видео, 83 книги) — SQL/БД
(114 видео, 77 книги) — Сисадмин
(107 видео, 43 книги) — BA/SA
(181 видео, 32 книги) — Go/Rust
(167 видео, 43 книги) — Kotlin/Swift
(112 видео, 24 книги) — Flutter
(137 видео, 93 книги) — DS/ML
(113 видео, 82 книги) — GameDev
(183 видео, 37 книги) — Дизайн
(136 видео, 33 книги) — PM/HR
Скачивать ничего не нужно — все выложили в Telegram
9 165
Задача: 1276. Number of Burgers with No Waste of Ingredients
Сложность: medium
Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните [].
Пример:
Input: tomatoSlices = 16, cheeseSlices = 7 Output: [1,6]👨💻 Алгоритм: 1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах. 2⃣Решите систему уравнений: 4J + 2S = tomatoSlices J + S = cheeseSlices 3⃣Если решение существует, верните его, иначе верните пустой список. 😎 Решение:
def numOfBurgers(tomatoSlices, cheeseSlices):
if tomatoSlices % 2 != 0 or tomatoSlices < 2 * cheeseSlices or tomatoSlices > 4 * cheeseSlices:
return []
total_jumbo = (tomatoSlices - 2 * cheeseSlices) // 2
total_small = cheeseSlices - total_jumbo
return [total_jumbo, total_small]9 165
Задача: 87. Scramble String
Сложность: hard
Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:
1. Если длина строки равна 1, остановиться.
2. Если длина строки больше 1, выполнить следующее:
- Разделить строку на две непустые подстроки в случайном индексе, например, если строка это s, разделить её на x и y, где s = x + y.
- Случайным образом решить, поменять ли местами две подстроки или оставить их в том же порядке. То есть после этого шага s может стать s = x + y или s = y + x.
- Применить шаг 1 рекурсивно к каждой из двух подстрок x и y.
Для двух строк s1 и s2 одинаковой длины вернуть true, если s2 является перемешанной строкой s1, в противном случае вернуть false.
Пример:
Input: s1 = "great", s2 = "rgeat" Output: true Explanation: One possible scenario applied on s1 is: "great" --> "gr/eat" // divide at random index. "gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order. "gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them. "g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order. "r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t". "r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order. The algorithm stops now, and the result string is "rgeat" which is s2. As one possible scenario led s1 to be scrambled to s2, we return true.👨💻 Алгоритм: 1️⃣- Итерируйте i от 0 до n-1. - Итерируйте j от 0 до n-1. - Установите dp[1][i][j] в булево значение s1[i] == s2[j]. (Базовый случай динамического программирования). 2️⃣- Итерируйте length от 2 до n. - Итерируйте i от 0 до n + 1 - length. - Итерируйте j от 0 до n + 1 - length. 3️⃣- Итерируйте newLength от 1 до length - 1. - Если dp[newLength][i][j] && dp[length-newLength][i+newLength][j+newLength]) || (dp[newLength][i][j+length-newLength] && dp[length-newLength][i+newLength][j]) верно, установите dp[length][i][j] в true. - Верните dp[n][0][0]. 😎 Решение:
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
n = len(s1)
dp = [
[[False for j in range(n)] for i in range(n)] for l in range(n + 1)
]
for i in range(n):
for j in range(n):
dp[1][i][j] = s1[i] == s2[j]
for length in range(2, n + 1):
for i in range(n + 1 - length):
for j in range(n + 1 - length):
for new_length in range(1, length):
dp1 = dp[new_length][i]
dp2 = dp[length - new_length][i + new_length]
dp[length][i][j] |= dp1[j] and dp2[j + new_length]
dp[length][i][j] |= (
dp1[j + length - new_length] and dp2[j]
)
return dp[n][0][0]9 165
Бесплатный курс по дизайну: веб, графический и UX/UI
Получи востребованные навыки:
- создание дизайна сайтов и приложений
- создание инфографики и карточек для маркетплейсов
- работа в графическом редакторе Figma и др.
Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰
Зарегистрироваться
#реклама 16+
ydaev.ru
О рекламодателе
