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']

更新于：2020年11月10日

310 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告