Word Ladder, Open the Lock, Course Schedule II.
Поиск кратчайшего пути в невзвешенном графе. Word Ladder, Open the Lock, Perfect Squares.
Условие:
Даны два слова beginWord и endWord, а также словарь wordList. Найдите длину кратчайшей последовательности преобразования от beginWord к endWord, где:
wordListВерните количество слов в кратчайшей последовательности или 0, если пути не существует.
Примеры:
Ввод: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Вывод: 5
Объяснение: "hit" -> "hot" -> "dot" -> "dog" -> "cog"
Ввод: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Вывод: 0
Ограничения:
💡 Подсказка: Используйте BFS. Для каждого слова генерируйте все возможные варианты с заменой одной буквы (26 × длина слова).
Решение:
from collections import deque
def ladderLength(beginWord, endWord, wordList):
if endWord not in wordList:
return 0
wordList = set(wordList)
queue = deque([(beginWord, 1)])
while queue:
word, steps = queue.popleft()
if word == endWord:
return steps
# Генерируем все варианты с одной изменённой буквой
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word in wordList:
wordList.remove(next_word) # Помечаем как посещённое
queue.append((next_word, steps + 1))
return 0Объяснение:
Сложность:
Условие:
Дано целое число n. Верните минимальное количество perfect square чисел (1, 4, 9, 16, ...), сумма которых равна n.
Примеры:
Ввод: n = 12
Вывод: 3
Объяснение: 12 = 4 + 4 + 4
Ввод: n = 13
Вывод: 2
Объяснение: 13 = 4 + 9
Ограничения:
💡 Подсказка: Используйте BFS. Каждый уровень представляет количество использованных квадратов.
Решение:
from collections import deque
def numSquares(n):
squares = [i*i for i in range(1, int(n**0.5) + 1)]
queue = deque([n])
level = 0
visited = {n}
while queue:
level += 1
for _ in range(len(queue)):
current = queue.popleft()
for sq in squares:
if current == sq:
return level
elif current < sq:
break
if current - sq not in visited:
visited.add(current - sq)
queue.append(current - sq)
return levelОбъяснение:
Сложность:
Условие: У вас есть замок с 4 круглыми дисками. Каждый диск имеет 10 цифр: '0'-'9'. Диски могут вращаться свободно.
Начальное состояние: '0000'. Дан список deadends — состояний, при которых замок блокируется. Дана цель target.
Верните минимальное количество поворотов для открытия замка или -1, если невозможно.
Примеры:
Ввод: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Вывод: 6
Ввод: deadends = ["8888"], target = "0009"
Вывод: 1
Ввод: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Вывод: -1
Ограничения:
💡 Подсказка: Используйте BFS. Из каждого состояния есть 8 переходов (4 позиции × 2 направления).
Решение:
from collections import deque
def openLock(deadends, target):
deadends = set(deadends)
if '0000' in deadends:
return -1
queue = deque([('0000', 0)])
visited = {'0000'}
while queue:
state, steps = queue.popleft()
if state == target:
return steps
# 4 позиции, 2 направления
for i in range(4):
for d in [-1, 1]:
next_digit = (int(state[i]) + d) % 10
next_state = state[:i] + str(next_digit) + state[i+1:]
if next_state not in visited and next_state not in deadends:
visited.add(next_state)
queue.append((next_state, steps + 1))
return -1Объяснение:
Сложность:
Условие:
Дана квадратная бинарная матрица n x n. Найдите кратчайший путь от левого верхнего угла (0,0) до правого нижнего (n-1, n-1).
Можно двигаться в 8 направлениях (горизонтально, вертикально, диагонально). Все клетки пути должны быть 0.
Примеры:
Ввод: grid = [[0,1],[1,0]]
Вывод: 2
Ввод: grid = [[0,0,0],[1,1,0],[1,1,0]]
Вывод: 4
Ввод: grid = [[1,0,0],[1,1,0],[1,1,0]]
Вывод: -1
Ограничения:
💡 Подсказка: Используйте BFS с 8 направлениями. Помечайте посещённые клетки, устанавливая grid[r][c] = 1.
Решение:
from collections import deque
def shortestPathBinaryMatrix(grid):
n = len(grid)
# Проверка начала и конца
if grid[0][0] or grid[-1][-1]:
return -1
queue = deque([(0, 0, 1)]) # (row, col, distance)
grid[0][0] = 1 # Помечаем как посещённое
directions = [(1,0), (-1,0), (0,1), (0,-1),
(1,1), (1,-1), (-1,1), (-1,-1)]
while queue:
r, c, dist = queue.popleft()
if r == n - 1 and c == n - 1:
return dist
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
grid[nr][nc] = 1
queue.append((nr, nc, dist + 1))
return -1Объяснение:
Сложность:
Условие:
Всего numCourses курсов, пронумерованных от 0 до numCourses - 1. Дан массив prerequisites, где prerequisites[i] = [ai, bi] означает, что для прохождения курса ai нужно сначала пройти курс bi.
Верните порядок прохождения курсов, чтобы закончить все курсы. Если это невозможно, верните пустой массив.
Примеры:
Ввод: numCourses = 2, prerequisites = [[1,0]]
Вывод: [0,1]
Ввод: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Вывод: [0,1,2,3] или [0,2,1,3]
Ввод: numCourses = 1, prerequisites = []
Вывод: [0]
Ограничения:
💡 Подсказка: Используйте топологическую сортировку (алгоритм Кана). Подсчитайте indegree для каждого курса и используйте BFS.
Решение:
from collections import deque
def findOrder(numCourses, prerequisites):
# Строим граф и считаем indegree
graph = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
# Начинаем с курсов без пререквизитов
queue = deque([i for i in range(numCourses) if indegree[i] == 0])
result = []
while queue:
course = queue.popleft()
result.append(course)
for neighbor in graph[course]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return result if len(result) == numCourses else []Объяснение:
Сложность:
| Задача | Ключевая идея |
|---|---|
| Word Ladder | Генерация 26 вариантов слова |
| Perfect Squares | BFS по остаткам |
| Open the Lock | 8 переходов из состояния |
| Shortest Path Binary Matrix | 8 направлений |
| Course Schedule II | Топологическая сортировка |
Проблема: В Word Ladder нужно помечать посещённые слова.
# ❌ Неправильно — нет visited
if next_word in wordList:
queue.append((next_word, steps + 1))
# wordList не изменён — может быть обработан снова!
# ✅ Правильно
if next_word in wordList:
wordList.remove(next_word) # Помечаем как посещённое
queue.append((next_word, steps + 1))Почему это неправильно: Без visited BFS зациклится или будет избыточно работать.
Проблема: Нужно обрабатывать переход 9→0 и 0→9.
# ❌ Неправильно — нет обработки перехода
next_digit = int(state[i]) + d # 9 + 1 = 10, а не 0!
# ✅ Правильно
next_digit = (int(state[i]) + d) % 10 # (9 + 1) % 10 = 0Почему это неправильно: Цифры на диске цикличны: 9→0 и 0→9.
Проблема: В Shortest Path нужно проверить, что старт и финиш проходимы.
# ❌ Неправильно — нет проверки
queue = deque([(0, 0, 1)])
# ✅ Правильно
if grid[0][0] or grid[-1][-1]:
return -1 # Начало или конец заблокированы
queue = deque([(0, 0, 1)])Почему это неправильно: Если (0,0) или (n-1,n-1) = 1, пути не существует.
BFS: Кратчайший путь — поиск кратчайшего пути в невзвешенном графе.
Ключевые приёмы:
Далее: Backtracking: Основы