← Назад к курсу
Решение задач с LeetCode TOP-150 (Блок 2/5: Задачи 31-60)
31. Longest Substring Without Repeating Characters
Описание: Найти длину самой длинной подстроки без повторяющихся символов.
def lengthOfLongestSubstring(s):
"""
Длина самой длинной подстроки без повторений
Используем sliding window с hashmap
"""
char_index = {} # Храним последний индекс каждого символа
max_length = 0
left = 0
for right, char in enumerate(s):
# Если символ уже встречался и находится в текущем окне
if char in char_index and char_index[char] >= left:
# Сдвигаем левую границу окна
left = char_index[char] + 1
# Обновляем индекс символа
char_index[char] = right
# Обновляем максимальную длину
max_length = max(max_length, right - left + 1)
return max_length
32. Substring with Concatenation of All Words
Описание: Найти все начальные индексы подстрок, содержащих все слова из списка.
from collections import Counter
def findSubstring(s, words):
"""
Поиск всех индексов, где начинается конкатенация всех слов
"""
if not s or not words:
return []
word_len = len(words[0])
total_len = len(words) * word_len
word_count = Counter(words)
result = []
# Проверяем все возможные начальные позиции
for i in range(len(s) - total_len + 1):
seen = {}
j = 0
while j < len(words):
# Берем слово из строки
word_start = i + j * word_len
word = s[word_start:word_start + word_len]
# Если слова нет в списке или превышено количество
if word not in word_count:
break
seen[word] = seen.get(word, 0) + 1
if seen[word] > word_count[word]:
break
j += 1
# Если нашли все слова
if j == len(words):
result.append(i)
return result
33. Minimum Window Substring
Описание: Найти минимальную подстроку, содержащую все символы искомой строки.
from collections import Counter
def minWindow(s, t):
"""
Минимальное окно, содержащее все символы строки t
"""
if not s or not t:
return ""
# Счетчик символов в t
t_count = Counter(t)
required = len(t_count) # Количество уникальных символов, которые нужно найти
# Счетчики для текущего окна
window_count = {}
formed = 0 # Количество символов, найденных с нужной частотой
left = 0
min_len = float('inf')
min_window = ""
for right in range(len(s)):
char = s[right]
window_count[char] = window_count.get(char, 0) + 1
# Если частота символа совпала с требуемой
if char in t_count and window_count[char] == t_count[char]:
formed += 1
# Пытаемся сжать окно слева
while left <= right and formed == required:
# Обновляем минимальное окно
if right - left + 1 < min_len:
min_len = right - left + 1
min_window = s[left:right+1]
# Убираем символ слева
left_char = s[left]
window_count[left_char] -= 1
if left_char in t_count and window_count[left_char] < t_count[left_char]:
formed -= 1
left += 1
return min_window
34. Valid Sudoku
Описание: Проверить, является ли частично заполненное судоку валидным.
def isValidSudoku(board):
"""
Проверка валидности судоку
"""
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for i in range(9):
for j in range(9):
num = board[i][j]
if num == '.':
continue
# Проверка строки
if num in rows[i]:
return False
rows[i].add(num)
# Проверка столбца
if num in cols[j]:
return False
cols[j].add(num)
# Проверка блока 3x3
box_idx = (i // 3) * 3 + (j // 3)
if num in boxes[box_idx]:
return False
boxes[box_idx].add(num)
return True
35. Spiral Matrix
Описание: Вернуть все элементы матрицы в спиральном порядке.
def spiralOrder(matrix):
"""
Обход матрицы по спирали
"""
if not matrix:
return []
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
# Верхняя строка слева направо
for j in range(left, right + 1):
result.append(matrix[top][j])
top += 1
# Правый столбец сверху вниз
for i in range(top, bottom + 1):
result.append(matrix[i][right])
right -= 1
# Нижняя строка справа налево (если есть строки)
if top <= bottom:
for j in range(right, left - 1, -1):
result.append(matrix[bottom][j])
bottom -= 1
# Левый столбец снизу вверх (если есть столбцы)
if left <= right:
for i in range(bottom, top - 1, -1):
result.append(matrix[i][left])
left += 1
return result
36. Rotate Image
Описание: Повернуть изображение (матрицу) на 90 градусов по часовой стрелке.
def rotate(matrix):
"""
Поворот матрицы на 90 градусов по часовой стрелке in-place
"""
n = len(matrix)
# Транспонирование матрицы
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Отражение по вертикали
for i in range(n):
for j in range(n // 2):
matrix[i][j], matrix[i][n - 1 - j] = matrix[i][n - 1 - j], matrix[i][j]
37. Set Matrix Zeroes
Описание: Установить нули в строке и столбце, если элемент матрицы равен нулю.
def setZeroes(matrix):
"""
Установка нулей в строках и столбцах, содержащих нули
Используем O(1) дополнительной памяти
"""
if not matrix:
return
m, n = len(matrix), len(matrix[0])
first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))
# Используем первую строку и первый столбец как маркеры
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# Устанавливаем нули на основе маркеров
for i in range(1, m):
if matrix[i][0] == 0:
for j in range(1, n):
matrix[i][j] = 0
for j in range(1, n):
if matrix[0][j] == 0:
for i in range(1, m):
matrix[i][j] = 0
# Обрабатываем первую строку и первый столбец
if first_row_has_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_has_zero:
for i in range(m):
matrix[i][0] = 0
38. Game of Life
Описание: Реализовать игру "Жизнь" Конвея in-place.
def gameOfLife(board):
"""
Игра "Жизнь" Конвея in-place
Используем специальные значения для обозначения переходов
"""
if not board:
return
m, n = len(board), len(board[0])
# Вспомогательная функция для подсчета живых соседей
def count_live_neighbors(i, j):
count = 0
for dx in [-1, 0, 1]:
for dy in [-1, 0, 1]:
if dx == 0 and dy == 0:
continue
ni, nj = i + dx, j + dy
if 0 <= ni < m and 0 <= nj < n:
# Учитываем текущее состояние или переход в мертвое
if board[ni][nj] in [1, 2]:
count += 1
return count
# Первый проход: отмечаем переходы
# 0 -> 0: остается мертвым
# 1 -> 0: живой становится мертвым (помечаем как 2)
# 0 -> 1: мертвый становится живым (помечаем как 3)
# 1 -> 1: остается живым
for i in range(m):
for j in range(n):
live_neighbors = count_live_neighbors(i, j)
if board[i][j] == 1: # Сейчас живой
if live_neighbors < 2 or live_neighbors > 3:
board[i][j] = 2 # Умирает
else: # Сейчас мертвый
if live_neighbors == 3:
board[i][j] = 3 # Оживает
# Второй проход: обновляем значения
for i in range(m):
for j in range(n):
if board[i][j] == 2:
board[i][j] = 0
elif board[i][j] == 3:
board[i][j] = 1
39. Ransom Note
Описание: Проверить, можно ли составить ransomNote из букв magazine.
from collections import Counter
def canConstruct(ransomNote, magazine):
"""
Проверка возможности составить ransomNote из magazine
"""
ransom_count = Counter(ransomNote)
magazine_count = Counter(magazine)
# Проверяем, что для каждой буквы в ransomNote хватает в magazine
for char, count in ransom_count.items():
if magazine_count.get(char, 0) < count:
return False
return True
40. Isomorphic Strings
Описание: Проверить, являются ли строки изоморфными (один-к-одному замена символов).
def isIsomorphic(s, t):
"""
Проверка изоморфности строк
"""
if len(s) != len(t):
return False
s_to_t = {}
t_to_s = {}
for char_s, char_t in zip(s, t):
# Проверяем соответствие s -> t
if char_s in s_to_t:
if s_to_t[char_s] != char_t:
return False
else:
s_to_t[char_s] = char_t
# Проверяем соответствие t -> s (обратное)
if char_t in t_to_s:
if t_to_s[char_t] != char_s:
return False
else:
t_to_s[char_t] = char_s
return True
41. Word Pattern
Описание: Проверить, соответствует ли строка pattern разделенной на слова строке s.
def wordPattern(pattern, s):
"""
Проверка соответствия pattern словам в s
"""
words = s.split()
if len(pattern) != len(words):
return False
char_to_word = {}
word_to_char = {}
for char, word in zip(pattern, words):
# Проверяем соответствие char -> word
if char in char_to_word:
if char_to_word[char] != word:
return False
else:
char_to_word[char] = word
# Проверяем соответствие word -> char
if word in word_to_char:
if word_to_char[word] != char:
return False
else:
word_to_char[word] = char
return True
42. Valid Anagram
Описание: Проверить, являются ли строки анаграммами.
from collections import Counter
def isAnagram(s, t):
"""
Проверка, являются ли строки анаграммами
"""
if len(s) != len(t):
return False
return Counter(s) == Counter(t)
# Альтернативное решение без Counter
def isAnagram2(s, t):
if len(s) != len(t):
return False
char_count = [0] * 26 # Для английских букв
for char in s:
char_count[ord(char) - ord('a')] += 1
for char in t:
char_count[ord(char) - ord('a')] -= 1
# Все счетчики должны быть нулями
return all(count == 0 for count in char_count)
43. Group Anagrams
Описание: Сгруппировать строки по анаграммам.
from collections import defaultdict
def groupAnagrams(strs):
"""
Группировка строк по анаграммам
"""
anagrams = defaultdict(list)
for word in strs:
# Сортируем буквы слова, чтобы использовать как ключ
sorted_word = ''.join(sorted(word))
anagrams[sorted_word].append(word)
return list(anagrams.values())
44. Two Sum
Описание: Найти индексы двух чисел, сумма которых равна target.
def twoSum(nums, target):
"""
Поиск индексов двух чисел с заданной суммой
"""
num_to_index = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_to_index:
return [num_to_index[complement], i]
num_to_index[num] = i
return []
45. Happy Number
Описание: Проверить, является ли число "счастливым".
def isHappy(n):
"""
Проверка, является ли число счастливым
"""
def get_next(num):
"""Вычисляет сумму квадратов цифр"""
total = 0
while num > 0:
digit = num % 10
total += digit * digit
num //= 10
return total
slow = fast = n
# Используем алгоритм Флойда для обнаружения цикла
while True:
slow = get_next(slow) # Один шаг
fast = get_next(get_next(fast)) # Два шага
if fast == 1:
return True
if slow == fast: # Обнаружен цикл
return False
46. Contains Duplicate II
Описание: Проверить, есть ли дубликаты в пределах расстояния k.
def containsNearbyDuplicate(nums, k):
"""
Проверка наличия дубликатов на расстоянии не более k
"""
num_indices = {}
for i, num in enumerate(nums):
if num in num_indices and i - num_indices[num] <= k:
return True
num_indices[num] = i
return False
47. Longest Consecutive Sequence
Описание: Найти длину самой длинной последовательной последовательности чисел.
def longestConsecutive(nums):
"""
Длина самой длинной последовательной последовательности
"""
if not nums:
return 0
num_set = set(nums)
max_length = 0
for num in num_set:
# Проверяем только начало последовательности
if num - 1 not in num_set:
current_num = num
current_length = 1
# Ищем всю последовательность
while current_num + 1 in num_set:
current_num += 1
current_length += 1
max_length = max(max_length, current_length)
return max_length
48. Summary Ranges
Описание: Создать список интервалов из отсортированного массива.
def summaryRanges(nums):
"""
Создание интервалов из отсортированного массива
"""
if not nums:
return []
result = []
start = nums[0]
for i in range(1, len(nums)):
# Если разрыв в последовательности
if nums[i] != nums[i-1] + 1:
if start == nums[i-1]:
result.append(str(start))
else:
result.append(f"{start}->{nums[i-1]}")
start = nums[i]
# Обрабатываем последний интервал
if start == nums[-1]:
result.append(str(start))
else:
result.append(f"{start}->{nums[-1]}")
return result
49. Merge Intervals
Описание: Объединить пересекающиеся интервалы.
def merge(intervals):
"""
Объединение пересекающихся интервалов
"""
if not intervals:
return []
# Сортируем интервалы по началу
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
# Если список пуст или интервалы не пересекаются
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
# Объединяем интервалы
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
50. Insert Interval
Описание: Вставить новый интервал в список непересекающихся интервалов.
def insert(intervals, newInterval):
"""
Вставка нового интервала
"""
result = []
i = 0
n = len(intervals)
# Добавляем все интервалы, которые заканчиваются до начала newInterval
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# Объединяем пересекающиеся интервалы
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
# Добавляем оставшиеся интервалы
while i < n:
result.append(intervals[i])
i += 1
return result
51. Minimum Number of Arrows to Burst Balloons
Описание: Найти минимальное количество стрел для лопанья всех шаров.
def findMinArrowShots(points):
"""
Минимальное количество стрел для лопанья всех шаров
"""
if not points:
return 0
# Сортируем по конечной точке
points.sort(key=lambda x: x[1])
arrows = 1
current_end = points[0][1]
for start, end in points[1:]:
# Если текущий шар не пересекается с предыдущим
if start > current_end:
arrows += 1
current_end = end
return arrows
52. Valid Parentheses
Описание: Проверить правильность расстановки скобок.
def isValid(s):
"""
Проверка правильности скобок
"""
stack = []
bracket_map = {')': '(', '}': '{', ']': '['}
for char in s:
if char in bracket_map.values(): # Открывающая скобка
stack.append(char)
elif char in bracket_map: # Закрывающая скобка
if not stack or stack[-1] != bracket_map[char]:
return False
stack.pop()
return not stack
53. Simplify Path
Описание: Упростить путь файловой системы Unix.
def simplifyPath(path):
"""
Упрощение Unix пути
"""
stack = []
components = path.split('/')
for component in components:
if component == '' or component == '.':
continue
elif component == '..':
if stack:
stack.pop()
else:
stack.append(component)
return '/' + '/'.join(stack)
54. Min Stack
Описание: Реализовать стек с поддержкой получения минимального элемента за O(1).
class MinStack:
def __init__(self):
"""
Инициализация стека
Используем два стека: основной и для минимумов
"""
self.stack = []
self.min_stack = []
def push(self, val):
"""
Добавление элемента
"""
self.stack.append(val)
# Добавляем в min_stack, если он пуст или новый элемент меньше/равен текущему минимуму
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
"""
Удаление верхнего элемента
"""
if self.stack:
val = self.stack.pop()
# Удаляем из min_stack, если это текущий минимум
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
"""
Получение верхнего элемента
"""
return self.stack[-1] if self.stack else None
def getMin(self):
"""
Получение минимального элемента
"""
return self.min_stack[-1] if self.min_stack else None
55. Evaluate Reverse Polish Notation
Описание: Вычислить выражение в обратной польской нотации.
def evalRPN(tokens):
"""
Вычисление выражения в обратной польской нотации
"""
stack = []
for token in tokens:
if token in '+-*/':
# Извлекаем два операнда
b = stack.pop()
a = stack.pop()
# Выполняем операцию
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
# В Python деление для отрицательных чисел работает иначе
stack.append(int(a / b)) # Используем int для округления к нулю
else:
stack.append(int(token))
return stack[0]
56. Basic Calculator
Описание: Вычислить базовое арифметическое выражение со скобками.
def calculate(s):
"""
Вычисление выражения со скобками и +-
"""
stack = []
num = 0
result = 0
sign = 1 # 1 для +, -1 для -
for char in s:
if char.isdigit():
num = num * 10 + int(char)
elif char == '+':
result += sign * num
num = 0
sign = 1
elif char == '-':
result += sign * num
num = 0
sign = -1
elif char == '(':
# Сохраняем текущий результат и знак
stack.append(result)
stack.append(sign)
# Сбрасываем для вычисления внутри скобок
result = 0
sign = 1
elif char == ')':
# Завершаем вычисление внутри скобок
result += sign * num
num = 0
# Восстанавливаем предыдущий знак и результат
result *= stack.pop() # знак перед скобками
result += stack.pop() # результат до скобок
# Добавляем последнее число
result += sign * num
return result
57. Linked List Cycle
Описание: Определить, есть ли цикл в связном списке.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def hasCycle(head):
"""
Проверка наличия цикла в связном списке
Алгоритм Флойда (черепаха и заяц)
"""
if not head or not head.next:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next # Один шаг
fast = fast.next.next # Два шага
if slow == fast: # Встречаются - есть цикл
return True
return False
58. Add Two Numbers
Описание: Сложить два числа, представленных в виде обратных связных списков.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1, l2):
"""
Сложение двух чисел, представленных обратными связными списками
"""
dummy = ListNode(0)
current = dummy
carry = 0
while l1 or l2 or carry:
# Суммируем значения и перенос
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
# Вычисляем новую цифру и перенос
digit = total % 10
carry = total // 10
# Создаем новый узел
current.next = ListNode(digit)
current = current.next
# Переходим к следующим узлам
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
59. Merge Two Sorted Lists
Описание: Объединить два отсортированных связных списка.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(list1, list2):
"""
Объединение двух отсортированных связных списков
"""
dummy = ListNode(0)
current = dummy
while list1 and list2:
if list1.val <= list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
# Добавляем оставшиеся узлы
if list1:
current.next = list1
elif list2:
current.next = list2
return dummy.next
60. Copy List with Random Pointer
Описание: Копировать связный список с указателями на случайные узлы.
class Node:
def __init__(self, x, next=None, random=None):
self.val = int(x)
self.next = next
self.random = random
def copyRandomList(head):
"""
Копирование связного списка с random указателями
"""
if not head:
return None
# Шаг 1: Создаем копии узлов и связываем их с оригиналами
current = head
while current:
# Создаем копию узла
copy = Node(current.val)
# Вставляем копию после оригинала
copy.next = current.next
current.next = copy
# Переходим к следующему оригинальному узлу
current = copy.next
# Шаг 2: Копируем random указатели
current = head
while current:
if current.random:
current.next.random = current.random.next
current = current.next.next
# Шаг 3: Разделяем два списка
dummy = Node(0)
copy_current = dummy
current = head
while current:
# Извлекаем копию
copy_current.next = current.next
copy_current = copy_current.next
# Восстанавливаем оригинальный список
current.next = copy_current.next
current = current.next
return dummy.next
Ключевые моменты второго блока:
- Sliding Window (31, 33): Оптимальный подход для подстрок
- Хеширование и множества (39-47): Эффективный поиск и группировка
- Интервалы (48-51): Сортировка и слияние интервалов
- Стек (52-56): Обработка вложенных структур
- Связные списки (57-60): Указатели, циклы, копирование
Сложности алгоритмов:
- Большинство решений имеют O(n) временную сложность
- Используется O(1) или O(n) дополнительной памяти
- Применяются классические алгоритмы (Флойда, два указателя и т.д.)