← Назад к курсу
Решение задач с LeetCode TOP-150 (Блок 5/5: Задачи 121-150)
121. Kth Largest Element in an Array
Описание: Найти k-й наибольший элемент в несортированном массиве.
import heapq
import random
def findKthLargest(nums, k):
"""
Поиск k-го наибольшего элемента
Способ 1: Используя минимальную кучу
"""
# Создаем минимальную кучу размера k
heap = []
for num in nums:
if len(heap) < k:
heapq.heappush(heap, num)
elif num > heap[0]:
heapq.heappushpop(heap, num)
return heap[0]
def findKthLargestQuickSelect(nums, k):
"""
Способ 2: QuickSelect (быстрый выбор)
"""
def partition(left, right, pivot_index):
"""Разделение массива относительно опорного элемента"""
pivot_value = nums[pivot_index]
# Перемещаем опорный элемент в конец
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
store_index = left
for i in range(left, right):
if nums[i] < pivot_value:
nums[store_index], nums[i] = nums[i], nums[store_index]
store_index += 1
# Возвращаем опорный элемент на правильное место
nums[right], nums[store_index] = nums[store_index], nums[right]
return store_index
def quickselect(left, right, k_smallest):
"""Рекурсивный QuickSelect"""
if left == right:
return nums[left]
# Выбираем случайный опорный элемент
pivot_index = random.randint(left, right)
# Разделяем и получаем позицию опорного элемента
pivot_index = partition(left, right, pivot_index)
# Нашли k-й наименьший элемент
if k_smallest == pivot_index:
return nums[k_smallest]
elif k_smallest < pivot_index:
return quickselect(left, pivot_index - 1, k_smallest)
else:
return quickselect(pivot_index + 1, right, k_smallest)
# k-й наибольший = (n-k)-й наименьший
return quickselect(0, len(nums) - 1, len(nums) - k)
122. IPO
Описание: Выбрать проекты для максимизации капитала после k инвестиций.
import heapq
def findMaximizedCapital(k, w, profits, capital):
"""
Максимизация капитала после k инвестиций
"""
n = len(profits)
projects = list(zip(capital, profits))
projects.sort() # Сортируем по требуемому капиталу
max_heap = [] # Максимальная куча для доступных проектов
i = 0
for _ in range(k):
# Добавляем все проекты, которые можем себе позволить
while i < n and projects[i][0] <= w:
heapq.heappush(max_heap, -projects[i][1]) # Отрицательное значение для max-heap
i += 1
if not max_heap:
break
# Берем самый прибыльный проект
w += -heapq.heappop(max_heap)
return w
123. Find K Pairs with Smallest Sums
Описание: Найти k пар с наименьшими суммами из двух массивов.
import heapq
def kSmallestPairs(nums1, nums2, k):
"""
Поиск k пар с наименьшими суммами
"""
if not nums1 or not nums2:
return []
result = []
heap = []
# Добавляем первые k пар (nums1[i] + nums2[0])
for i in range(min(k, len(nums1))):
heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))
while heap and len(result) < k:
_, i, j = heapq.heappop(heap)
result.append([nums1[i], nums2[j]])
# Добавляем следующую пару из того же элемента nums1
if j + 1 < len(nums2):
heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
return result
124. Find Median from Data Stream
Описание: Реализовать структуру данных для нахождения медианы из потока чисел.
import heapq
class MedianFinder:
def __init__(self):
"""
Инициализация структуры данных
Две кучи: max_heap для левой половины, min_heap для правой
"""
self.max_heap = [] # Левая половина (отрицательные значения для max-heap)
self.min_heap = [] # Правая половина (min-heap)
def addNum(self, num):
"""
Добавление числа в структуру
"""
# Добавляем в max_heap (левую половину)
heapq.heappush(self.max_heap, -num)
# Балансировка: перемещаем максимальный элемент из левой в правую
max_left = -heapq.heappop(self.max_heap)
heapq.heappush(self.min_heap, max_left)
# Если правая куча стала больше левой, балансируем обратно
if len(self.min_heap) > len(self.max_heap):
min_right = heapq.heappop(self.min_heap)
heapq.heappush(self.max_heap, -min_right)
def findMedian(self):
"""
Нахождение медианы
"""
if len(self.max_heap) > len(self.min_heap):
return -self.max_heap[0]
else:
return (-self.max_heap[0] + self.min_heap[0]) / 2
# Альтернативная реализация с приоритетами
class MedianFinder2:
def __init__(self):
self.small = [] # Max-heap (отрицательные значения)
self.large = [] # Min-heap
def addNum(self, num):
# Всегда добавляем в small, затем балансируем
heapq.heappush(self.small, -num)
# Убедимся, что все элементы в small <= все элементы в large
if self.small and self.large and (-self.small[0] > self.large[0]):
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
# Балансировка размеров
if len(self.small) > len(self.large) + 1:
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
elif len(self.large) > len(self.small):
val = heapq.heappop(self.large)
heapq.heappush(self.small, -val)
def findMedian(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2
125. Add Binary
Описание: Сложить два бинарных числа, представленных строками.
def addBinary(a, b):
"""
Сложение бинарных чисел
"""
result = []
carry = 0
i, j = len(a) - 1, len(b) - 1
while i >= 0 or j >= 0 or carry:
# Получаем цифры (или 0 если строка закончилась)
digit_a = int(a[i]) if i >= 0 else 0
digit_b = int(b[j]) if j >= 0 else 0
# Суммируем с переносом
total = digit_a + digit_b + carry
digit = total % 2
carry = total // 2
result.append(str(digit))
i -= 1
j -= 1
# Результат в обратном порядке
return ''.join(reversed(result))
# Альтернативное решение с использованием встроенных функций
def addBinary2(a, b):
return bin(int(a, 2) + int(b, 2))[2:]
126. Reverse Bits
Описание: Перевернуть биты 32-битного беззнакового целого числа.
def reverseBits(n):
"""
Переворот битов 32-битного числа
"""
result = 0
for i in range(32):
# Сдвигаем результат влево
result <<= 1
# Добавляем младший бит n
result |= (n & 1)
# Сдвигаем n вправо
n >>= 1
return result
# Оптимизированная версия
def reverseBitsOptimized(n):
n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16)
n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)
return n
127. Number of 1 Bits
Описание: Подсчитать количество единичных битов в числе (Hamming weight).
def hammingWeight(n):
"""
Подсчет единичных битов (Hamming weight)
"""
count = 0
while n:
# Удаляем младший установленный бит
n &= (n - 1)
count += 1
return count
# Альтернативные способы
def hammingWeight2(n):
return bin(n).count('1')
def hammingWeight3(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
128. Single Number
Описание: Найти элемент, встречающийся один раз в массиве, где все остальные встречаются дважды.
def singleNumber(nums):
"""
Поиск единственного элемента (используя XOR)
"""
result = 0
for num in nums:
result ^= num
return result
129. Single Number II
Описание: Найти элемент, встречающийся один раз в массиве, где все остальные встречаются трижды.
def singleNumber(nums):
"""
Поиск единственного элемента (все остальные встречаются 3 раза)
"""
ones = 0 # Биты, появившиеся один раз
twos = 0 # Биты, появившиеся два раза
for num in nums:
# Добавляем в ones, если не в twos
ones = (ones ^ num) & ~twos
# Добавляем в twos, если не в ones
twos = (twos ^ num) & ~ones
return ones
# Альтернативное решение с подсчетом битов
def singleNumber2(nums):
result = 0
for i in range(32):
count = 0
for num in nums:
# Считаем i-й бит
if (num >> i) & 1:
count += 1
# Если количество не кратно 3, устанавливаем бит
if count % 3:
result |= (1 << i)
# Преобразуем в signed 32-bit integer
if result >= (1 << 31):
result -= (1 << 32)
return result
130. Bitwise AND of Numbers Range
Описание: Найти побитовое И всех чисел в диапазоне [left, right].
def rangeBitwiseAnd(left, right):
"""
Побитовое И чисел в диапазоне
"""
shift = 0
# Находим общий префикс
while left < right:
left >>= 1
right >>= 1
shift += 1
# Возвращаем общий префикс с добавлением нулей
return left << shift
# Альтернативное решение
def rangeBitwiseAnd2(left, right):
while left < right:
# Удаляем младший бит справа
right &= (right - 1)
return right
131. Palindrome Number
Описание: Проверить, является ли целое число палиндромом.
def isPalindrome(x):
"""
Проверка, является ли число палиндромом
"""
# Отрицательные числа не могут быть палиндромами
if x < 0:
return False
original = x
reversed_num = 0
while x > 0:
digit = x % 10
reversed_num = reversed_num * 10 + digit
x //= 10
return original == reversed_num
# Решение без использования дополнительной памяти
def isPalindrome2(x):
if x < 0 or (x % 10 == 0 and x != 0):
return False
reversed_half = 0
while x > reversed_half:
reversed_half = reversed_half * 10 + x % 10
x //= 10
return x == reversed_half or x == reversed_half // 10
132. Plus One
Описание: Увеличить большое число, представленное массивом цифр, на 1.
def plusOne(digits):
"""
Увеличение числа, представленного массивом цифр, на 1
"""
n = len(digits)
for i in range(n - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1
return digits
digits[i] = 0
# Если все цифры были 9
return [1] + digits
# Рекурсивное решение
def plusOneRecursive(digits):
def helper(idx):
if idx < 0:
digits.insert(0, 1)
elif digits[idx] == 9:
digits[idx] = 0
helper(idx - 1)
else:
digits[idx] += 1
helper(len(digits) - 1)
return digits
133. Factorial Trailing Zeroes
Описание: Найти количество нулей в конце n!.
def trailingZeroes(n):
"""
Подсчет нулей в конце факториала
"""
count = 0
# Считаем количество множителей 5
while n > 0:
n //= 5
count += n
return count
# Рекурсивное решение
def trailingZeroesRecursive(n):
if n == 0:
return 0
return n // 5 + trailingZeroesRecursive(n // 5)
134. Sqrt(x)
Описание: Вычислить целочисленный квадратный корень.
def mySqrt(x):
"""
Вычисление целочисленного квадратного корня
"""
if x < 2:
return x
left, right = 1, x // 2
while left <= right:
mid = (left + right) // 2
square = mid * mid
if square == x:
return mid
elif square < x:
left = mid + 1
else:
right = mid - 1
return right # Округляем вниз
# Метод Ньютона (быстрее)
def mySqrtNewton(x):
if x < 2:
return x
guess = x // 2
while guess * guess > x:
guess = (guess + x // guess) // 2
return guess
135. Pow(x, n)
Описание: Вычислить x в степени n.
def myPow(x, n):
"""
Быстрое возведение в степень
"""
if n == 0:
return 1
if n < 0:
x = 1 / x
n = -n
result = 1
current_product = x
while n > 0:
if n % 2 == 1:
result *= current_product
current_product *= current_product
n //= 2
return result
# Рекурсивное решение
def myPowRecursive(x, n):
if n == 0:
return 1
if n < 0:
return 1 / myPowRecursive(x, -n)
half = myPowRecursive(x, n // 2)
if n % 2 == 0:
return half * half
else:
return half * half * x
136. Max Points on a Line
Описание: Найти максимальное количество точек, лежащих на одной прямой.
from collections import defaultdict
import math
def maxPoints(points):
"""
Максимальное количество точек на одной прямой
"""
n = len(points)
if n < 3:
return n
max_points = 1
for i in range(n):
slopes = defaultdict(int)
same_points = 1 # Текущая точка
for j in range(i + 1, n):
x1, y1 = points[i]
x2, y2 = points[j]
# Одинаковые точки
if x1 == x2 and y1 == y2:
same_points += 1
continue
# Вертикальная линия
if x1 == x2:
slope = float('inf')
else:
# Используем дробь для представления наклона
dx = x2 - x1
dy = y2 - y1
gcd_val = math.gcd(dx, dy)
slope = (dx // gcd_val, dy // gcd_val)
slopes[slope] += 1
# Находим максимальное количество точек для текущей точки
current_max = same_points
if slopes:
current_max = max(current_max, same_points + max(slopes.values()))
max_points = max(max_points, current_max)
return max_points
137. Climbing Stairs
Описание: Найти количество способов подняться по лестнице из n ступенек.
def climbStairs(n):
"""
Количество способов подняться по лестнице (фибоначчи)
"""
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Оптимизированное решение (O(1) памяти)
def climbStairsOptimized(n):
if n <= 2:
return n
prev1, prev2 = 2, 1 # для i=2 и i=1
for i in range(3, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
# Используя формулу Бине
def climbStairsFormula(n):
sqrt5 = 5 ** 0.5
phi = (1 + sqrt5) / 2
return int((phi ** (n + 1) - (1 - phi) ** (n + 1)) / sqrt5)
138. House Robber
Описание: Максимизировать сумму кражи, не грабя два соседних дома.
def rob(nums):
"""
Максимальная сумма без грабежа соседних домов
"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
# Оптимизированное решение
def robOptimized(nums):
prev1 = prev2 = 0
for num in nums:
current = max(prev1, prev2 + num)
prev2 = prev1
prev1 = current
return prev1
139. Word Break
Описание: Определить, можно ли разбить строку на слова из словаря.
def wordBreak(s, wordDict):
"""
Проверка возможности разбиения строки на слова из словаря
"""
word_set = set(wordDict)
n = len(s)
# dp[i] = можно ли разбить s[:i]
dp = [False] * (n + 1)
dp[0] = True # Пустая строка
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]
# С оптимизацией по максимальной длине слова
def wordBreakOptimized(s, wordDict):
word_set = set(wordDict)
max_len = max(len(word) for word in wordDict) if wordDict else 0
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(max(0, i - max_len), i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]
140. Coin Change
Описание: Найти минимальное количество монет для суммы.
def coinChange(coins, amount):
"""
Минимальное количество монет для суммы
"""
# dp[i] = минимальное количество монет для суммы i
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# Другая реализация
def coinChange2(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if i >= coin:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
141. Longest Increasing Subsequence
Описание: Найти длину самой длинной возрастающей подпоследовательности.
def lengthOfLIS(nums):
"""
Длина самой длинной возрастающей подпоследовательности
"""
if not nums:
return 0
n = len(nums)
dp = [1] * n # dp[i] = LIS заканчивающаяся на nums[i]
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# Оптимизированное решение с бинарным поиском O(n log n)
def lengthOfLISOptimized(nums):
tails = [] # tails[i] = минимальное последнее значение LIS длины i+1
for num in nums:
# Бинарный поиск позиции для вставки
left, right = 0, len(tails)
while left < right:
mid = (left + right) // 2
if tails[mid] < num:
left = mid + 1
else:
right = mid
if left == len(tails):
tails.append(num)
else:
tails[left] = num
return len(tails)
142. Triangle
Описание: Найти минимальную сумму пути от вершины до основания треугольника.
def minimumTotal(triangle):
"""
Минимальная сумма пути в треугольнике
"""
if not triangle:
return 0
n = len(triangle)
# Начинаем с предпоследней строки
for i in range(n - 2, -1, -1):
for j in range(len(triangle[i])):
triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])
return triangle[0][0]
# С дополнительной памятью
def minimumTotal2(triangle):
if not triangle:
return 0
n = len(triangle)
dp = triangle[-1][:] # Копируем последнюю строку
for i in range(n - 2, -1, -1):
for j in range(len(triangle[i])):
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
return dp[0]
143. Minimum Path Sum
Описание: Найти минимальную сумму пути от левого верхнего до правого нижнего угла сетки.
def minPathSum(grid):
"""
Минимальная сумма пути в сетке
"""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
# Инициализируем первую строку и первый столбец
for i in range(1, m):
grid[i][0] += grid[i - 1][0]
for j in range(1, n):
grid[0][j] += grid[0][j - 1]
# Заполняем остальные ячейки
for i in range(1, m):
for j in range(1, n):
grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
return grid[m - 1][n - 1]
# С дополнительной памятью
def minPathSum2(grid):
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
# Первая строка
for j in range(1, n):
dp[0][j] = dp[0][j - 1] + grid[0][j]
# Первый столбец
for i in range(1, m):
dp[i][0] = dp[i - 1][0] + grid[i][0]
# Остальные ячейки
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
return dp[m - 1][n - 1]
144. Unique Paths II
Описание: Найти количество уникальных путей в сетке с препятствиями.
def uniquePathsWithObstacles(obstacleGrid):
"""
Количество уникальных путей с препятствиями
"""
if not obstacleGrid or not obstacleGrid[0]:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
# Если начало или конец заблокированы
if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
return 0
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1
# Первая строка
for j in range(1, n):
if obstacleGrid[0][j] == 0:
dp[0][j] = dp[0][j - 1]
# Первый столбец
for i in range(1, m):
if obstacleGrid[i][0] == 0:
dp[i][0] = dp[i - 1][0]
# Остальные ячейки
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 0:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
# Оптимизированная версия с O(n) памяти
def uniquePathsWithObstaclesOptimized(obstacleGrid):
if not obstacleGrid or not obstacleGrid[0]:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
return 0
dp = [0] * n
dp[0] = 1
for i in range(m):
for j in range(n):
if obstacleGrid[i][j] == 1:
dp[j] = 0
elif j > 0:
dp[j] += dp[j - 1]
return dp[n - 1]
145. Longest Palindromic Substring
Описание: Найти самую длинную палиндромную подстроку.
def longestPalindrome(s):
"""
Поиск самой длинной палиндромной подстроки
"""
if not s:
return ""
n = len(s)
start, max_len = 0, 1
# dp[i][j] = является ли s[i:j+1] палиндромом
dp = [[False] * n for _ in range(n)]
# Все подстроки длины 1 - палиндромы
for i in range(n):
dp[i][i] = True
# Подстроки длины 2
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
start = i
max_len = 2
# Подстроки длины >= 3
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
if length > max_len:
start = i
max_len = length
return s[start:start + max_len]
# Оптимизированное решение с расширением от центра
def longestPalindromeOptimized(s):
if not s:
return ""
def expand_around_center(left, right):
"""Расширяемся от центра, пока символы совпадают"""
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1 # Длина палиндрома
start, end = 0, 0
for i in range(len(s)):
# Нечетная длина (центр - один символ)
len1 = expand_around_center(i, i)
# Четная длина (центр - два символа)
len2 = expand_around_center(i, i + 1)
length = max(len1, len2)
if length > (end - start):
start = i - (length - 1) // 2
end = i + length // 2
return s[start:end + 1]
146. Interleaving String
Описание: Проверить, является ли строка s3 интерливингом строк s1 и s2.
def isInterleave(s1, s2, s3):
"""
Проверка, является ли s3 интерливингом s1 и s2
"""
if len(s1) + len(s2) != len(s3):
return False
m, n = len(s1), len(s2)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# Только s1
for i in range(1, m + 1):
dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
# Только s2
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
# Оба
for i in range(1, m + 1):
for j in range(1, n + 1):
# Проверяем, можем ли взять символ из s1 или из s2
take_from_s1 = dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]
take_from_s2 = dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
dp[i][j] = take_from_s1 or take_from_s2
return dp[m][n]
147. Edit Distance
Описание: Найти минимальное количество операций для преобразования одной строки в другую.
def minDistance(word1, word2):
"""
Минимальное расстояние редактирования (Левенштейн)
"""
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Инициализация
for i in range(m + 1):
dp[i][0] = i # Удаление всех символов из word1
for j in range(n + 1):
dp[0][j] = j # Вставка всех символов в word1
# Заполнение таблицы
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # Символы совпадают
else:
# Выбираем минимальную операцию
dp[i][j] = 1 + min(
dp[i - 1][j], # Удаление
dp[i][j - 1], # Вставка
dp[i - 1][j - 1] # Замена
)
return dp[m][n]
# Оптимизированная версия с O(n) памяти
def minDistanceOptimized(word1, word2):
m, n = len(word1), len(word2)
prev = [0] * (n + 1)
# Инициализация первой строки
for j in range(n + 1):
prev[j] = j
for i in range(1, m + 1):
curr = [0] * (n + 1)
curr[0] = i # Удаление i символов
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
curr[j] = prev[j - 1]
else:
curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
prev = curr
return prev[n]
148. Best Time to Buy and Sell Stock III
Описание: Максимальная прибыль при максимум двух сделках.
def maxProfit(prices):
"""
Максимальная прибыль при максимум двух сделках
"""
if not prices:
return 0
n = len(prices)
# Первая транзакция: слева направо
first_profit = [0] * n
min_price = prices[0]
for i in range(1, n):
min_price = min(min_price, prices[i])
first_profit[i] = max(first_profit[i - 1], prices[i] - min_price)
# Вторая транзакция: справа налево
second_profit = [0] * n
max_price = prices[-1]
for i in range(n - 2, -1, -1):
max_price = max(max_price, prices[i])
second_profit[i] = max(second_profit[i + 1], max_price - prices[i])
# Находим максимальную общую прибыль
max_total = 0
for i in range(n):
max_total = max(max_total, first_profit[i] + second_profit[i])
return max_total
# Оптимизированная версия
def maxProfitOptimized(prices):
if not prices:
return 0
# 4 состояния: после первой покупки, первой продажи, второй покупки, второй продажи
buy1 = buy2 = float('-inf')
sell1 = sell2 = 0
for price in prices:
# Первая покупка
buy1 = max(buy1, -price)
# Первая продажа
sell1 = max(sell1, buy1 + price)
# Вторая покупка (используем прибыль от первой продажи)
buy2 = max(buy2, sell1 - price)
# Вторая продажа
sell2 = max(sell2, buy2 + price)
return sell2
149. Best Time to Buy and Sell Stock IV
Описание: Максимальная прибыль при максимум k сделках.
def maxProfit(k, prices):
"""
Максимальная прибыль при максимум k сделках
"""
n = len(prices)
if k == 0 or n < 2:
return 0
# Если k достаточно велико, можно совершать любые сделки
if k >= n // 2:
profit = 0
for i in range(1, n):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profit
# dp[i][j] = максимальная прибыль после i сделок до дня j
dp = [[0] * n for _ in range(k + 1)]
for transaction in range(1, k + 1):
max_diff = -prices[0] # Максимальная разница после transaction-1 сделок
for day in range(1, n):
# Либо не совершаем сделку в день j, либо совершаем
dp[transaction][day] = max(
dp[transaction][day - 1], # Не продаем
prices[day] + max_diff # Продаем
)
# Обновляем max_diff для следующего дня
max_diff = max(max_diff, dp[transaction - 1][day] - prices[day])
return dp[k][n - 1]
# Оптимизированная версия с O(n) памяти
def maxProfitOptimized(k, prices):
n = len(prices)
if k == 0 or n < 2:
return 0
if k >= n // 2:
profit = 0
for i in range(1, n):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profit
# buy[j] = максимальная прибыль после j покупок
# sell[j] = максимальная прибыль после j продаж
buy = [float('-inf')] * (k + 1)
sell = [0] * (k + 1)
for price in prices:
for j in range(1, k + 1):
buy[j] = max(buy[j], sell[j - 1] - price)
sell[j] = max(sell[j], buy[j] + price)
return sell[k]
150. Maximal Square
Описание: Найти максимальный квадрат из '1' в бинарной матрице.
def maximalSquare(matrix):
"""
Максимальный квадрат из '1' в матрице
"""
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_side = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if matrix[i - 1][j - 1] == '1':
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
max_side = max(max_side, dp[i][j])
return max_side * max_side
# Оптимизированная версия с O(n) памяти
def maximalSquareOptimized(matrix):
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
dp = [0] * (n + 1)
max_side = 0
prev = 0 # Для хранения dp[i-1][j-1]
for i in range(1, m + 1):
for j in range(1, n + 1):
temp = dp[j] # Сохраняем для следующей итерации
if matrix[i - 1][j - 1] == '1':
dp[j] = min(dp[j], dp[j - 1], prev) + 1
max_side = max(max_side, dp[j])
else:
dp[j] = 0
prev = temp
return max_side * max_side
Ключевые моменты пятого блока:
- Heap и приоритетные очереди (121-124): QuickSelect, IPO, медиана из потока
- Битовые операции (125-130): Двоичная арифметика, подсчет битов, битовые маски
- Математические задачи (131-136): Числа, степени, геометрия
- Динамическое программирование (137-150): Классические задачи DP
Основные алгоритмы:
- QuickSelect для k-го элемента
- Две кучи для медианы из потока
- Алгоритм Кадане для максимального подмассива
- Двоичный поиск для LIS
- Динамическое программирование в 2D
Сложности:
- Heap задачи: O(n log k) или O(n log n)
- DP задачи: O(n²) или O(nm) для 2D задач
- Битовые операции: O(1) или O(n)