Python | LeetCode
Kanalga Telegram’da o‘tish
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Ko'proq ko'rsatish
Tarmoq:8 953
Obunachilar
-624 soatlar
-347 kun
-11030 kun
Postlar arxiv
8 953
Задача: 1441. Build an Array With Stack Operations
Сложность: medium
Вам дан целочисленный массив target и целое число n.
У вас есть пустой стек с двумя следующими операциями:
"Push": добавляет целое число на вершину стека.
"Pop": удаляет целое число с вершины стека.
Также у вас есть поток целых чисел в диапазоне [1, n].
Используйте две операции стека, чтобы сделать числа в стеке (от нижнего к верхнему) равными target. Вы должны следовать следующим правилам:
Если поток чисел не пуст, возьмите следующее целое число из потока и поместите его на вершину стека.
Если стек не пуст, извлеките целое число с вершины стека.
Если в любой момент элементы в стеке (от нижнего к верхнему) равны target, не берите новые числа из потока и не выполняйте больше операций со стеком.
Верните операции стека, необходимые для построения target согласно указанным правилам. Если существует несколько правильных ответов, верните любой из них.
Пример:
Input: target = [1,3], n = 3 Output: ["Push","Push","Pop","Push"] Explanation: Initially the stack s is empty. The last element is the top of the stack. Read 1 from the stream and push it to the stack. s = [1]. Read 2 from the stream and push it to the stack. s = [1,2]. Pop the integer on the top of the stack. s = [1]. Read 3 from the stream and push it to the stack. s = [1,3].👨💻 Алгоритм: 1⃣Инициализировать пустой список ans и переменную i равной 0. 2⃣Для каждого элемента num в target: Пока i < num - 1: Добавить "Push" в ans. Добавить "Pop" в ans. Увеличить i. Добавить "Push" в ans. Увеличить i. 3⃣Вернуть ans. 😎 Решение:
class Solution:
def buildArray(self, target: List[int], n: int) -> List[str]:
ans = []
i = 0
for num in target:
while i < num - 1:
ans.append("Push")
ans.append("Pop")
i += 1
ans.append("Push")
i += 1
return ans8 953
Задача: 1347. Minimum Number of Steps to Make Two Strings Anagram
Сложность: medium
Даны две строки одинаковой длины s и t. За один шаг вы можете выбрать любой символ строки t и заменить его другим символом.
Вернуть минимальное количество шагов, чтобы сделать t анаграммой строки s.
Анаграмма строки — это строка, которая содержит те же символы в другом (или том же) порядке.
Пример:
Input: s = "bab", t = "aba" Output: 1 Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.👨💻 Алгоритм: 1⃣Вычислить разницу частот символов в строках t и s, сохраняя результаты в массиве count. 2⃣Подсчитать количество символов, которые нужно заменить в t, добавляя в ans только положительные значения из массива count. 3⃣Вернуть ans как минимальное количество шагов для превращения t в анаграмму строки s. 😎 Решение:
class Solution:
def minSteps(self, s: str, t: str) -> int:
count = [0] * 26
for i in range(len(s)):
count[ord(t[i]) - ord('a')] += 1
count[ord(s[i]) - ord('a')] -= 1
ans = 0
for i in range(26):
ans += max(0, count[i])
return ans8 953
Бесплатный курс по дизайну: веб, графический и UX/UI
Научись создавать дизайн сайтов и приложений, инфографику для карточек на маркетплейсах и работать в Figma!
Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰
Этот курс для тебя, если ты:
✅ мечтаешь о новой профессии в digital, но не знаешь, с чего начать;
✅ чувствуешь, что хочешь большего — свободы, самореализации, творчества;
✅ полный новичок и хочешь систему, а не хаос;
✅ хочешь начать зарабатывать удалённо.
Зарегистрироваться
#реклама 16+
ydaev.ru
О рекламодателе
8 953
Задача: 859. Buddy Strings
Сложность: easy
Даны две строки s и goal. Верните true, если вы можете поменять местами две буквы в s так, чтобы результат был равен goal, в противном случае верните false.
Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].
Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".
Пример:
Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.class Solution:
def buddyStrings(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
if s == goal:
freq = {}
for ch in s:
if ch in freq:
return True
freq[ch] = 1
return False
firstIndex = -1
secondIndex = -1
for i in range(len(s)):
if s[i] != goal[i]:
if firstIndex == -1:
firstIndex = i
elif secondIndex == -1:
secondIndex = i
else:
return False
return secondIndex != -1 and \
s[firstIndex] == goal[secondIndex] and \
s[secondIndex] == goal[firstIndex]8 953
Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля
Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰
Научись ей бесплатно!
- Бесплатный доступ
- Разбор ДЗ от наставника
- Мощные кейсы в портфолио
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе
8 953
Repost from easyoffer
⏳ 90 акционных мест
Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу
🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях
🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов
🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме
🔥 Экономь время с помощью автоматических откликов
🔥 Подготовься идеально к интервью с тренажёрами и симуляторами
Успей забрать место по акции: 👉 https://easyoffer.ru/pro
8 953
Задача: 85. Maximal Rectangle
Сложность: hard
Дана бинарная матрица размером rows x cols, заполненная 0 и 1. Найдите наибольший прямоугольник, содержащий только 1, и верните его площадь.
Пример:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 6 Explanation: The maximal rectangle is shown in the above picture.👨💻 Алгоритм: 1️⃣Вычисление максимальной ширины прямоугольника для каждой координаты: Для каждой ячейки в каждой строке сохраняем количество последовательных единиц. При прохождении по строке обновляем максимально возможную ширину в этой точке, используя формулу row[i] = row[i - 1] + 1, если row[i] == '1'. 2️⃣Определение максимальной площади прямоугольника с нижним правым углом в данной точке: При итерации вверх по столбцу максимальная ширина прямоугольника от исходной точки до текущей точки является минимальным значением среди всех максимальных ширин, с которыми мы сталкивались. Используем формулу maxWidth = min(maxWidth, widthHere) и curArea = maxWidth * (currentRow - originalRow + 1), затем обновляем maxArea = max(maxArea, curArea). 3️⃣Применение алгоритма для каждой точки ввода для глобального максимума: Преобразуя входные данные в набор гистограмм, где каждый столбец является новой гистограммой, мы вычисляем максимальную площадь для каждой гистограммы. 😎 Решение:
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
maxarea = 0
dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == "0":
continue
width = dp[i][j] = dp[i][j - 1] + 1 if j else 1
for k in range(i, -1, -1):
width = min(width, dp[k][j])
maxarea = max(maxarea, width * (i - k + 1))
return maxarea8 953
Месяц игр в RuStore
Любите мобильные игры? Тогда загляните в RuStore ⚡
В течение всего месяца вас ждут эксклюзивные скидки от 30% и промокоды в популярных играх.
RPG, стратегии, гонки, головоломки, казуалки — в сторе доступно более 40 000 игр от российских и зарубежных разработчиков.
Игры и бонусы уже ждут вас — переходите, загружайте и побеждайте.
Перейти на сайт
#реклама 16+
rustore.ru
О рекламодателе
8 953
Задача: 298. Binary Tree Longest Consecutive Sequence
Сложность: medium
Дан корень бинарного дерева, верните длину самого длинного пути последовательных значений.
Путь последовательных значений — это путь, где значения увеличиваются на единицу вдоль пути.
Обратите внимание, что путь может начинаться с любого узла в дереве, и вы не можете перейти от узла к его родителю на пути.
Пример:
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 953
Задача: 1337. The K Weakest Rows in a Matrix
Сложность: easy
Вам дана бинарная матрица размером m x n mat, состоящая из 1 (представляющих солдат) и 0 (представляющих гражданских лиц). Солдаты расположены перед гражданскими лицами. То есть, все 1 будут расположены слева от всех 0 в каждой строке.
Строка i слабее строки j, если выполнено одно из следующих условий:
Количество солдат в строке i меньше, чем в строке j.
Обе строки имеют одинаковое количество солдат, но i < j.
Верните индексы k самых слабых строк в матрице, упорядоченных от самой слабой к самой сильной.
Пример:
Input: mat =
[[1,1,0,0,0],
[1,1,1,1,0],
[1,0,0,0,0],
[1,1,0,0,0],
[1,1,1,1,1]],
k = 3
Output: [2,0,3]
Explanation:
The number of soldiers in each row is:
- Row 0: 2
- Row 1: 4
- Row 2: 1
- Row 3: 2
- Row 4: 5
The rows ordered from weakest to strongest are [2,0,3,1,4].class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
m = len(mat)
n = len(mat[0])
pairs = []
for i in range(m):
strength = 0
for j in range(n):
if mat[i][j] == 0:
break
strength += 1
pairs.append((strength, i))
pairs.sort()
indexes = [pairs[i][1] for i in range(k)]
return indexes8 953
Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed
Сложность: hard
RandomizedCollection — это структура данных, содержащая набор чисел, возможно с дубликатами (т.е. мультимножество). Она должна поддерживать вставку и удаление определенных элементов, а также предоставление случайного элемента.
Реализуйте класс RandomizedCollection:
RandomizedCollection(): Инициализирует пустой объект RandomizedCollection.
bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае.
bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них.
int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество.
Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени.
Пример:
Input ["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"] [[], [1], [1], [2], [], [1], []] Output [null, true, false, true, 2, true, 1]👨💻 Алгоритм: 1⃣Создать словарь для хранения значений и их индексов в списке, а также список для хранения всех элементов мультимножества. 2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае. Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае. 3⃣Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента. 😎 Решение:
import random
from collections import defaultdict
class RandomizedCollection:
def __init__(self):
self.dict = defaultdict(set)
self.list = []
def insert(self, val: int) -> bool:
self.dict[val].add(len(self.list))
self.list.append(val)
return len(self.dict[val]) == 1
def remove(self, val: int) -> bool:
if not self.dict[val]:
return False
index = self.dict[val].pop()
last_element = self.list[-1]
self.list[index] = last_element
self.dict[last_element].add(index)
self.dict[last_element].discard(len(self.list) - 1)
self.list.pop()
if not self.dict[val]:
del self.dict[val]
return True
def getRandom(self) -> int:
return random.choice(self.list)8 953
Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium
Даны 2 целых числа n и start. Ваша задача - вернуть любую перестановку p из (0,1,2.....,2^n -1) такую, что : p[0] = start p[i] и p[i+1] отличаются только одним битом в их двоичном представлении. p[0] и p[2^n -1] также должны отличаться только одним битом в их двоичном представлении.
Пример:
Input: n = 2, start = 3 Output: [3,2,0,1]👨💻 Алгоритм: 1⃣Генерация Грей-кода: Генерация Грей-кода для чисел от 0 до 2𝑛−1 2⃣Определение начальной позиции: Находим индекс числа start в последовательности Грей-кода. 3⃣Построение перестановки: Формируем перестановку, начиная с числа start и следуя по циклическому Грей-коду. 😎 Решение:
def grayCode(n):
return [i ^ (i >> 1) for i in range(1 << n)]
def circularPermutation(n, start):
gray = grayCode(n)
start_index = gray.index(start)
return gray[start_index:] + gray[:start_index]8 953
SOC Forum 2025 онлайн — все профи ИБ в одном месте
📅 18–20 ноября пройдет ключевое событие
Недели кибербезопасности — SOC Forum.
👍 Ведущие эксперты соберутся, чтобы обсудить самые острые темы и представить лучшие практические кейсы: каждый доклад прошел строгий отбор, так что вас ждет концентрат пользы.
⚡ Станьте частью форума даже онлайн!
Помимо прямой трансляции лекций, для удаленных участников будут работать «Кибербез ТВ» и радиостанция «ЭХО лОСЕЙ» — с новостными дайджестами, эксклюзивными интервью, мастер-классами и специальными сюжетами, доступными только в онлайн-формате.
✅ Зарегистрируйтесь, и мы пришлем напоминание перед стартом.
Зарегистрироваться
#реклама 16+
registration.forumsoc.ru
О рекламодателе
8 953
Задача: 217. Contains Duplicate
Сложность: easy
Дан массив целых чисел nums. Верните true, если любое значение появляется в массиве хотя бы дважды, и верните false, если каждый элемент уникален.
Пример:
Input: nums = [1,2,3,4] Output: false👨💻 Алгоритм: 1️⃣Отсортируйте массив nums по возрастанию. 2️⃣Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим. 3️⃣Если любое число совпадает с следующим, верните true. Если цикл завершится без совпадений, верните false. 😎 Решение:
def containsDuplicate(nums):
nums.sort()
for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
return True
return False8 953
Задача: 268. Missing Number
Сложность: easy
Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.
Пример:
Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.👨💻 Алгоритм: 1️⃣Сначала отсортируйте массив nums. 2️⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце. 3️⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число. 😎 Решение:
class Solution:
def missingNumber(self, nums):
nums.sort()
if nums[-1] != len(nums):
return len(nums)
elif nums[0] != 0:
return 0
for i in range(1, len(nums)):
expected_num = nums[i - 1] + 1
if nums[i] != expected_num:
return expected_num
return -18 953
Станьте разработчиком нейро-сотрудников на Python и зарабатывайте от 150.000р в месяц 🔥🔥🔥
Мы научим вас создавать топовых нейро-сотрудников на базе GPT-4 Omni, и вы сможете:
1️⃣ Устроиться разработчиком в крупную компанию и зарабатывать от 150 тысяч ₽ в месяц
2️⃣ Разрабатывать такие проекты на заказ и зарабатывать от 500 тысяч ₽ за проект
3️⃣ Создать нейро-сотрудника в вашей компании и вырасти на +30-100% в зарплате
Что будет на интенсиве?
🧬 Теория: как создаются нейро-сотрудники с GPT-4o на Python
🧬 Практика: мы создадим нейро-консультанта, нейро-HR, нейро-маркетолога и др.
Ведущий интенсива - Senior AI разработчик нейросетей и основатель Университета искусственного интеллекта
🔥 Регистрируйтесь на бесплатный интенсив! Встречаемся в ближайший четверг!
8 953
Реклама для бизнеса любого уровня в Яндекс Директе
Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌
Начните прямо сейчас ⚡
Зарегистрироваться
#реклама
direct.yandex.ru
О рекламодателе
8 953
Задача: 112. Path Sum
Сложность: easy
Дан корень бинарного дерева и целое число targetSum. Верните true, если в дереве существует путь от корня до листа, такой, что сумма всех значений вдоль пути равна targetSum.
Лист — это узел без детей.
Пример:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown.👨💻 Алгоритм: 1️⃣Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val. 2️⃣Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом. 3️⃣Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами. 😎 Решение:
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
de = [
(root, sum - root.val),
]
while de:
node, curr_sum = de.pop()
if not node.left and not node.right and curr_sum == 0:
return True
if node.right:
de.append((node.right, curr_sum - node.right.val))
if node.left:
de.append((node.left, curr_sum - node.left.val))
return False8 953
Запустите рекламу в телеграм-каналах с Яндекс Директом
Перфоманс-реклама теперь в телеграм-каналах ⚡
Яндекс Директ знает, как привлечь целевую аудиторию 💰👌
Попробовать
#реклама
yandex.ru
О рекламодателе
8 953
Задача: 736. Parse Lisp Expression
Сложность: hard
Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.
Пример:
Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))" Output: 14👨💻 Алгоритм: 1⃣Определите функцию для оценки выражений. 2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных). 3⃣Используйте словарь для отслеживания значений переменных с учетом области видимости. 😎 Решение:
class Solution:
def evaluate(self, expression: str) -> int:
def evaluate(expression, env):
if expression[0] != '(':
if expression[0].isalpha():
return env[expression]
return int(expression)
tokens = tokenize(expression)
if tokens[0] == 'let':
for i in range(1, len(tokens) - 2, 2):
env[tokens[i]] = evaluate(tokens[i + 1], env)
return evaluate(tokens[-1], env)
elif tokens[0] == 'add':
return evaluate(tokens[1], env) + evaluate(tokens[2], env)
elif tokens[0] == 'mult':
return evaluate(tokens[1], env) * evaluate(tokens[2], env)
def tokenize(expression):
tokens, token, parens = [], '', 0
for char in expression:
if char == '(':
parens += 1
if parens == 1:
continue
elif char == ')':
parens -= 1
if parens == 0:
tokens.append(tokenize(token))
token = ''
continue
elif char == ' ' and parens == 1:
if token:
tokens.append(token)
token = ''
continue
token += char
if token:
tokens.append(token)
return tokens
return evaluate(expression, {})