目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

说明:

如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
所有的机场都用三个大写字母表示（机场代码）。
假定所有机票至少存在一种合理的行程。

示例 1:

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]

示例 2:

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

二、解题思路

1.sorted()函数可以为字母组合排序

2.邻接表：key值为出发地，value值包含一个或多个目的地，例如[A,B]和[A,C]为[A:[B,C]]

3.栈stack存放路径，can_fly为False则表示既不在key中也不在对应的value中，则pop并加入到所属key对应value的末尾（append）

三、代码

      class Solution:
      def findItinerary(self, tickets):
       edges = {}
       edges["count"] = len(tickets)
      for ticket in tickets:
      if ticket[0] not in edges:
       edges[ticket[0]] = []
       edges[ticket[0]].append(ticket[1])
       stack = ["JFK"]
      def iter_dfs(stack, edges):
      if edges["count"] == 0:
      return True
      if stack[-1] not in edges or not edges[stack[-1]]:
      return False
       sorted_edges_stack_last = sorted(edges[stack[-1]])
      for cur in sorted_edges_stack_last:
       stack.append(cur)
       edges[stack[-2]].remove(cur)
       edges["count"] -= 1
       can_fly = iter_dfs(stack, edges)
      if can_fly:
      return True
       stack.pop()
       edges[stack[-1]].append(cur)  # add to last
       edges["count"] += 1
      return False
       iter_dfs(stack, edges)
      return stack
      if __name__ == '__main__':
       tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
       s = Solution()
       ans = s.findItinerary(tickets)
       print(ans)
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108266928