[출발지, 목적지] 쌍으로 항공편 목록이 있다고 가정합니다. 목록이 섞입니다. 우리는 올바른 순서로 방문한 모든 공항을 찾아야 합니다. 둘 이상의 유효한 일정이 있는 경우 사전순으로 가장 작은 일정을 먼저 반환합니다.
따라서 입력이 flight =[["Mumbai", "Kolkata"],["Delhi", "Mumbai"],["Kolkata", "Delhi"] ]인 경우 출력은 ['Delhi' , '뭄바이', '콜카타', '델리']
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
ins :=빈 지도
-
outs :=빈 지도
-
adj_list :=빈 지도
-
dfs() 함수를 정의합니다. 공항으로 이동합니다.
-
outs[airport]가 null이 아닌 동안 수행
-
nxt :=adj_list[공항] 크기 - outs[공항]
-
아웃[공항] :=아웃[공항] - 1
-
ans의 끝에 공항을 삽입하십시오.
-
-
solve()라는 메서드를 정의하면 비행 시간이 걸립니다.
-
비행의 각 시작 끝 쌍 s, e에 대해 수행
-
adj_list[s]
끝에 e 삽입 -
아웃[s] :=아웃[s] + 1
-
ins[e] :=ins[e] + 1
-
-
adj_list의 모든 값 목록에서 각 l에 대해 수행
-
목록 정렬 l
-
-
시작 :=null, 종료 :=null
-
adj_list의 모든 키 목록에 있는 각 공항에 대해 수행
-
outs[airport] - ins[airport]가 1과 같으면
-
시작이 null이 아닌 경우
-
반환
-
-
시작 :=공항
-
-
그렇지 않으면 outs[airport] - ins[airport]가 -1과 같을 때
-
end가 null이 아니면
-
반환
-
-
끝 :=공항
-
-
그렇지 않으면 outs[airport] - ins[airport]가 0과 같지 않으면
-
반환
-
-
-
start :=start가 null이 아닌 경우 시작, 그렇지 않으면 adj_list의 모든 키 중 최소값
-
ans :=새 목록
-
dfs(시작)
-
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']