P183. 行程安排

leetcode 332 lintcode 1288 DFS 回溯 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,给你一组由出发机场与到达机场 [from, to] 表示的机票,你要按顺序把途经的机场排列出来。每个机场都由 3 个大写字母表示,并且一开始从 JFK 机场出发。

注意,所有的机票都要用上,并且它们至少可以组成一个有效的行程。如果存在多个有效行程,则返回字典序最小的那个行程。

为了方便演示,我们假设用单个大写字母来表示机场,并且一开始由 A 机场出发。

比如说,给你的机票是:

[B, D]
[A, B]
[C, E]
[D, C]

这 4 张机票只能构成一个有效行程:

[A, B, D, C, E]

再比如说,给你的机票是:

[A, C]
[A, B]
[C, B]
[B, A]

这 4 张机票可以组成两个有效的行程:

[A, B, A, C, B]
[A, C, B, A, B]

在这两个有效行程中,出发机场都是 A,然后第一个行程来到机场 B,而第二个行程来到机场 C。B 在字典序上是小于 C 的,因此我们要返回第一个有效行程:

[A, B, A, C, B]

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。