Привет, тебе налили? 🍻
Сегодня я, ваш надежный друг и опытный программист, расскажу, как не превратить свою жизнь в бесконечный аэропорт с потерянными билетами и пересадками. Поставьте себе стаканчик сока, расслабьтесь и слушайте.
Что нового под солнцем? ☀️
Вы узнаете, как алгоритмы на графах могут помочь вам в реальной жизни. Ну, или хотя бы в этой задаче с LeetCode.
Сюжет таинственного расследования 🕵️♂️
Задача весьма интересная: у вас есть куча билетов от аэропорта к аэропорту. Ваша задача — собрать их все в один маршрут, начиная с "JFK". И да, не забудьте, что существует не один маршрут, а много. Но нам нужен самый "алфавитный" из них.
Чтобы не теряться, лучше ознакомьтесь с полным условием задачи на LeetCode
Графы, но не в том смысле 🤔
Перед тем, как решить эту задачу, давайте поймем, что такое граф в программировании. Нет, это не кружок с фамильным гербом, это структура данных, состоящая из узлов и ребер. Интересный факт: этот граф не имеет графинь, но у него есть вершины и ребра! 😅
Собираем все билеты в одну кучу 🎫🎫
Первым делом, давайте отсортируем все наши билеты в лексикографическом порядке. Потому что нам не просто куда-то лететь, нам нужно лететь со стилем.
# Сортируем билеты. Важно: переворачиваем список,
# чтобы попозже доставать элементы с конца (это быстрее)
tickets.sort(key=lambda x: x[1], reverse=True)
Словарь маршрутов: от каждого аэропорта к каждому 🛫🌍
Теперь создадим словарь flights, который будет хранить все возможные маршруты от каждого аэропорта.
from collections import defaultdict
# Инициализируем словарь маршрутов
flights = defaultdict(list)
# Заполняем его
for src, dst in tickets:
flights[src].append(dst)
⚠️А, забыл рассказать про defaultdict! Это не просто какой-то там словарь, это словарь с понтами! 🎩👑 В обычном словаре, если вы пытаетесь получить значение по ключу, которого нет, Python вас накажет KeyError. А defaultdict — он не такой, он понимающий. Если ключа нет, он просто создаст новую запись с этим ключом и дефолтным значением, которое вы ему укажете.
Итак, представим, что defaultdict — это как хороший бармен 🍻. Вы приходите в бар и просите виски. Если виски нет, обычный бармен скажет: "У нас нет виски, уходите" (KeyError). Но не defaultdict! Он скажет: "У нас нет виски, но держите пиво, пока я не принесу виски" и пойдет искать вам ваше виски (или просто поставит дефолтное значение).
DFS: не Depth-First Search, а "Don't Forget Scotch" 🥃🔍
DFS — это аббревиатура от "Depth-First Search", или "Поиск в глубину" на русском. Представьте, что у вас есть лабиринт, и вам нужно найти выход. Вместо того, чтобы бродить без цели, вы решаете всегда идти вперёд, пока не упрётесь в тупик. Как только это происходит, вы возвращаетесь назад и пробуете другой путь. И так до тех пор, пока не найдете выход.
В программировании DFS часто используется для обхода графов и деревьев. Суть такова: вы начинаете с какой-то стартовой вершины и двигаетесь вперёд, пока не достигнете конца. Потом возвращаетесь на шаг назад и снова двигаетесь вперёд, и так далее. Всё это удобно делать с помощью рекурсии.
Теперь представьте, что каждый перелёт между аэропортами — это переход от одной вершины графа к другой. DFS помогает нам "пройти" все эти перелёты так, чтобы в итоге у нас получился правильный маршрут.
Вообще, в реальной жизни такой подход к выбору маршрута скорее всего приведёт к потере всех денег и времени. Но в программировании — это часто оптимальный способ решить задачу! 😄👍
# Итоговый маршрут будет храниться здесь
route = []
# Наш DFS
def dfs(airport):
while flights[airport]:
dfs(flights[airport].pop())
route.append(airport)
Финальный код: 🤖🎬
Хватит разговоров, давайте к делу!
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
# DFS функция, или "Don't Forget Scotch" — так, я знаю, это рекурсия,
# не DFS, но кто вообще заметит?
def dfs(src):
while adj_list[src]:
# pop(0) — это как взять самый старый
# сыр из холодильника.
# Первым пришёл — первым и ушёл.
dfs(adj_list[src].pop(0))
# Добавляем аэропорт в маршрут,
# как бармен добавляет виски в ваш стакан
itinerary.append(src)
# Здесь мы создаём своего рода "социальную сеть"
# для аэропортов. Да-да, Facebook для аэропортов.
adj_list = defaultdict(list)
for src, dst in sorted(tickets): # Сортируем, потому что мы не варвары!
adj_list[src].append(dst) # Всё как в жизни: каждый знает, куда лететь.
# Это будет наш маршрут, пока что пуст,
# как мой стакан в пятницу вечером
itinerary = []
# Начнём с JFK, потому что все пути ведут
# через JFK. Ну или почти все.
dfs("JFK")
# Возвращаем маршрут в правильном порядке,
# потому что мы не из тех, кто читает книги с конца!
return itinerary[::-1]
Асимптотика 🚀
Давайте поговорим о том, как быстро наш код умеет летать. Сложность алгоритма — это O(n log n). Почему? Хитрые сортировки тут как раз и пригодятся. Мы используем сортировку при сборе всех билетов, а также при поиске следующего билета на нашем пути. Но это быстро, как сверхзвуковой самолет! 🛫
В истории с Шерлоком и графами 🕵️♂️📚
Эта задача — классический пример задачи на поиск в глубину (Depth-First Search, или просто DFS). Не пугайтесь, это просто как "вычеркивание" всех возможных вариантов в вашем детективном блокноте, пока вы не найдете того единственно верного.
Чтение — это сила 📚
Анекдот
Шерлок Холмс и доктор Ватсон решают провести выходные на кемпинге. После хорошего ужина и бутылки вина они ложатся спать в палатку. Через несколько часов Шерлок толкает Ватсона и говорит:
— Ватсон, посмотрите на небо и скажите, что вы видите.
— Я вижу миллионы звёзд, Шерлок.
— И что вы из этого заключаете?
— Астрономически, это значит, что во Вселенной миллионы галактик и, возможно, миллиарды планет. Астрологически, Сатурн в льве. Часовым углом, примерно четверть третьего. Теологически, видно, что Господь всемогущ. Метеорологически, завтра будет красивый день. А что вы из этого заключаете, Шерлок?
— Ватсон, кто-то украл наш Wi-Fi !!!!
В жизни, как и в программировании, иногда самые сложные проблемы имеют самые простые решения. Не забывайте об этом, друзья! 😄🕵️♂️🎫