Python | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
نمایش بیشتر
شبکه:8 966
مشترکین
اطلاعاتی وجود ندارد24 ساعت
-297 روز
-10530 روز
آرشیو پست ها
8 966
Задача: 1413. Minimum Value to Get Positive Step by Step Sum
Сложность: easy
Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.
На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).
Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.
Пример:
Input: nums = [-3,2,-3,4,2] Output: 5 Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1. step by step sum startValue = 4 | startValue = 5 | nums (4 -3 ) = 1 | (5 -3 ) = 2 | -3 (1 +2 ) = 3 | (2 +2 ) = 4 | 2 (3 -3 ) = 0 | (4 -3 ) = 1 | -3 (0 +4 ) = 4 | (1 +4 ) = 5 | 4 (4 +2 ) = 6 | (5 +2 ) = 7 | 2👨💻 Алгоритм: 1⃣Инициализируйте переменные startValue со значением 1 и total со значением startValue. 2⃣Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1. 3⃣Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue. 😎 Решение:
class Solution:
def minStartValue(self, nums: List[int]) -> int:
startValue = 1
while True:
total = startValue
isValid = True
for num in nums:
total += num
if total < 1:
isValid = False
break
if isValid:
return startValue
startValue += 18 966
👩💻 Стажировки и вакансии для Python разработчиков.
- Вакансии которых нет на джоб-агрегаторах
- Только прямые контакты HR в Telegram
👉 @jobs_python
Больше тут:
🤖 ML & DS 👩💻 DevOps
👨✈️ ИБ & OSINT 👣 Go
👩💻 Mobile 👩💻 C#
👩💻 Node.js 👩💻 Python
🔎 QA 👩💻 Java
👩💻 UX/UI 👩💻 Frontend
🖼️ PHP 📋 Analyst
💼 1C 🖥 SQL
👩💻 IT HR
Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.
8 966
Задача: 496. Next Greater Element I
Сложность: easy
Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве.
Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2.
Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1.
Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше.
Пример:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1] Explanation: The next greater element for each value of nums1 is as follows: - 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1. - 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3. - 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.👨💻 Алгоритм: 1⃣Инициализация и поиск совпадений Создайте массив res для хранения результатов. Для каждого элемента nums1[i] найдите его индекс j в массиве nums2. 2⃣Поиск следующего большего элемента После нахождения индекса j в nums2 начните поиск элемента справа от nums2[j], который больше nums1[i]. Если такой элемент найден, добавьте его в res. 3⃣Заполнение результата Если следующий больший элемент не найден, добавьте -1 в соответствующую позицию res. Верните массив res. 😎 Решение:
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = [-1] * len(nums1)
for i in range(len(nums1)):
found = False
for j in range(len(nums2)):
if nums2[j] == nums1[i]:
found = True
if found and nums2[j] > nums1[i]:
res[i] = nums2[j]
break
return res8 966
Задача: 247. Strobogrammatic Number II
Сложность: medium
Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).
Пример:
Input: n = 2 Output: ["11","69","88","96"]👨💻 Алгоритм: 1️⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа. 2️⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n: Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"]. Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns. Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n. 3️⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums. 😎 Решение:
class Solution:
def __init__(self):
self.reversiblePairs = [
('0', '0'), ('1', '1'),
('6', '9'), ('8', '8'), ('9', '6')
]
def generateStroboNumbers(self, n, finalLength):
if n == 0:
return [""]
if n == 1:
return ["0", "1", "8"]
prevStroboNums = self.generateStroboNumbers(n - 2, finalLength)
currStroboNums = []
for prevStroboNum in prevStroboNums:
for a, b in self.reversiblePairs:
if a != '0' or n != finalLength:
currStroboNums.append(a + prevStroboNum + b)
return currStroboNums
def findStrobogrammatic(self, n):
return self.generateStroboNumbers(n, n)8 966
Бесплатный курс диджитал-дизайна
На бесплатном курсе ты сможешь:
✨попробовать себя в диджитал-дизайне: афиши, сайты, UX/UI-дизайн (дизайн интерфейсов)
✨сделать 3 проекта для портфолио с обратной связью от наставника
✨понять, как устроена работа дизайнера
✨получить доступ к закрытой базе материалов и пошаговым инструкциям по профессии
Попробовать
#реклама 18+
study.logomachine.ru
О рекламодателе
8 966
Задача: 1053. Previous Permutation With One Swap
Сложность: medium
Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].
Пример:
Input: arr = [3,2,1] Output: [3,1,2]👨💻 Алгоритм: 1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив. 2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники. 3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд. 😎 Решение:
def prevPermOpt1(arr):
n = len(arr)
for i in range(n - 2, -1, -1):
if arr[i] > arr[i + 1]:
break
else:
return arr
for j in range(n - 1, i, -1):
if arr[j] < arr[i] and (j == n - 1 or arr[j] != arr[j + 1]):
break
arr[i], arr[j] = arr[j], arr[i]
return arr8 966
Задача: 1801. Number of Orders in the Backlog
Сложность: medium
Дан двумерный целочисленный массив
orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть:
- 0, если это партия заказов на покупку, или
- 1, если это партия заказов на продажу.
Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i.
Существует список невыполненных заказов (backlog), который изначально пуст. При размещении заказа происходит следующее:
- Если это заказ на покупку, вы просматриваете заказ на продажу с наименьшей ценой в списке невыполненных заказов. Если цена этого заказа на продажу меньше или равна цене текущего заказа на покупку, они будут сопоставлены и выполнены, и этот заказ на продажу будет удален из списка. В противном случае заказ на покупку добавляется в список невыполненных заказов.
- Если это заказ на продажу, вы просматриваете заказ на покупку с наибольшей ценой в списке невыполненных заказов. Если цена этого заказа на покупку больше или равна цене текущего заказа на продажу, они будут сопоставлены и выполнены, и этот заказ на покупку будет удален из списка. В противном случае заказ на продажу добавляется в список невыполненных заказов.
Верните общее количество заказов в списке невыполненных заказов после размещения всех заказов из входных данных. Поскольку это число может быть большим, верните его по модулю 10^9 + 7.
Пример:
Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]] Output: 6👨💻 Алгоритм: 1⃣Обрабатывайте каждый заказ в orders. Для заказа на покупку сравните с самыми дешевыми заказами на продажу в списке и выполняйте их при возможности, иначе добавьте в список. 2⃣Для заказа на продажу сравните с самыми дорогими заказами на покупку в списке и выполняйте их при возможности, иначе добавьте в список. 3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7. 😎 Решение:
class Solution:
def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
buyOrders, sellOrders = [], []
MOD = 1_000_000_007
for price, amount, orderType in orders:
if orderType == 0:
while amount > 0 and sellOrders and sellOrders[0][0] <= price:
sellOrder = heapq.heappop(sellOrders)
executedAmount = min(amount, sellOrder[1])
amount -= executedAmount
if sellOrder[1] > executedAmount:
heapq.heappush(sellOrders, (sellOrder[0], sellOrder[1] - executedAmount))
if amount > 0:
heapq.heappush(buyOrders, (-price, amount))
else:
while amount > 0 and buyOrders and -buyOrders[0][0] >= price:
buyOrder = heapq.heappop(buyOrders)
executedAmount = min(amount, buyOrder[1])
amount -= executedAmount
if buyOrder[1] > executedAmount:
heapq.heappush(buyOrders, (buyOrder[0], buyOrder[1] - executedAmount))
if amount > 0:
heapq.heappush(sellOrders, (price, amount))
return sum(amount for _, amount in buyOrders + sellOrders) % MOD8 966
Задача: 1019. Next Greater Node In Linked List
Сложность: medium
Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.
Пример:
Input: head = [2,1,5] Output: [5,5,0]👨💻 Алгоритм: 1⃣Инициализация переменных: Пройдитесь по всему списку и сохраните значения узлов в массив. Инициализируйте стек для хранения индексов узлов, которые нужно обработать. 2⃣Поиск следующего большего элемента: Итерируйте по массиву значений узлов. Для каждого элемента, пока стек не пуст и текущий элемент больше, чем элемент на вершине стека, обновите массив ответов значением текущего элемента и удалите элемент из стека. Добавьте текущий индекс в стек. 3⃣Заполнение оставшихся значений: Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента. 😎 Решение:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def nextLargerNodes(self, head: ListNode) -> List[int]:
values = []
while head:
values.append(head.val)
head = head.next
answer = [0] * len(values)
stack = []
for i, value in enumerate(values):
while stack and values[stack[-1]] < value:
answer[stack.pop()] = value
stack.append(i)
return answer8 966
Всё, что вы любите, есть на Wildberries
Все мы ищем разное, но всегда находим что-то своё на WB — со скидками и доставкой.
Перейти на сайт
#реклама
wildberries.ru
О рекламодателе
8 966
Задача: 1342. Number of Steps to Reduce a Number to Zero
Сложность: easy
Дано целое число num, вернуть количество шагов, необходимых для его сокращения до нуля.
На каждом шаге, если текущее число четное, его нужно разделить на 2, в противном случае, вы должны вычесть из него 1.
Пример:
Input: num = 14 Output: 6 Explanation: Step 1) 14 is even; divide by 2 and obtain 7. Step 2) 7 is odd; subtract 1 and obtain 6. Step 3) 6 is even; divide by 2 and obtain 3. Step 4) 3 is odd; subtract 1 and obtain 2. Step 5) 2 is even; divide by 2 and obtain 1. Step 6) 1 is odd; subtract 1 and obtain 0.👨💻 Алгоритм: 1⃣На каждом шаге проверяйте, четное ли текущее число, используя оператор остатка от деления (%). Если число четное (number % 2 == 0), разделите его на 2. 2⃣Если число нечетное (number % 2 == 1), вычтите из него 1. 3⃣После выполнения каждого из этих действий увеличивайте счетчик шагов на 1, чтобы в конце вернуть его значение. 😎 Решение:
def numberOfSteps(num):
steps = 0
while num != 0:
if num % 2 == 0:
num //= 2
else:
num -= 1
steps += 1
return steps8 966
Задача: 1473. Paint House III
Сложность: hard
Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.
Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.
Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.
Пример:
Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.class Solution:
def __init__(self):
self.MAX_COST = 1000001
self.memo = {}
def findMinCost(self, houses, cost, targetCount, currIndex, neighborhoodCount, prevHouseColor):
if currIndex == len(houses):
return 0 if neighborhoodCount == targetCount else self.MAX_COST
if neighborhoodCount > targetCount:
return self.MAX_COST
if (currIndex, neighborhoodCount, prevHouseColor) in self.memo:
return self.memo[(currIndex, neighborhoodCount, prevHouseColor)]
minCost = self.MAX_COST
if houses[currIndex] != 0:
newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor)
minCost = self.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex])
else:
for color in range(1, len(cost[0]) + 1):
newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor)
currCost = cost[currIndex][color - 1] + self.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color)
minCost = min(minCost, currCost)
self.memo[(currIndex, neighborhoodCount, prevHouseColor)] = minCost
return minCost
def minCost(self, houses, cost, m, n, target):
answer = self.findMinCost(houses, cost, target, 0, 0, 0)
return -1 if answer == self.MAX_COST else answer8 966
Куда срочно перенести рабочие чаты?
Битрикс24 — мессенджер для работы и бизнеса.
Личные и групповые чаты, видеозвонки и каналы в одном сервисе. Приглашайте коллег и внешние команды. Работает как привычный мессенджер.
Есть бесплатный тариф. Начните работать уже сейчас.
Попробовать
#реклама 16+
bitrix24.ru
О рекламодателе
8 966
Задача: 459. Repeated Substring Pattern
Сложность: easy
Дана строка s, проверьте, может ли она быть построена путем взятия подстроки и добавления нескольких копий этой подстроки друг за другом.
Пример:
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.👨💻 Алгоритм: 1⃣Создайте целочисленную переменную n, равную длине строки s. 2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2: Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s. Если pattern равен s, вернуть true. 3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false. 😎 Решение:
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
for i in range(1, n // 2 + 1):
if n % i == 0:
pattern = s[:i] * (n // i)
if s == pattern:
return True
return False8 966
Задача: 635. Design Log Storage System
Сложность: medium
Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения.
int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать.
Пример:
Input ["LogSystem", "put", "put", "put", "retrieve", "retrieve"] [[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]] Output [null, null, null, null, [3, 2, 1], [2, 1]]👨💻 Алгоритм: 1⃣Инициализация и хранение журналов Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения. 2⃣Формирование диапазона Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity. 3⃣Фильтрация и возврат результатов Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон. 😎 Решение:
class LogSystem:
def __init__(self):
self.logs = []
def put(self, id: int, timestamp: str) -> None:
self.logs.append((id, timestamp))
def retrieve(self, start: str, end: str, granularity: str) -> [int]:
index = {
'Year': 4,
'Month': 7,
'Day': 10,
'Hour': 13,
'Minute': 16,
'Second': 19
}[granularity]
start = start[:index]
end = end[:index]
result = []
for id, timestamp in self.logs:
if start <= timestamp[:index] <= end:
result.append(id)
return result8 966
Задача: 733. Flood Fill
Сложность: easy
Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.
Пример:
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Output: [[2,2,2],[2,2,0],[2,0,1]]👨💻 Алгоритм: 1⃣Получите цвет начального пикселя. 2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет. 3⃣Обновите изображение и верните его. 😎 Решение:
def floodFill(image, sr, sc, color):
original_color = image[sr][sc]
if original_color == color:
return image
def dfs(x, y):
if x < 0 or x >= len(image) or y < 0 or y >= len(image[0]) or image[x][y] != original_color:
return
image[x][y] = color
dfs(x + 1, y)
dfs(x - 1, y)
dfs(x, y + 1)
dfs(x, y - 1)
dfs(sr, sc)
return image8 966
Задача: 1474. Delete N Nodes After M Nodes of a Linked List
Сложность: easy
Вам дано начало связанного списка и два целых числа m и n.
Пройдите по связанному списку и удалите некоторые узлы следующим образом:
Начните с головы как текущего узла.
Сохраните первые m узлов, начиная с текущего узла.
Удалите следующие n узлов.
Продолжайте повторять шаги 2 и 3, пока не достигнете конца списка.
Верните голову изменённого списка после удаления указанных узлов.
Пример:
Input: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3
Output: [1,2,6,7,11,12]
Explanation: Keep the first (m = 2) nodes starting from the head of the linked List (1 ->2) show in black nodes.
Delete the next (n = 3) nodes (3 -> 4 -> 5) show in read nodes.
Continue with the same procedure until reaching the tail of the Linked List.
Head of the linked list after removing nodes is returned.class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
currentNode = head
lastMNode = head
while currentNode:
mCount, nCount = m, n
while currentNode and mCount > 0:
lastMNode = currentNode
currentNode = currentNode.next
mCount -= 1
while currentNode and nCount > 0:
currentNode = currentNode.next
nCount -= 1
lastMNode.next = currentNode
return head8 966
Задача: 162. Find Peak Element
Сложность: medium
Пиковым элементом называется элемент, который строго больше своих соседей.
Для массива целых чисел nums с индексацией с нуля найдите пиковый элемент и верните его индекс. Если в массиве несколько пиков, верните индекс любого из пиков.
Вы можете представить, что nums[-1] = nums[n] = -∞. Другими словами, элемент всегда считается строго большим, чем сосед, находящийся за пределами массива.
Необходимо написать алгоритм, который работает за время O(log n).
Пример:
Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2.👨💻 Алгоритм: 1️⃣Начальная проверка: Определяем средний элемент массива mid как mid = low + (high - low) / 2. Это помогает предотвратить возможное переполнение при больших значениях индексов. 2️⃣Определение направления поиска: Сравниваем элемент nums[mid] с его правым соседом nums[mid + 1]. Если nums[mid] меньше nums[mid + 1], это указывает на наличие восходящей последовательности, и мы двигаемся вправо, устанавливая low = mid + 1. Это потому, что пик гарантированно находится в правой части. Если nums[mid] больше nums[mid + 1], это указывает на наличие нисходящей последовательности, и пик находится либо в mid, либо слева от него, тогда устанавливаем high = mid. 3️⃣Завершение поиска: Процесс продолжается до тех пор, пока low не станет равным high, что означает сужение поисковой области до одного элемента, который и является пиком, поскольку мы исключили все другие возможности. 😎 Решение:
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
return self.search(nums, 0, len(nums) - 1)
def search(self, nums: List[int], l: int, r: int) -> int:
if l == r:
return l
mid = (l + r) // 2
if nums[mid] > nums[mid + 1]:
return self.search(nums, l, mid)
return self.search(nums, mid + 1, r)8 966
Задача: 398. Random Pick Index
Сложность: medium
Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата.
Пример:
Input ["Solution", "pick", "pick", "pick"] [[[1, 2, 3, 3, 3]], [3], [1], [3]] Output [null, 4, 0, 2]👨💻 Алгоритм: 1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования. 2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным. 3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса. 😎 Решение:
import random
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
def pick(self, target: int) -> int:
count = 0
result = -1
for i, num in enumerate(self.nums):
if num == target:
count += 1
if random.randint(1, count) == count:
result = i
return result8 966
Задача: 1263. Minimum Moves to Move a Box to Their Target Location
Сложность: hard
Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1.
Пример:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 3
👨💻 Алгоритм:
1⃣Выполните поиск в ширину (BFS) для всех возможных позиций игрока и коробки, отслеживая количество толчков.
2⃣Используйте очередь для хранения состояний игрока и коробки, а также текущего количества толчков.
3⃣Для каждого состояния проверяйте все возможные движения игрока и перемещения коробки, обновляйте очередь и отмечайте посещенные состояния.
😎 Решение:
from collections import deque
def minPushBox(grid):
m, n = len(grid), len(grid[0])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def valid(x, y):
return 0 <= x < m and 0 <= y < n and grid[x][y] != '#'
def bfs(start):
queue = deque([start])
visited = set([start])
while queue:
px, py, bx, by, pushes = queue.popleft()
if (bx, by) == target:
return pushes
for dx, dy in directions:
npx, npy = px + dx, py + dy
if valid(npx, npy) and (npx, npy, bx, by, pushes) not in visited:
if (npx, npy) == (bx, by):
nbx, nby = bx + dx, by + dy
if valid(nbx, nby) and (npx, npy, nbx, nby, pushes + 1) not in visited:
queue.append((npx, npy, nbx, nby, pushes + 1))
visited.add((npx, npy, nbx, nby, pushes + 1))
else:
queue.append((npx, npy, bx, by, pushes))
visited.add((npx, npy, bx, by, pushes))
return -1
for i in range(m):
for j in range(n):
if grid[i][j] == 'S':
player = (i, j)
elif grid[i][j] == 'B':
box = (i, j)
elif grid[i][j] == 'T':
target = (i, j)
return bfs((*player, *box, 0))8 966
Задача: 941. Valid Mountain Array
Сложность: easy
Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Пример:
Input: arr = [2,1] Output: false👨💻 Алгоритм: 1⃣Убедиться, что длина массива не меньше 3. 2⃣Найти вершину горы, которая удовлетворяет условиям горного массива. Проверить, что все элементы слева от вершины строго возрастают. Проверить, что все элементы справа от вершины строго убывают. 3⃣Вернуть true, если оба условия выполнены, иначе вернуть false. 😎 Решение:
def validMountainArray(arr):
if len(arr) < 3:
return False
i = 1
while i < len(arr) and arr[i] > arr[i - 1]:
i += 1
if i == 1 or i == len(arr):
return False
while i < len(arr) and arr[i] < arr[i - 1]:
i += 1
return i == len(arr)