資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：按正確順序查詢機場？
假設我們有一份航班列表，以[起點，終點]對的形式給出。列表是亂序的；我們必須找到所有按正確順序訪問的機場。如果有多個有效的行程，則先返回字典序最小的行程。
因此，如果輸入類似於flights = [["Mumbai", "Kolkata"],["Delhi", "Mumbai"],["Kolkata", "Delhi"] ]，則輸出將為['Delhi', 'Mumbai', 'Kolkata', 'Delhi']
為了解決這個問題，我們將遵循以下步驟
ins := 一個空對映
outs := 一個空對映
adj_list := 一個空對映
定義一個函式dfs()。這將接受機場作為引數
當outs[airport]不為空時，執行以下操作：
nxt := adj_list[airport]的大小 - outs[airport]
outs[airport] := outs[airport] - 1
將機場插入ans的末尾
定義一個名為solve()的方法，這將接受航班作為引數
對於flights中的每個起點-終點對s, e，執行以下操作：
將e插入adj_list[s]的末尾
outs[s] := outs[s] + 1
ins[e] := ins[e] + 1
對於adj_list所有值的列表中的每個l，執行以下操作：
對列表l進行排序
start := null, end := null
對於adj_list所有鍵的列表中的每個機場，執行以下操作：
如果outs[airport] - ins[airport]等於1，則
如果start不為空，則
返回
start := airport
否則，如果outs[airport] - ins[airport]等於-1，則
如果end不為空，則
返回
end := airport
否則，如果outs[airport] - ins[airport]不等於0，則
返回
start := 如果start不為空則為start，否則為adj_list所有鍵的最小值
ans := 一個新的列表
dfs(start)
返回ans的反轉
從主方法呼叫solve(flights)
示例
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']
310 次瀏覽
