Python | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
显示更多8 888
订阅者
-324 小时
-247 天
-12430 天
正在加载数据
相似频道
标签云
进出提及
---
---
---
---
---
---
吸引订阅者
十一月 '2611月 '26
十一月 '26
+15
在0个频道中
十月 '26
+28
在0个频道中
Get PRO
九月 '26
+42
在0个频道中
Get PRO
八月 '26
+43
在1个频道中
Get PRO
七月 '26
+36
在0个频道中
Get PRO
六月 '26
+44
在2个频道中
Get PRO
五月 '26
+40
在0个频道中
Get PRO
四月 '26
+47
在0个频道中
Get PRO
三月 '26
+50
在0个频道中
Get PRO
二月 '26
+42
在0个频道中
Get PRO
一月 '26
+69
在0个频道中
Get PRO
十二月 '25
+55
在0个频道中
Get PRO
十一月 '25
+105
在0个频道中
Get PRO
十月 '25
+110
在0个频道中
Get PRO
九月 '25
+67
在0个频道中
Get PRO
八月 '25
+112
在1个频道中
Get PRO
七月 '25
+128
在4个频道中
Get PRO
六月 '25
+129
在2个频道中
Get PRO
五月 '25
+166
在3个频道中
Get PRO
四月 '25
+178
在0个频道中
Get PRO
三月 '25
+217
在3个频道中
Get PRO
二月 '25
+343
在6个频道中
Get PRO
一月 '25
+307
在53个频道中
Get PRO
十二月 '24
+150
在0个频道中
Get PRO
十一月 '24
+174
在0个频道中
Get PRO
十月 '24
+725
在15个频道中
Get PRO
九月 '24
+3 750
在329个频道中
Get PRO
八月 '24
+260
在0个频道中
Get PRO
七月 '24
+2 514
在219个频道中
Get PRO
六月 '24
+3 546
在232个频道中
| 日期 | 订阅者增长 | 提及 | 频道 | |
| 16 十一月 | 0 | |||
| 15 十一月 | +1 | |||
| 14 十一月 | 0 | |||
| 13 十一月 | +1 | |||
| 12 十一月 | +1 | |||
| 11 十一月 | +1 | |||
| 10 十一月 | 0 | |||
| 09 十一月 | +1 | |||
| 08 十一月 | 0 | |||
| 07 十一月 | +3 | |||
| 06 十一月 | +3 | |||
| 05 十一月 | +1 | |||
| 04 十一月 | 0 | |||
| 03 十一月 | 0 | |||
| 02 十一月 | +1 | |||
| 01 十一月 | +2 |
频道帖子
Срочно требуются дизайнеры в FIGMA. Обучим с нуля.
Онлайн-программа с наставником и чатом.
Внимание! 80% практики.
✅По результату обучения у вас будет портфолио из нескольких работ.
✅Сертификат о прохождении курса.
✅Возможность пройти полное обучение и получить карьерное сопровождение!
Учитесь дизайну у профессионалов в Yudaev Shool.
Переходи по кнопки: "Подробнее" и начинай свое обучение.
Доступ 0 руб.
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе
| 2 | Задача: №20. Valid Parentheses
Сложность: easy
Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, является ли входная строка допустимой. Входная строка действительна, если:
- Открытые скобки должны закрываться скобками того же типа.
- Открытые скобки должны закрываться в правильном порядке.
- Каждой закрывающей скобке соответствует открытая скобка того же типа.
Пример:
Input: s = "()[]{}"
Output: true
👨💻 Алгоритм:
1️⃣Использовать стек для отслеживания открытых скобок.
2️⃣При встрече закрывающей скобки проверять соответствие последней открытой скобке.
3️⃣В конце стек должен быть пустым, если строка валидна.
😎 Решение:
class Solution:
def isValid(self, s: str) -> bool:
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
Ставь 👍 и забирай 📚 Базу знаний | 230 |
| 3 | Задача: 979. Distribute Coins in Binary Tree
Сложность: medium
Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет.
За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю.
Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету.
Пример:
Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.
👨💻 Алгоритм:
1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0.
2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves.
3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves.
😎 Решение:
class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
self.moves = 0
self.dfs(root)
return self.moves
def dfs(self, current: Optional[TreeNode]) -> int:
if not current:
return 0
leftCoins = self.dfs(current.left)
rightCoins = self.dfs(current.right)
self.moves += abs(leftCoins) + abs(rightCoins)
return current.val - 1 + leftCoins + rightCoins
Ставь 👍 и забирай 📚 Базу знаний | 347 |
| 4 | Яндекс Музыка до 360 дней бесплатно
Яндекс Музыка для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в мультиподписке Плюс.
Попробуйте бесплатно❤️
Слушать
#реклама 18+
music.yandex.ru
О рекламодателе | 399 |
| 5 | Аренда и размещение серверов в дата-центрах Москвы
ITSOFT оказывает услуги коммерческого дата-центра в Москве.
👌Аренда физических выделенных серверов (Dedicated Servers) в готовых конфигурациях и в рамках индивидуальных сборок.
👌Colocation и аренда серверных стоек.
👌Предоставление инфраструктурных ИТ-решений для физических лиц и корпоративных клиентов.
👌Предоставление высокоскоростных каналов передачи данных.
Узнать цену
#реклама 16+
itsoft.ru
О рекламодателе | 390 |
| 6 | Бесплатные онлайн-лекции по ИТ и биотеху: 6—17 ноября
Что меняется с развитием ИИ в ИТ-сфере? Расскажут эксперты — представители науки и индустрии на открытых лекциях магистратуры Центрального университета.
6—17 ноября онлайн.
Для тех, кто строит карьеру в ИТ!
Зарегистрироваться
#реклама 16+
cu.ru
О рекламодателе | 330 |
| 7 | Задача: 292. Nim Game
Сложность: easy
Вы играете в следующую игру Nim со своим другом:
Изначально на столе лежит куча камней.
Вы и ваш друг поочередно делаете ходы, и вы ходите первым.
Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.
Тот, кто убирает последний камень, становится победителем.
Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.
Пример:
Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.
👨💻 Алгоритм:
1⃣Определите базовый случай:
Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true.
2⃣Анализ оставшихся камней:
Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false.
3⃣Выигрышная стратегия:
Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true.
😎 Решение:
class Solution:
def canWinNim(self, n: int) -> bool:
return n % 4 != 0
Ставь 👍 и забирай 📚 Базу знаний | 704 |
| 8 | Задача: 362. Design Hit Counter
Сложность: medium
Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.
Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной.
Пример:
Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]
Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1); // hit at timestamp 1.
hitCounter.hit(2); // hit at timestamp 2.
hitCounter.hit(3); // hit at timestamp 3.
hitCounter.getHits(4); // get hits at timestamp 4, return 3.
hitCounter.hit(300); // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.
👨💻 Алгоритм:
1⃣При вызове метода hit(int timestamp), добавьте временную метку в очередь.
2⃣ При вызове метода getHits(int timestamp), удалите все временные метки из очереди, которые старше 300 секунд от текущей временной метки.
3⃣Верните размер очереди как количество попаданий за последние 5 минут.
😎 Решение:
from collections import deque
class HitCounter:
def __init__(self):
self.hits = deque()
def hit(self, timestamp: int) -> None:
self.hits.append(timestamp)
def getHits(self, timestamp: int) -> int:
while self.hits and timestamp - self.hits[0] >= 300:
self.hits.popleft()
return len(self.hits)
Ставь 👍 и забирай 📚 Базу знаний | 532 |
| 9 | Задача: 340. Longest Substring with At Most K Distinct Characters
Сложность: medium
Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.
Пример:
Input: n = 27
Output: true
Explanation: 27 = 3^3
👨💻 Алгоритм:
1⃣Инициализация
Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length).
2⃣Раздвижение окна
Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.
3⃣Обновление максимальной длины
На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки.
😎 Решение:
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
left = 0
right = 0
char_count = {}
max_length = 0
while right < len(s):
char_count[s[right]] = char_count.get(s[right], 0) + 1
while len(char_count) > k:
char_count[s[left]] -= 1
if char_count[s[left]] == 0:
del char_count[s[left]]
left += 1
max_length = max(max_length, right - left + 1)
right += 1
return max_length
Ставь 👍 и забирай 📚 Базу знаний | 407 |
| 10 | Задача: 1101. The Earliest Moment When Everyone Become Friends
Сложность: medium
В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.
Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.
Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.
Пример:
Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.
👨💻 Алгоритм:
1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они.
2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск":
Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b).
Каждое объединение добавляет новые связи между участниками.
3⃣Следите за количеством групп:
Изначально каждый участник рассматривается как отдельная группа.
Количество групп уменьшается с каждым полезным объединением.
Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени.
Если такого момента не существует, верните -1.
😎 Решение:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
return True
return False
class Solution:
def earliestAcq(self, logs: List[List[int]], n: int) -> int:
logs.sort()
uf = UnionFind(n)
group_count = n
for timestamp, friendA, friendB in logs:
if uf.union(friendA, friendB):
group_count -= 1
if group_count == 1:
return timestamp
return -1
Ставь 👍 и забирай 📚 Базу знаний | 406 |
| 11 | Задача: 1319. Number of Operations to Make Network Connected
Сложность: medium
Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть.
Вам даны начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными.
Верните минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, верните -1.
Пример:
Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.
👨💻 Алгоритм:
1⃣Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь граф. В этом случае возвращаем -1.
2⃣Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте целое число numberOfConnectedComponents, которое хранит количество компонент связности в графе. Инициализируйте его значением 0.
3⃣Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS:
Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i.
Отметьте узел как посещенный.
Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла.
Верните numberOfConnectedComponents - 1.
😎 Решение:
class Solution:
def dfs(self, node, adj, visit):
visit[node] = True
if node not in adj:
return
for neighbor in adj[node]:
if not visit[neighbor]:
visit[neighbor] = True
self.dfs(neighbor, adj, visit)
def makeConnected(self, n, connections):
if len(connections) < n - 1:
return -1
adj = {}
for connection in connections:
adj.setdefault(connection[0], []).append(connection[1])
adj.setdefault(connection[1], []).append(connection[0])
numberOfConnectedComponents = 0
visit = [False] * n
for i in range(n):
if not visit[i]:
numberOfConnectedComponents += 1
self.dfs(i, adj, visit)
return numberOfConnectedComponents - 1
Ставь 👍 и забирай 📚 Базу знаний | 422 |
| 12 | 🔥 Скрытые вакансии с удаленной работой для Python разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 Python Jobs | Вакансии
🔹 Data Science ML | Вакансии
🔹 Golang Go Jobs | Вакансии
🔸 Все каналы с вакансиями | 450 |
| 13 | Срочно требуются дизайнеры в FIGMA. Обучим с нуля.
Онлайн-программа с наставником и чатом.
Внимание! 80% практики.
✅По результату обучения у вас будет портфолио из нескольких работ.
✅Сертификат о прохождении курса.
✅Возможность пройти полное обучение и получить карьерное сопровождение!
Учитесь дизайну у профессионалов в Yudaev Shool.
Переходи по кнопки: "Подробнее" и начинай свое обучение.
Доступ 0 руб.
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе | 348 |
| 14 | Задача: 1025. Divisor Game
Сложность: easy
Алиса и Боб играют в игру по очереди, причем Алиса начинает первой. Изначально на доске мелом написано число n. В свой ход каждый игрок делает ход, состоящий из: выбора любого x при 0 < x < n и n % x == 0. Замены числа n на доске на n - x. Также, если игрок не может сделать ход, он проигрывает игру. Возвращается true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально.
Пример:
Input: n = 2
Output: true
👨💻 Алгоритм:
1⃣Определение выигрыша:
Заметим, что если число n четное, Алиса всегда выигрывает, потому что она может уменьшить n на 1, и оставить Боба с нечетным числом.
Если число n нечетное, Алиса всегда проигрывает, потому что Боб может уменьшить n на 1, и оставить Алису с четным числом.
2⃣Проверка четности числа:
Проверяем, четное ли число n. Если n четное, возвращаем true, если нечетное, возвращаем false.
3⃣Возврат результата:
Возвращаем результат в зависимости от четности числа n.
😎 Решение:
class Solution:
def divisorGame(self, n: int) -> bool:
return n % 2 == 0
Ставь 👍 и забирай 📚 Базу знаний | 477 |
| 15 | Минус один вечер над домашкой
Тема – слайды – текст для выступления. Всё в Кэмпе ⚡
Не надо сидеть до ночи в поисках картинок и источников.
Первые 400 токенов бесплатно, попробуй к ближайшей паре.
Попробовать
#реклама 16+
kampus.ai
О рекламодателе | 359 |
| 16 | Задача: 312. Burst Balloons
Сложность: hard
Дано n воздушных шаров, пронумерованных от 0 до n - 1. Каждый шарик окрашен в число, представленное массивом nums. Вам нужно лопнуть все шарики.
Если вы лопаете шарик i, вы получите nums[i - 1] * nums[i] * nums[i + 1] монет. Если i - 1 или i + 1 выходит за границы массива, то считайте, что там находится шарик с числом 1.
Верните максимальное количество монет, которое можно собрать, лопая шарики с умом.
Пример:
Input: nums = [1,5]
Output: 10
👨💻 Алгоритм:
1⃣Инициализация и подготовка данных
Добавьте по одному шару с числом 1 в начало и конец массива nums, чтобы упростить обработку граничных случаев. Определите функцию dp(left, right), которая будет возвращать максимальное количество монет, если лопнуть все шары на интервале [left, right] включительно.
2⃣Вычисление значений для всех интервалов
Для каждого интервала [left, right] и каждого индекса i в этом интервале: Вычислите максимальные монеты, которые можно получить, сначала лопая все шары кроме i, а затем лопая i. Обновите dp(left, right) максимальной суммой этих монет.
3⃣Возврат результата
Верните значение dp(1, n - 2), которое будет содержать максимальное количество монет, которое можно собрать, лопнув все шары с умом, исключая добавленные нами шары.
😎 Решение:
class Solution:
def maxCoins(self, nums: List[int]) -> int:
nums = [1] + nums + [1]
n = len(nums)
@lru_cache(None)
def dp(left: int, right: int) -> int:
if left > right:
return 0
max_coins = 0
for i in range(left, right + 1):
coins = dp(left, i - 1) + dp(i + 1, right) + nums[left - 1] * nums[i] * nums[right + 1]
max_coins = max(max_coins, coins)
return max_coins
return dp(1, n - 2)
Ставь 👍 и забирай 📚 Базу знаний | 486 |
| 17 | Квартиры Петербург Новостройка Рассрочка от застройщика
Жилой комплекс "Квартал Заречье"
Санкт-Петербург. Колпино.
4 девятиэтажных жилых корпуса
8-этажный крытый гараж на 496 парковочных мест
В живописном месте у реки Ижора.
На первых этажах будут размещены магазины, кофейни, поликлиника и зона коворкинга.
Перейти на сайт
Финансовые услуги оказывает: ПАО «Сбербанк». Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО «СЗ «ЗАГОРОДНАЯ, 71».
#реклама
квартал-заречье.рф
О рекламодателе | 418 |
| 18 | Задача: 1335. Minimum Difficulty of a Job Schedule
Сложность: hard
Вы хотите составить расписание списка заданий на d дней. Задания зависят друг от друга (т.е. чтобы выполнить задание i, вы должны закончить все задания j, где 0 <= j < i).
Вы должны выполнять как минимум одно задание каждый день. Сложность расписания заданий — это сумма сложностей каждого дня из d дней. Сложность дня — это максимальная сложность задания, выполненного в этот день.
Вам дан массив целых чисел jobDifficulty и целое число d. Сложность i-го задания равна jobDifficulty[i].
Верните минимальную сложность расписания заданий. Если вы не можете найти расписание для заданий, верните -1.
Пример:
Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7
👨💻 Алгоритм:
1⃣Определение состояния:
Индекс i (индекс первой задачи на сегодняшний день в массиве jobDifficulty) и день d (количество оставшихся дней) будут определять состояние динамического программирования. min_diff(i, d) обозначает минимальную сложность при начале с i-й задачи с оставшимися d днями. min_diff(0, d) будет окончательным ответом, так как он представляет начало с начала массива задач и завершение всех задач за ровно d дней.
2⃣Функция перехода состояния:
Задача с индексом j будет первой задачей на следующий день, следовательно, задачи, которые должны быть завершены сегодня, это все задачи с индексами между i и j, то есть jobDifficulty[i
]. Поскольку сложность дня — это максимальная сложность выполненной в этот день задачи, к сумме сложностей задач будет добавляться максимум из jobDifficulty[i
]. Формулируем функцию перехода состояния следующим образом: min_diff(i, d) = min_diff(j, d - 1) + max(jobDifficulty[i
]) для всех j > i.
3⃣Базовый случай:
Когда остается только 1 день, необходимо завершить все незавершенные задачи в этот день и увеличить сложность расписания задач на максимальную сложность этих задач.
😎 Решение:
class Solution:
def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
n = len(jobDifficulty)
if n < d:
return -1
mem = [[-1] * (d + 1) for _ in range(n)]
def minDiff(i, daysRemaining):
if mem[i][daysRemaining] != -1:
return mem[i][daysRemaining]
if daysRemaining == 1:
return max(jobDifficulty[i:])
res = float('inf')
dailyMaxJobDiff = 0
for j in range(i, n - daysRemaining + 1):
dailyMaxJobDiff = max(dailyMaxJobDiff, jobDifficulty[j])
res = min(res, dailyMaxJobDiff + minDiff(j + 1, daysRemaining - 1))
mem[i][daysRemaining] = res
return res
return minDiff(0, d)
Ставь 👍 и забирай 📚 Базу знаний | 463 |
| 19 | Бесплатные онлайн-лекции по ИТ и биотеху: 6—17 ноября
Что меняется с развитием ИИ в ИТ-сфере? Расскажут эксперты — представители науки и индустрии на открытых лекциях магистратуры Центрального университета.
6—17 ноября онлайн.
Для тех, кто строит карьеру в ИТ!
Зарегистрироваться
#реклама 16+
cu.ru
О рекламодателе | 386 |
| 20 | Задача: 1234. Replace the Substring for Balanced String
Сложность: medium
Вам дана строка s длины n, содержащая только четыре вида символов: 'Q', 'W', 'E' и 'R'. Строка считается сбалансированной, если каждый из ее символов встречается n / 4 раз, где n - длина строки. Верните минимальную длину подстроки, которую можно заменить любой другой строкой той же длины, чтобы сделать s сбалансированной. Если s уже сбалансирована, верните 0.
Пример:
Input: s = "QWER"
Output: 0
👨💻 Алгоритм:
1⃣Проверка баланса:
Сначала проверим, сбалансирована ли строка s. Если да, то возвращаем 0.
2⃣Подсчет частоты символов:
Подсчитаем количество каждого символа в строке s.
3⃣Использование скользящего окна:
Используем метод двух указателей (скользящее окно) для нахождения минимальной подстроки, которую можно заменить, чтобы строка стала сбалансированной.
Начнем с окна, которое захватывает всю строку, и будем постепенно уменьшать его, проверяя при каждом шаге, становится ли строка сбалансированной.
😎 Решение:
def balancedString(s):
from collections import Counter
n = len(s)
count = Counter(s)
target = n // 4
def is_balanced():
return all(count[char] <= target for char in 'QWER')
if is_balanced():
return 0
min_length = n
left = 0
for right in range(n):
count[s[right]] -= 1
while is_balanced():
min_length = min(min_length, right - left + 1)
count[s[left]] += 1
left += 1
return min_length
Ставь 👍 и забирай 📚 Базу знаний | 474 |
