计划在Python中以正确的顺序查找机场？
假设我们有一个航班列表，分别是[原点，目的地]对。列表被打乱了；我们必须找到以正确顺序访问的所有机场。如果有多个有效行程，请首先返回按字典顺序最小的行程。
因此，如果输入就像flights=[[“”Mumbai“，”Kolkata“]，[”Delhi“，”Mumbai“]，[”Kolkata“，”Delhi“]]]，那么输出将是['Delhi'，“孟买”，“加尔各答”，“德里”]
为了解决这个问题，我们将按照以下步骤
ins：=一个空的映射
出局：=空映射
adj_list：=一个空的映射
定义一个功能dfs()。这将带机场
而outs[airport]不为null时，执行
nxt：=adj_list[airport]的大小-outs[airport]
outs[机场]：=outs[机场]-1
在ans结尾处插入机场
定义一个名为的方法solve()，这将进行
对于航班中的每个出发端对s，e
在adj_list[s]的末尾插入e
outs[s]：=outs[s]+1
ins[e]：=ins[e]+1
对于adj_list所有值列表中的每个l，执行
排序列表l
开始：=null，结束：=null
对于adj_list所有键列表中的每个机场，执行
返回
如果end不为null，则
结束：=机场
返回
如果开始不为空，则
开始：=机场
返回
如果outs[airport]-ins[airport]与1相同，则
否则，当outs[airport]-ins[airport]与-1相同时，则
否则，当outs[airport]-ins[airport]不等于0时，则
start：=如果start不为null，则开始，否则adj_list的所有键的最小值
ans：=一个新列表
dfs（开始）
返回ans的反向
从主要方法中调用solve（航班）
示例
from collections import defaultdict
class Solution:
def solve(self, flights):
ins = defaultdict(int)
outs = defaultdict(int)
adj_list = defaultdict(list)
for s, e in flights:
adj_list[s].append(e)
outs[s] += 1
ins[e] += 1
for l in adj_list.values():
l.sort()
start = None
end = None
for airport in adj_list.keys():
if outs[airport] - ins[airport] == 1:
if start:
return
start = airport
elif outs[airport] - ins[airport] == -1:
if end:
return
end = airport
elif outs[airport] - ins[airport] != 0:
return
start = start if start else min(adj_list.keys())
ans = []
def dfs(airport):
while outs[airport]:
nxt = len(adj_list[airport]) - outs[airport]
outs[airport] -= 1
dfs(adj_list[airport][nxt])
ans.append(airport)
dfs(start)
return ans[::-1]
ob = Solution()flights = [
["Mumbai", "Kolkata"],
["Delhi", "Mumbai"],
["Kolkata", "Delhi"]
]
print(ob.solve(flights))输入值
[["Mumbai", "Kolkata"], ["Delhi", "Mumbai"], ["Kolkata", "Delhi"] ]
输出结果
['Delhi', 'Mumbai', 'Kolkata', 'Delhi']