Python | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر
شبکه:9 162
مشترکین
-624 ساعت
-197 روز
-7230 روز
آرشیو پست ها
9 162
Задача: 251. Flatten 2D Vector
Сложность: medium
Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.
Реализуйте класс Vector2D:
Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.
Пример:
Input ["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"] [[[[1, 2], [3], [4]]], [], [], [], [], [], [], []] Output [null, 1, 2, 3, true, true, 4, false] Explanation Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]); vector2D.next(); // return 1 vector2D.next(); // return 2 vector2D.next(); // return 3 vector2D.hasNext(); // return True vector2D.hasNext(); // return True vector2D.next(); // return 4 vector2D.hasNext(); // return False👨💻 Алгоритм: 1️⃣Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента. 2️⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае. 3️⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next(). 😎 Решение:
class Vector2D:
def __init__(self, v):
self.nums = [num for inner_list in v for num in inner_list]
self.position = -1
def next(self):
self.position += 1
return self.nums[self.position]
def hasNext(self):
return self.position + 1 < len(self.nums)9 162
Задача: 907. Sum of Subarray Minimums
Сложность: medium
Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.
Пример:
Input: arr = [3,1,2,4] Output: 17👨💻 Алгоритм: 1⃣Использовать монотонный стек для нахождения ближайшего меньшего элемента слева и справа для каждого элемента массива. 2⃣Использовать эту информацию для вычисления количества подмассивов, где каждый элемент является минимальным. 3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7. 😎 Решение:
def sumSubarrayMins(arr):
MOD = 10**9 + 7
n = len(arr)
left = [0] * n
right = [0] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
left[i] = i + 1 if not stack else i - stack[-1]
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
right[i] = n - i if not stack else stack[-1] - i
stack.append(i)
result = sum(a * l * r for a, l, r in zip(arr, left, right)) % MOD
return result9 162
Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard
У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: steps = 3, arrLen = 2 Output: 4👨💻 Алгоритм: 1⃣Инициализируйте массив для хранения количества способов достижения каждого индекса на каждом шаге. 2⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге. 3⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге. 😎 Решение:
def numWays(steps, arrLen):
mod = 10**9 + 7
max_pos = min(arrLen - 1, steps)
dp = [0] * (max_pos + 1)
dp[0] = 1
for _ in range(steps):
new_dp = [0] * (max_pos + 1)
for i in range(max_pos + 1):
new_dp[i] = dp[i] % mod
if i > 0:
new_dp[i] = (new_dp[i] + dp[i - 1]) % mod
if i < max_pos:
new_dp[i] = (new_dp[i] + dp[i + 1]) % mod
dp = new_dp
return dp[0]9 162
Repost from Идущий к IT
🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной
📺 Видео: https://youtu.be/G_FOwEGPwlw
9 162
Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium
Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.
Пример:
Input: s = "havefunonleetcode", k = 5 Output: 6 Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.👨💻 Алгоритм: 1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов. 2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s: Для каждого индекса i: Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа. Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот. Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию. Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1. 3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k. 😎 Решение:
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
if k > 26:
return 0
n = len(s)
answer = 0
for i in range(n - k + 1):
freq = [0] * 26
is_unique = True
for j in range(i, i + k):
freq[ord(s[j]) - ord('a')] += 1
if freq[ord(s[j]) - ord('a')] > 1:
is_unique = False
break
if is_unique:
answer += 1
return answer9 162
Задача: 740. Delete and Earn
Сложность: medium
Вам дан целочисленный массив nums. Вы хотите максимизировать количество очков, выполнив следующую операцию любое количество раз: Выберите любой элемент nums[i] и удалите его, чтобы заработать nums[i] очков. После этого вы должны удалить каждый элемент, равный nums[i] - 1, и каждый элемент, равный nums[i] + 1. Верните максимальное количество очков, которое вы можете заработать, применив вышеуказанную операцию некоторое количество раз.
Пример:
Input: nums = [3,4,2] Output: 6👨💻 Алгоритм: 1⃣Подсчитайте количество каждого числа в массиве nums. 2⃣Используйте динамическое программирование для расчета максимальных очков, которые можно заработать, используя накопленный результат для чисел, меньших текущего. Добавьте текущий день в стек. 3⃣Для каждого числа num в nums, учитывайте два случая: не брать число или взять число и добавить его очки. 😎 Решение:
def deleteAndEarn(nums):
from collections import Counter
count = Counter(nums)
prev = None
avoid = using = 0
for num in sorted(count):
if num - 1 != prev:
new_avoid, new_using = max(avoid, using), num * count[num] + max(avoid, using)
else:
new_avoid, new_using = max(avoid, using), num * count[num] + avoid
avoid, using = new_avoid, new_using
prev = num
return max(avoid, using)9 162
Задача: 849. Maximize Distance to Closest Person
Сложность: medium
Вам дан массив, представляющий ряд сидений, где seats[i] = 1 означает, что на i-м месте сидит человек, а seats[i] = 0 означает, что i-е место пусто (индексация с нуля).
Есть по крайней мере одно пустое место и по крайней мере один человек, сидящий на месте.
Алекс хочет сесть на такое место, чтобы расстояние между ним и ближайшим к нему человеком было максимальным.
Верните это максимальное расстояние до ближайшего человека.
Пример:
Input: seats = [1,0,0,0,1,0,1] Output: 2 Explanation: If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2. If Alex sits in any other open seat, the closest person has distance 1. Thus, the maximum distance to the closest person is 2.👨💻 Алгоритм: 1⃣Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i. 2⃣Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места. 3⃣Найдите и верните максимальное расстояние до ближайшего занятого места. 😎 Решение:
class Solution:
def maxDistToClosest(self, seats: List[int]) -> int:
n = len(seats)
prev = -1
future = 0
ans = 0
for i in range(n):
if seats[i] == 1:
prev = i
else:
while future < n and (seats[future] == 0 or future < i):
future += 1
left = n if prev == -1 else i - prev
right = n if future == n else future - i
ans = max(ans, min(left, right))
return ans9 162
Задача: 678. Valid Parenthesis String
Сложность: medium
Создайте карту, которая позволяет выполнять следующие действия:
Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:
Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если s является допустимой.
Следующие правила определяют допустимую строку:
Любая открывающая скобка '(' должна иметь соответствующую закрывающую скобку ')'.
Любая закрывающая скобка ')' должна иметь соответствующую открывающую скобку '('.
Открывающая скобка '(' должна идти перед соответствующей закрывающей скобкой ')'.
'*' может рассматриваться как одна закрывающая скобка ')', одна открывающая скобка '(' или пустая строка "".
Пример:
Input: s = "()"
Output: true
Example 2:class Solution:
def checkValidString(self, s: str) -> bool:
memo = [[-1] * len(s) for _ in range(len(s))]
return self.isValidString(0, 0, s, memo)
def isValidString(self, index: int, openCount: int, s: str, memo: list) -> bool:
if index == len(s):
return openCount == 0
if memo[index][openCount] != -1:
return memo[index][openCount] == 1
isValid = False
if s[index] == '*':
isValid = self.isValidString(index + 1, openCount + 1, s, memo)
if openCount > 0:
isValid = isValid or self.isValidString(index + 1, openCount - 1, s, memo)
isValid = isValid or self.isValidString(index + 1, openCount, s, memo)
elif s[index] == '(':
isValid = self.isValidString(index + 1, openCount + 1, s, memo)
elif openCount > 0:
isValid = self.isValidString(index + 1, openCount - 1, s, memo)
memo[index][openCount] = 1 if isValid else 0
return isValid9 162
Задача: 401. Binary Watch
Сложность: easy
Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа.
Пример:
Input: turnedOn = 1 Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]👨💻 Алгоритм: 1⃣Генерация всех возможных комбинаций: Переберите все возможные значения для часов и минут. Используйте битовые операции для подсчета количества единиц в бинарном представлении числа. 2⃣Проверка количества горящих светодиодов: Для каждой комбинации проверьте, соответствует ли сумма единиц в бинарном представлении часов и минут заданному количеству горящих светодиодов. 3⃣Форматирование результата: Если комбинация часов и минут соответствует условию, отформатируйте их в виде строки "часы:минуты" и добавьте в список результатов. 😎 Решение:
class Solution:
def readBinaryWatch(self, turnedOn: int) -> List[str]:
results = []
for h in range(12):
for m in range(60):
if bin(h).count('1') + bin(m).count('1') == turnedOn:
results.append(f"{h}:{m:02d}")
return results9 162
Задача: 1202. Smallest String With Swaps
Сложность: medium
Вам дана строка s и массив пар индексов в строке pairs, где pairs[i] = [a, b] указывает на 2 индекса (начиная с 0) в строке.
Вы можете менять местами символы в любой паре индексов в заданных парах любое количество раз.
Верните лексикографически наименьшую строку, которую можно получить после выполнения перестановок.
Пример:
Input: s = "dcab", pairs = [[0,3],[1,2]] Output: "bacd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[1] and s[2], s = "bacd"👨💻 Алгоритм: 1⃣Создание списка смежности: Итеративно пройдитесь по парам и создайте список смежности adj, где adj[source] содержит все смежные вершины вершины source. 2⃣Обход графа и сбор индексов и символов: Итеративно пройдитесь по индексам от 0 до s.size() - 1. Для каждого индекса vertex: - выполните DFS, если вершина еще не посещена (visited[vertex] = false). - во время выполнения DFS сохраняйте vertex в список indices и символ s[vertex] в список characters. 3⃣Сортировка и построение результирующей строки: Отсортируйте списки indices и characters. Пройдитесь по индексам и символам, и разместите i-й символ в i-й индекс результирующей строки smallestString. Верните smallestString. 😎 Решение:
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
adj = defaultdict(list)
for a, b in pairs:
adj[a].append(b)
adj[b].append(a)
visited = [False] * len(s)
s = list(s)
def dfs(node, indices, chars):
visited[node] = True
indices.append(node)
chars.append(s[node])
for neighbor in adj[node]:
if not visited[neighbor]:
dfs(neighbor, indices, chars)
for i in range(len(s)):
if not visited[i]:
indices = []
chars = []
dfs(i, indices, chars)
indices.sort()
chars.sort()
for index, char in zip(indices, chars):
s[index] = char
return ''.join(s)9 162
Задача: 75. Sort Colors
Сложность: medium
Дан массив nums, содержащий n объектов, окрашенных в красный, белый или синий цвет. Отсортируйте их на месте так, чтобы объекты одного цвета находились рядом, а цвета располагались в порядке красный, белый и синий.
Мы будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего цветов соответственно.
Вы должны решить эту задачу без использования функции сортировки библиотеки.
Пример:
Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]👨💻 Алгоритм: 1️⃣Инициализация крайней правой границы нулей: p0 = 0. Во время выполнения алгоритма nums[idx < p0] = 0. 2️⃣Инициализация крайней левой границы двоек: p2 = n - 1. Во время выполнения алгоритма nums[idx > p2] = 2. 3️⃣Инициализация индекса текущего элемента для рассмотрения: curr = 0. Пока curr <= p2: Если nums[curr] = 0: поменять местами элементы с индексами curr и p0, и сдвинуть оба указателя вправо. Если nums[curr] = 2: поменять местами элементы с индексами curr и p2. Сдвинуть указатель p2 влево. Если nums[curr] = 1: сдвинуть указатель curr вправо. 😎 Решение:
class Solution:
def sortColors(self, nums: List[int]) -> None:
p0 = curr = 0
p2 = len(nums) - 1
while curr <= p2:
if nums[curr] == 0:
nums[p0], nums[curr] = nums[curr], nums[p0]
p0 += 1
curr += 1
elif nums[curr] == 2:
nums[curr], nums[p2] = nums[p2], nums[curr]
p2 -= 1
else:
curr += 19 162
Задача: 1318. Minimum Flips to Make a OR b Equal to c
Сложность: medium
Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении.
Пример:
Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)class Solution:
def minFlips(self, a: int, b: int, c: int) -> int:
answer = 0
while a != 0 or b != 0 or c != 0:
if (c & 1) == 1:
if (a & 1) == 0 and (b & 1) == 0:
answer += 1
else:
answer += (a & 1) + (b & 1)
a >>= 1
b >>= 1
c >>= 1
return answer9 162
Задача: 288. Unique Word Abbreviation
Сложность: medium
Сокращение слова — это объединение его первой буквы, количества символов между первой и последней буквой и последней буквы. Если слово состоит только из двух символов, то оно является сокращением само по себе.
Например:
dog --> d1g, потому что между первой буквой 'd' и последней буквой 'g' одна буква.
internationalization --> i18n, потому что между первой буквой 'i' и последней буквой 'n' 18 букв.
it --> it, потому что любое слово из двух символов является своим собственным сокращением.
Реализуйте класс ValidWordAbbr:
ValidWordAbbr(String[] dictionary) Инициализирует объект со словарем слов.
boolean isUnique(string word) Возвращает true, если выполняется одно из следующих условий (в противном случае возвращает false):
В словаре нет слова, сокращение которого равно сокращению слова word.
Для любого слова в словаре, сокращение которого равно сокращению слова word, это слово и word одинаковы.
Пример:
Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]
Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.class ValidWordAbbr:
def __init__(self, dictionary: List[str]):
self.abbr_dict = {}
self.dict = set(dictionary)
for word in self.dict:
abbr = self.to_abbr(word)
self.abbr_dict[abbr] = not self.abbr_dict.get(abbr, False)
def isUnique(self, word: str) -> bool:
abbr = self.to_abbr(word)
has_abbr = self.abbr_dict.get(abbr)
return has_abbr is None or (has_abbr and word in self.dict)
def to_abbr(self, word: str) -> str:
n = len(word)
if n <= 2:
return word
return f"{word[0]}{n - 2}{word[-1]}"9 162
Задача: 438. Find All Anagrams in a String
Сложность: medium
Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.
Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.
Пример:
Input: s = "cbaebabacd", p = "abc" Output: [0,6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".👨💻 Алгоритм: 1⃣Построить эталонный счетчик pCount для строки p. 2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева. 3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список. 😎 Решение:
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ns, np = len(s), len(p)
if ns < np:
return []
pCount = Counter(p)
sCount = Counter()
output = []
for i in range(ns):
sCount[s[i]] += 1
if i >= np:
if sCount[s[i - np]] == 1:
del sCount[s[i - np]]
else:
sCount[s[i - np]] -= 1
if pCount == sCount:
output.append(i - np + 1)
return output9 162
Задача: 290. Word Pattern
Сложность: easy
Дан шаблон и строка 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 True9 162
Задача: 604. Design Compressed String Iterator
Сложность: easy
Разработайте и реализуйте структуру данных для итератора сжатой строки. Данная сжатая строка будет в виде каждой буквы, за которой следует положительное целое число, представляющее количество этой буквы в оригинальной несжатой строке.
Реализуйте класс
StringIterator:
- next(): Возвращает следующий символ, если в оригинальной строке еще остались несжатые символы, в противном случае возвращает пробел.
- hasNext(): Возвращает true, если в оригинальной строке остались символы, которые нужно распаковать, в противном случае возвращает false.
Пример:
Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]
Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return Trueclass StringIterator:
def __init__(self, s: str):
self.res = []
self.ptr = 0
i = 0
while i < len(s):
ch = s[i]
i += 1
num = 0
while i < len(s) and s[i].isdigit():
num = num * 10 + int(s[i])
i += 1
self.res.extend([ch] * num)
def next(self) -> str:
if not self.hasNext():
return ' '
char = self.res[self.ptr]
self.ptr += 1
return char
def hasNext(self) -> bool:
return self.ptr < len(self.res)9 162
Задача: 1017. Convert to Base -2
Сложность: medium
Если задано целое число n, верните двоичную строку, представляющую его в базе -2. Обратите внимание, что возвращаемая строка не должна содержать ведущих нулей, за исключением случаев, когда строка равна "0".
Пример:
Input: n = 2 Output: "110"👨💻 Алгоритм: 1⃣Инициализация переменных: Создайте пустую строку для хранения двоичного представления числа. Используйте цикл для вычисления каждой цифры числа в базе -2. 2⃣Вычисление цифр: В цикле, пока число не равно 0, вычисляйте остаток от деления числа на -2. Если остаток отрицательный, корректируйте его, добавляя 2, и увеличивайте число на 1. Добавляйте остаток в начало строки. 3⃣Возврат результата: Верните строку, представляющую число в базе -2. Если строка пустая, верните "0". 😎 Решение:
class Solution:
def baseNeg2(self, n: int) -> str:
if n == 0:
return "0"
res = ""
while n != 0:
n, remainder = divmod(n, -2)
if remainder < 0:
remainder += 2
n += 1
res = str(remainder) + res
return res9 162
Забирай на онлайн-встрече 3 трендовых рецепта 2026 года
Дорогая, 😊 я так рада, что мы с тобой делимся страстью к настоящим азиатским десертам - особенно к нежным МОТИ, которые не должны терять свою аутентичность в вихре трендов 2026 года.
Присоединяйся ко мне на уютной онлайн - встрече кондитеров, где мы мягко разберём все тонкие фишки: от идеальной текстуры теста до секретов начинок, чтобы сохранить душу оригинального рецепта.
В подарокм все участники встречи получат настоящие рецепты "Панна-котиков", "Мункейки", "Пирожное Шу Баббл-ти"
Перейти на сайт
#реклама 16+
buduconditerom.online
О рекламодателе
9 162
Задача: 224. Basic Calculator
Сложность: hard
Дана строка s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и верните результат вычисления.
Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().
Пример:
Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23👨💻 Алгоритм: 1⃣Итерация строки выражения в обратном порядке: Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра. Сохраняем операнды в стек, как только встречаем нецифровой символ. 2⃣Обработка выражения внутри скобок: Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки. Результат выражения помещаем обратно в стек. 3⃣Финальная оценка выражения: Продолжаем процесс до получения финального результата. Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение. 😎 Решение:
class Solution:
def evaluate_expr(self, stack):
if not stack or type(stack[-1]) == str:
stack.append(0)
res = stack.pop()
while stack and stack[-1] != ')':
sign = stack.pop()
if sign == '+':
res += stack.pop()
else:
res -= stack.pop()
return res
def calculate(self, s: str) -> int:
stack = []
n, operand = 0, 0
for i in range(len(s) - 1, -1, -1):
ch = s[i]
if ch.isdigit():
operand = (10**n * int(ch)) + operand
n += 1
elif ch != " ":
if n:
stack.append(operand)
n, operand = 0, 0
if ch == '(':
res = self.evaluate_expr(stack)
stack.pop()
stack.append(res)
else:
stack.append(ch)
if n:
stack.append(operand)
return self.evaluate_expr(stack)9 162
![Задача: 646. Maximum Length of Pair Chain Сложность: medium Вам дан массив из n пар, где pairs[i] = [lefti, righti] и lefti &](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/wAARCAAXACgDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwDZozQabjPJByKAFB9QRSg5puTjOD9KOmMA0AOooooAKKKKAE59B+dLRRQAUUUUAf/Z)
Задача: 646. Maximum Length of Pair Chain
Сложность: medium
Вам дан массив из n пар, где pairs[i] = [lefti, righti] и lefti < righti. Пара p2 = [c, d] следует за парой p1 = [a, b], если b < c. Таким образом можно построить цепочку пар. Верните самую длинную цепочку, которую можно составить. Вам не нужно использовать все заданные интервалы. Вы можете выбирать пары в любом порядке.
Пример:
Input: nums = [1,2,2,4] Output: [2,3]👨💻 Алгоритм: 1⃣Отсортируйте пары по второму элементу каждой пары (righti). 2⃣Используйте динамическое программирование или жадный алгоритм, чтобы построить цепочку максимальной длин 3⃣Переберите отсортированные пары и выберите пары, которые могут следовать одна за другой, увеличивая длину цепочки. 😎 Решение:
def findLongestChain(pairs):
pairs.sort(key=lambda x: x[1])
current_end = float('-inf')
count = 0
for pair in pairs:
if current_end < pair[0]:
current_end = pair[1]
count += 1
return count