力扣—332重新安排行程
题目描述
给定一个机票的字符串二维数组 [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"]。但是它自然排序更大更靠后。
解题思路
图的深度搜索回溯,首先对行程来建立字典,对于行程中的每一条记录,第一个元素为start,第二个元素为end,以示例2为例子,建立字典后{“JFK”: ["SFO", "ATL], "SFO":["ATL"], "ATL":["JFK", "SFO"]},这里由于考虑先后问题,可以对字典中每个元素所对应的列表进行排序,排序后为{“JFK”: ["ATL", "SFO"], "SFO":["ATL"], "ATL":["JFK", "SFO"]},这里仅”JFK“对应的元素对换了。然后进行dfs遍历,从”JFK“开始,如果对应的列表不为空,那么从中弹出第一个元素,然后对该元素进行dfs,当对应列表为空时就回溯,这里首先是”ATL“,弹出ATL,对ATL进行dfs,ATL列表中有两个元素,所以先遍历”JFK“,此时JFK列表中只剩”SFO“,依次进行计算,每次把节点逆序插入到结果集中
详情可以看看https://leetcode-cn.com/problems/reconstruct-itinerary/solution/javadfsjie-fa-by-pwrliang/
题目中给定的机场名称是图的顶点,行程是图的边。题目要求重新安排行程,从示例可以看出每个行程都必须用到且只用一次。对应到欧拉路径的定义,每条边都要走到,且不重复。那么,这道题就转化成了给定起点,求一条字典顺序最小的欧拉路径。为了引出解法,我们先放几个例子。
图 1 展示了一张顶点度数都为偶数的图,首先我们忽略掉按字典顺序输出的条件。我们可以看出,如果顶点度数为偶数,那么我们先从 JFK 到 MUC 再回 JFK 到 ATL 最后返回 JFK,又或是 JFK 先到 ATL 再回 JFK 再去 MUC 再回 JFK,都是合法的路径。如果按照字典顺序输出,我们 优先访问字典顺序小的节点ATL即可。因此,我们 使用贪心策略,优先访问字典顺序小的顶点。
图 2 这个例子可以看出,我们别无选择必须先从 JFK 到 NRT 再回 JFK,最后到达 KUL 作为终点。如果我们按照字典顺序先到 KUL,就进入了 “死路”。但是上一个例子我们提到了,优先访问字典顺序小的顶点,那么我们第一次肯定是先到 KUL,这就走不通了,那怎么解决呢?当我们采用 DFS 方式遍历图时,需要将访问到的节点逆序插入到结果集。因此第一个访问到的节点将出现在结果集最后面,而我们是以顺序的方式来查看结果。如果第一个访问的节点是 “孤岛节点”,他会出现在结果集的最后。当我们顺序读取结果集时,这种 “孤岛节点” 是最后遇到的,是图遍历的终点,这样就没有问题了。
我们在图 3 绘制了算法执行过程,黑色实线表示图的边;红色实实线表示递归调用;绿色虚线表示递归调用返回;数字代表执行顺序;文字表示执行的操作,结果集的数字表示在第几步操作加入的。我们从 JFK 出发,沿着边到达 KUL(因为 KUL 字典顺序比 NRT 小),然后 KUL 没有临接点,将它放入结果集(2),然后从 KUL 返回到达 JFK,注意这个是通过调用栈返回而不是沿着边返回。然后从 JFK 出发沿着边到达NRT,因为 NRT 到 JFK 有返回边,沿着边再回到 JFK。此时 JFK 的两个临接点都访问过了,我们将 JFK 加入结果集(6)。然后我们从 JFK 返回到 NRT,这是从调用栈返回。然后 NRT 的临接点都访问过了,我们将 NRT 加入结果集(8),然后退栈回到 JFK。JFK 的所有临接点都访问过了,将 JFK 加入结果集(10),然后退栈,整个流程结束
import collections
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
dic = collections.defaultdict(list)
for start, end in tickets:
dic[start] += [end]
for item in dic:
dic[item].sort()
ans = []
def dfs(f):
while dic[f]:
dfs(dic[f].pop(0))
ans.insert(0, f)
dfs("JFK")
return ans
S = Solution()
print(S.findItinerary([["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]))
上一篇: 28岁中二程序员的C