Python | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Показати більше
8 922
Підписники
-524 години
-477 днів
-12930 днів
Архів дописів
8 922
#hard
Задача: 297. Serialize and Deserialize Binary Tree
Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде.
Разработайте алгоритм для сериализации и десериализации бинарного дерева. Нет ограничений на то, как ваш алгоритм сериализации/десериализации должен работать. Вам нужно просто гарантировать, что бинарное дерево может быть сериализовано в строку, и эта строка может быть десериализована в исходную структуру дерева.
Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы.
Пример:
Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5]👨💻 Алгоритм: 1⃣Сериализация дерева: Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree. Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None". 2⃣Пример: Начните с корня, узел 1, строка сериализации становится "1,". Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,". Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None"). Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,"). 3⃣Десериализация строки: Разделите строку на список значений. Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой. 😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Codec:
def rserialize(self, root, string):
if root is None:
string += "null,"
else:
string += str(root.val) + ","
string = self.rserialize(root.left, string)
string = self.rserialize(root.right, string)
return string
def serialize(self, root):
return self.rserialize(root, "")
def rdeserialize(self, data_list):
if data_list[0] == "null":
data_list.pop(0)
return None
root = TreeNode(int(data_list.pop(0)))
root.left = self.rdeserialize(data_list)
root.right = self.rdeserialize(data_list)
return root
def deserialize(self, data):
data_list = data.split(',')
return self.rdeserialize(data_list)8 922
#medium
Задача: 433. Minimum Genetic Mutation
Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'.
Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке.
Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией.
Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой.
Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1.
Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк.
Пример:
Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"] Output: 1👨💻 Алгоритм: 1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene. 2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen. 3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1. 😎 Решение:
from collections import deque
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
queue = deque([start])
seen = set([start])
steps = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node == end:
return steps
for c in "ACGT":
for i in range(len(node)):
neighbor = node[:i] + c + node[i+1:]
if neighbor not in seen and neighbor in bank:
queue.append(neighbor)
seen.add(neighbor)
steps += 1
return -18 922
#medium
Задача: 298. Binary Tree Longest Consecutive Sequence
Дан корень бинарного дерева, верните длину самого длинного пути последовательных значений.
Путь последовательных значений — это путь, где значения увеличиваются на единицу вдоль пути.
Обратите внимание, что путь может начинаться с любого узла в дереве, и вы не можете перейти от узла к его родителю на пути.
Пример:
Input: root = [1,null,3,2,4,null,null,null,5] Output: 3 Explanation: Longest consecutive sequence path is 3-4-5, so return 3.👨💻 Алгоритм: 1⃣Инициализация и начало обхода: Начните обход дерева с корневого узла. Инициализируйте переменную length, чтобы хранить текущую длину последовательного пути, и передавайте её вниз по дереву. 2⃣Сравнение текущего узла с родительским узлом: Для каждого узла сравните его значение со значением родительского узла. Если значение текущего узла на единицу больше значения родительского узла, увеличьте length. Если значение текущего узла не является последовательным (не больше на единицу), сбросьте length на 1. 3⃣Обход дерева: Рекурсивно обходите левое и правое поддерево, передавая обновлённое значение length. В каждом узле обновляйте максимальную длину последовательного пути, если текущая длина больше. 😎 Решение:
class Solution:
def __init__(self):
self.maxLength = 0
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
self.dfs(root, None, 0)
return self.maxLength
def dfs(self, node: Optional[TreeNode], parent: Optional[TreeNode], length: int) -> None:
if not node:
return
if parent and node.val == parent.val + 1:
length += 1
else:
length = 1
self.maxLength = max(self.maxLength, length)
self.dfs(node.left, node, length)
self.dfs(node.right, node, length)8 922
⚡️ IT-обучение теперь в Telegram!
В cвязи с недавнем замедлением Ютуба — лучшие обучающие каналы переехали в Telegram
Вот каналы для айтишников:
👩💻 Python: @Python
📱 GitHub: @GitHub
👩💻 Frontend: @Frontend
⚙️ Backend: @Backend
🤓 Общее айти: @portalToIT
👩💻 Java: @Java
👩💻 C#: @Csharp
👩💻 С/С++: @Cpp
🖥 Базы Данных & SQL: @SQL
👩💻 Golang: @Golang
👩💻 PHP: @PHP
👩💻 Моб. разработка: @MobDev
👩💻 Разработка игр: @GameDev
👩💻 DevOps: @DevOps
🖥 Data Science: @DataScience
🤔 Хакинг & ИБ: @InfoSec
🐞 Тестирование: @QA
📱 Маркетинг: @Marketing
🖥 Дизайн: @Design
➡️ Сохраняйте себе, чтобы не потерять
8 922
#medium
Задача: 299. Bulls and Cows
Вы играете в игру "Быки и коровы" со своим другом.
Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией:
Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции.
Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками.
Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга.
Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры.
Пример:
Input: secret = "1807", guess = "7810" Output: "1A3B" Explanation: Bulls are connected with a '|' and cows are underlined: "1807" | "7810"👨💻 Алгоритм: 1⃣Инициализация счетчиков: Инициализируйте количество быков и коров значениями ноль. Создайте хеш-таблицу для хранения символов строки secret и их частот. 2⃣Обход строки guess: Для каждого символа ch в строке guess: Если ch присутствует в строке secret: Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]): Увеличьте количество быков: bulls += 1. Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0). Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]): Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0). Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1. 3⃣Возврат результата: Верните количество быков и коров в формате "xAyB". 😎 Решение:
class Solution:
def getHint(self, secret: str, guess: str) -> str:
from collections import defaultdict
h = defaultdict(int)
for ch in secret:
h[ch] += 1
bulls = 0
cows = 0
n = len(guess)
secretArray = list(secret)
guessArray = list(guess)
for idx in range(n):
ch = guessArray[idx]
if ch in h:
if ch == secretArray[idx]:
bulls += 1
if h[ch] <= 0:
cows -= 1
else:
if h[ch] > 0:
cows += 1
h[ch] -= 1
return f"{bulls}A{cows}B"8 922
#medium
Задача: 300. Longest Increasing Subsequence
Дан массив целых чисел 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)8 922
+4
Senior-разработчик создал крутейший канал про SQL
Благодаря простым картинкам даже новичок научится разрабатывать приложения с использованием баз данных.
Присоединяйтесь: @SQL
8 922
#medium
Задача: 395. Longest Substring with At Least K Repeating Characters
Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.
Если такой подстроки не существует, верните 0.
Пример:
Input: s = "aaabb", k = 3 Output: 3 Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.👨💻 Алгоритм: 1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке. 2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой. 3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки. 😎 Решение:
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
if len(s) == 0 or k > len(s):
return 0
n = len(s)
result = 0
for start in range(n):
count_map = [0] * 26
for end in range(start, n):
count_map[ord(s[end]) - ord('a')] += 1
if self.is_valid(count_map, k):
result = max(result, end - start + 1)
return result
def is_valid(self, count_map, k):
count_letters = 0
count_at_least_k = 0
for count in count_map:
if count > 0:
count_letters += 1
if count >= k:
count_at_least_k += 1
return count_letters == count_at_least_k8 922
🔥 Ресурсы для подготовки к работе в IT! 🔥
1️⃣ База собеседований IT – это уникальная коллекция собеседований от реальных топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и многие другие! 🏢 Мы собрали 150+ собеседований, чтобы ты мог подготовиться к интервью с уверенностью и успехом.
2️⃣ База тестовых заданий – твоё секретное оружие для успешного прохождения этапов отбора! 📋 Здесь ты найдёшь 121+ тестовых заданий от тех же топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries. Решай реальные задачи и набирайся опыта для будущих собеседований!
🎯 Присоединяйся к базам и прокачай свои шансы на успешное трудоустройство!
8 922
#medium
Задача: 280. Wiggle Sort
Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....
Вы можете считать, что входной массив всегда имеет допустимый ответ.
Пример:
Input: nums = [3,5,2,1,6,4] Output: [3,5,1,6,2,4] Explanation: [1,6,2,5,3,4] is also accepted.👨💻 Алгоритм: 1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена. 2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 😎 Решение:
class Solution:
def swap(self, nums, i, j):
nums[i], nums[j] = nums[j], nums[i]
def wiggleSort(self, nums):
for i in range(len(nums) - 1):
if (i % 2 == 0 and nums[i] > nums[i + 1]) or (i % 2 == 1 and nums[i] < nums[i + 1]):
self.swap(nums, i, i + 1)
8 922
CodHub теперь в Telegram!
Бесплатные обучающие материалы, которые лучше платных — книги, ресурсы, статьи и курсы топовых вузов страны тут:
👩💻 Материалы по Python
👩💻 Материалы по Frontend
👩💻 Материалы по Java
👩💻 Материалы по С#
👩💻 Материалы по C/C++
👩💻 Материалы по Хакингу
🖥 Материалы по SQL
👩💻 Материалы по Kotlin/Swift
👩💻 Материалы по Linux
🐞 Материалы по QA
👩💻 Материалы по Go
👩💻 Материалы по PHP
Подписываетесь: @CodHub_tg
8 922
#hard
Задача: 301. Remove Invalid Parentheses
Дана строка s, содержащая скобки и буквы. Удалите минимальное количество неверных скобок, чтобы сделать строку допустимой.
Верните список уникальных строк, которые являются допустимыми с минимальным количеством удалений. Вы можете вернуть ответ в любом порядке.
Пример:
Input: s = "()())()" Output: ["(())()","()()()"]👨💻 Алгоритм: 1⃣Инициализация: Инициализируйте массив, который будет хранить все допустимые выражения. Начните рекурсию с самой левой скобки в последовательности и двигайтесь вправо. Определите состояние рекурсии переменной index, представляющей текущий обрабатываемый индекс в исходном выражении. Также используйте переменные left_count и right_count для отслеживания количества добавленных левых и правых скобок соответственно. 2⃣Обработка текущего символа: Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии. Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения. 3⃣Завершение рекурсии и проверка: Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны). Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор. Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в массив допустимых выражений. 😎 Решение:
class Solution:
def __init__(self):
self.valid_expressions = set()
self.minimum_removed = float('inf')
def reset(self):
self.valid_expressions.clear()
self.minimum_removed = float('inf')
def recurse(self, s, index, left_count, right_count, expression, removed_count):
if index == len(s):
if left_count == right_count:
if removed_count <= self.minimum_removed:
possible_answer = "".join(expression)
if removed_count < self.minimum_removed:
self.valid_expressions.clear()
self.minimum_removed = removed_count
self.valid_expressions.add(possible_answer)
return
current_character = s[index]
length = len(expression)
if current_character != '(' and current_character != ')':
expression.append(current_character)
self.recurse(s, index + 1, left_count, right_count, expression, removed_count)
expression.pop()
else:
self.recurse(s, index + 1, left_count, right_count, expression, removed_count + 1)
expression.append(current_character)
if current_character == '(':
self.recurse(s, index + 1, left_count + 1, right_count, expression, removed_count)
elif right_count < left_count:
self.recurse(s, index + 1, left_count, right_count + 1, expression, removed_count)
expression.pop()
def removeInvalidParentheses(self, s: str) -> [str]:
self.reset()
self.recurse(s, 0, 0, 0, [], 0)
return list(self.valid_expressions)8 922
#medium
Задача: 394. Decode String
Дана закодированная строка, вернуть её декодированную версию.
Правило кодирования следующее: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.
Можно предположить, что входная строка всегда допустима; нет лишних пробелов, квадратные скобки корректно сформированы и т.д. Более того, можно предположить, что исходные данные не содержат никаких цифр, и что цифры используются только для обозначения количества повторений, k. Например, не будет таких входных данных, как 3a или 2[4].
Тестовые случаи сгенерированы так, что длина выходной строки никогда не превысит 105.
Пример:
Input: s = "3[a]2[bc]" Output: "aaabcbc"👨💻 Алгоритм: 1⃣Проходите по строке s и обрабатывайте каждый символ. Если текущий символ не является закрывающей скобкой ], поместите его в стек. 2⃣Если текущий символ является закрывающей скобкой ], начните декодировать последнюю пройденную строку. Извлекайте из стека символы, пока следующий символ не станет открывающей скобкой [, и добавляйте каждый символ (a-z) к decodedString. Затем извлеките открывающую скобку [ из стека и извлекайте символы, пока следующий символ является цифрой (0-9), чтобы собрать число k. 3⃣Декодируйте шаблон k[decodedString], помещая decodedString в стек k раз. После того как вся строка будет пройдена, извлеките результат из стека и верните его. 😎 Решение:
class Solution:
def decodeString(self, s: str) -> str:
stack = []
for char in s:
if char != ']':
stack.append(char)
else:
decoded_string = ''
while stack[-1] != '[':
decoded_string = stack.pop() + decoded_string
stack.pop()
k = 0
base = 1
while stack and stack[-1].isdigit():
k = k + int(stack.pop()) * base
base *= 10
stack.append(decoded_string * k)
return ''.join(stack)8 922
🌟✨ ФРИЛАНС = СВОБОДА ✨🌟
Забудь о 9-18 и офисных буднях!!!
Фриланс — это твой путь к независимости и творчеству! 🎨💻
Работай тогда, когда тебе удобно, и откуда угодно! 🏖️🌍 Не знаешь, как начать?
У нас есть всё, что нужно:
-советы
-вакансии
-поддержка
Ты мастер своего времени: выбирай проекты, которые вдохновляют! 💪💫 Получай достойный доход, реализуя свои идеи и мечты.
Присоединяйся к нашему каналу и найдите свою свободу с фрилансом уже сегодня! 🚀👩💻
Фриланс=Свобода
8 922
#medium
Задача: 393. UTF-8 Validation
Дан целочисленный массив data, представляющий данные, верните, является ли это допустимой UTF-8 кодировкой (т.е. переводится в последовательность допустимых UTF-8 закодированных символов).
Символ в UTF-8 может быть от 1 до 4 байтов в длину, при этом соблюдаются следующие правила:
Для 1-байтового символа первый бит — 0, за которым следует его Unicode код.
Для n-байтового символа первые n битов — все единицы, (n + 1)-й бит — 0, за которыми следуют n - 1 байт с наиболее значимыми 2 битами, равными 10.
Это работает следующим образом:
Количество байтов | UTF-8 Октетная последовательность
| (бинарная)
--------------------+-----------------------------------------
1 | 0xxxxxxx
2 | 110xxxxx 10xxxxxx
3 | 1110xxxx 10xxxxxx 10xxxxxx
4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
x обозначает бит в бинарной форме байта, который может быть как 0, так и 1.
Примечание: Вход представляет собой массив целых чисел. Используются только 8 младших значимых битов каждого целого числа. Это означает, что каждое целое число представляет только 1 байт данных.
Пример:
Input: data = [197,130,1] Output: true Explanation: data represents the octet sequence: 11000101 10000010 00000001. It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.👨💻 Алгоритм: 1⃣Начните обработку целых чисел в данном массиве одно за другим. Для каждого целого числа получите его двоичное представление в виде строки. Поскольку целые числа могут быть очень большими, следует учитывать только 8 младших значимых битов данных и отбросить остальные, как указано в условии задачи. После этого шага у вас должно быть 8-битное или 1-байтовое строковое представление целого числа. Назовем эту строку bin_rep. 2⃣Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа. 3⃣Продолжайте обрабатывать целые числа массива таким образом, пока не обработаете их все или не обнаружите недопустимый сценарий. Теперь давайте перейдем к реализации этого алгоритма. 😎 Решение:
class Solution:
def validUtf8(self, data):
n_bytes = 0
for num in data:
bin_rep = format(num, '#010b')[-8:]
if n_bytes == 0:
for bit in bin_rep:
if bit == '0': break
n_bytes += 1
if n_bytes == 0:
continue
if n_bytes == 1 or n_bytes > 4:
return False
else:
if not (bin_rep[0] == '1' and bin_rep[1] == '0'):
return False
n_bytes -= 1
return n_bytes == 08 922
#easy
Задача: 392. Is Subsequence
Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false.
Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является).
Пример:
Input: s = "abc", t = "ahbgdc" Output: true👨💻 Алгоритм: 1⃣Назначьте два указателя: левый для исходной строки и правый для целевой строки. Эти указатели будут использоваться для итерации по строкам и сравнения их символов. 2⃣Перемещайте указатели в зависимости от совпадения символов. Если символы на текущих позициях указателей совпадают, переместите оба указателя на один шаг вперед. Если символы не совпадают, переместите только правый указатель целевой строки. 3⃣Итерация завершается, когда один из указателей выходит за пределы своей строки. Если в конце итерации все символы исходной строки были найдены в целевой строке, исходная строка является подпоследовательностью целевой строки. 😎 Решение:
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
left_bound, right_bound = len(s), len(t)
p_left, p_right = 0, 0
while p_left < left_bound and p_right < right_bound:
if s[p_left] == t[p_right]:
p_left += 1
p_right += 1
return p_left == left_bound8 922
👩💻 Python: @python_ready
👩💻 Java: @java_ready
📖 Общее IT: @roadmap_ready
👩💻 Frontend: @code_ready
👩💻 Backend: @backend_ready
🖥 Базы Данных & SQL: @sql_ready
👩💻 C#: @csharp_ready
👩💻 C/C++: @cpp_ready
📋 IT Архив: @archive_ready
🖥 Design: @time_design
8 922
#easy
Задача: 290. Word Pattern
Дан шаблон и строка s, необходимо определить, следует ли строка s этому шаблону.
Здесь "следует" означает полное соответствие, такое что существует биекция между буквой в шаблоне и непустым словом в строке s.
Пример:
Input: pattern = "abba", s = "dog cat cat dog" Output: true👨💻 Алгоритм: 1⃣Разделение строки на слова: Разделите строку s на отдельные слова. Если количество слов не равно длине шаблона, возвращаем false. 2⃣Создание отображений: Создайте два словаря: один для отображения букв шаблона на слова, другой для слов на буквы шаблона. 3⃣Проверка биекции: Пройдите по каждому символу шаблона и соответствующему слову. Если символ уже в словаре и не соответствует текущему слову или слово уже в словаре и не соответствует текущему символу, возвращаем false. Иначе добавляем символ и слово в словари и продолжаем проверку. Если все проверки пройдены, возвращаем true. 😎 Решение:
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
map_char = {}
map_word = {}
words = s.split()
if len(words) != len(pattern):
return False
for c, w in zip(pattern, words):
if c not in map_char:
if w in map_word:
return False
else:
map_char[c] = w
map_word[w] = c
else:
if map_char[c] != w:
return False
return True8 922
#easy
Задача: 389. Find the Difference
Даны две строки s и t.
Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию.
Верните букву, которая была добавлена в t.
Пример:
Input: s = "abcd", t = "abcde" Output: "e" Explanation: 'e' is the letter that was added.👨💻 Алгоритм: 1⃣Отсортируйте строки s и t. 2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s. 3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время. 😎 Решение:
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
sorted_s = sorted(s)
sorted_t = sorted(t)
for i in range(len(sorted_s)):
if sorted_s[i] != sorted_t[i]:
return sorted_t[i]
return sorted_t[len(sorted_s)]8 922
#hard
Задача: 369. Plus One Linked List
Дано неотрицательное целое число, представленное в виде связного списка цифр. Добавить к этому числу единицу.
Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.
Пример:
Input: head = [1,2,3] Output: [1,2,4]👨💻 Алгоритм: 1️⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти. 2️⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль. 3️⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next). 😎 Решение:
class Solution:
def plusOne(self, head: ListNode) -> ListNode:
# sentinel head
sentinel = ListNode(0)
sentinel.next = head
not_nine = sentinel
# find the rightmost not-nine digit
while head:
if head.val != 9:
not_nine = head
head = head.next
# increase this rightmost not-nine digit by 1
not_nine.val += 1
not_nine = not_nine.next
# set all the following nines to zeros
while not_nine:
not_nine.val = 0
not_nine = not_nine.next
return sentinel if sentinel.val else sentinel.nextInput: head = [1,2,3] Output: [1,2,4]👨💻 Алгоритм: 1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти. 2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль. 3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next). 😎 Решение:
class Solution:
def plusOne(self, head: ListNode) -> ListNode:
# sentinel head
sentinel = ListNode(0)
sentinel.next = head
not_nine = sentinel
# find the rightmost not-nine digit
while head:
if head.val != 9:
not_nine = head
head = head.next
# increase this rightmost not-nine digit by 1
not_nine.val += 1
not_nine = not_nine.next
# set all the following nines to zeros
while not_nine:
not_nine.val = 0
not_nine = not_nine.next
return sentinel if sentinel.val else sentinel.next