LeetCode 重新安排行程题解

LeetCode 重新安排行程题解题目描述给定一个机票列表从起点出发重新安排行程。示例输入tickets [[MUC,LHR],[JFK,MUC],[SFO,SJC],[LHR,SFO]]输出[JFK,MUC,LHR,SFO,SJC]解题思路方法Hierholzer 算法思路使用 Hierholzer 算法找到欧拉路径。使用字典存储每个起点的所有目的地并排序。从 JFK 开始递归地遍历所有目的地。复杂度分析时间复杂度O(E log E)。空间复杂度O(E)。代码实现from collections import defaultdict def find_itinerary(tickets): graph defaultdict(list) for src, dst in tickets: graph[src].append(dst) for src in graph: graph[src].sort() result [] def dfs(src): while graph[src]: dst graph[src].pop(0) dfs(dst) result.append(src) dfs(JFK) return result[::-1] # 测试 def test_find_itinerary(): tickets [[MUC, LHR], [JFK, MUC], [SFO, SJC], [LHR, SFO]] print(find_itinerary(tickets)) # 输出[JFK, MUC, LHR, SFO, SJC] if __name__ __main__: test_find_itinerary()总结重新安排行程是 Hierholzer 算法的典型应用找到欧拉路径。