HTML CSS JAVASCRIPT JQUERY AI PHP SQL EXCEL LINUX C# C++ C PYTHON JAVA 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ

用 Python 编写程序以正确的顺序查找机场?

pythonserver side programmingprogramming更新于 2026/2/16 22:04:17

假设我们有一个航班列表，以 [出发地，目的地] 对的形式列出。该列表是随机排列的；我们必须以正确的顺序找到所有访问过的机场。如果有多个有效行程，则首先返回按字典顺序最小的行程。

因此，如果输入为 flights = [["Mumbai", "Kolkata"],["Delhi", "Mumbai"],["Kolkata", "Delhi"] ]，则输出为 ['Delhi', 'Mumbai', 'Kolkata', 'Delhi']

为了解决这个问题，我们将遵循以下步骤

  • ins := 一个空的 map

  • outs := 一个空的 map

  • adj_list := 一个空的map

  • 定义一个函数 dfs() 。这将需要 airport

  • 当 outs[airport] 不为空时，执行

    • nxt := adj_list[airport] 的大小 - outs[airport]

    • outs[airport] := outs[airport] - 1

    • 在 ans 末尾插入 airport

  • 定义一个名为 solved() 的方法，这将需要 flights

  • 对于 flights 中的每个起始结束对 s、e，执行

    • 在 adj_list[s] 末尾插入 e

    • outs[s] := outs[s] + 1

    • ins[e] := ins[e] + 1

  • 对于 adj_list 所有值列表中的每个 l，执行

    • 对列表 l 进行排序

  • start := null, end := null

  • 对于 adj_list 所有键列表中的每个 airport，执行

    • 如果 outs[airport] - ins[airport] 与 1 相同，则

      • 如果 start 不为 null，则

        • 返回

      • start := airport

    • 否则outs[airport] - ins[airport] 与 -1 相同，则

      • 如果 end 不为空，则

        • 返回

      • end := airport

    • 否则，当 outs[airport] - ins[airport] 不等于 0 时，则

      • 返回

  • 如果 start 不为空，则 start := start，否则 adj_list 中所有键的最小值

  • ans := a new list

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

相关文章

有用资源

打印 下一节:如何在 Pandas 中查找和过滤重复行? ❯❮ 上一节:如何在 Python Pandas 中使用字典顺序切片选择数据子集?