LeetCode 332. 重新安排行程
原题链接
中等
作者:
我太快乐了
,
2021-05-06 22:16:33
,
所有人可见
,
阅读 315
算法1
回溯
时间复杂度
参考文献
Python3 代码
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
# 回溯算法
path = ["JFK"]
choice = collections.defaultdict(list)
# 数据结构重建
for elem in tickets:
choice[elem[0]].append(elem[1])
def backtrace(begin):
## 回溯终止
if len(path) == len(tickets)+1:
return True
choice[begin].sort()
# 1. 做选择
for _ in choice[begin]:
end = choice[begin].pop(0)
path.append(end)
# 2. 回溯
if backtrace(end):
return True
# 3. 回退选择
tmp = path.pop()
choice[begin].append(tmp)
return False
backtrace("JFK")
return path
算法2
DFS解欧拉通路
Pthon3 代码
def DFS(curr):
while vec[curr]:
tmp = heapq.heappop(vec[curr])
DFS(tmp)
stack.append(curr)
vec = collections.defaultdict(list)
stack = []
for depart,arrive in tickets:
vec[depart].append(arrive)
for key in vec:
heapq.heapify(vec[key])
DFS("JFK")
return stack[::-1]