欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

力扣—332重新安排行程

程序员文章站 2022-04-24 12:38:48
...

题目描述

给定一个机票的字符串二维数组 [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/

题目中给定的机场名称是图的顶点,行程是图的边。题目要求重新安排行程,从示例可以看出每个行程都必须用到且只用一次。对应到欧拉路径的定义,每条边都要走到,且不重复。那么,这道题就转化成了给定起点,求一条字典顺序最小的欧拉路径。为了引出解法,我们先放几个例子。

                                                                               力扣—332重新安排行程

图 1 展示了一张顶点度数都为偶数的图,首先我们忽略掉按字典顺序输出的条件。我们可以看出,如果顶点度数为偶数,那么我们先从 JFK 到 MUC 再回 JFK 到 ATL 最后返回 JFK,又或是 JFK 先到 ATL 再回 JFK 再去 MUC 再回 JFK,都是合法的路径。如果按照字典顺序输出,我们 优先访问字典顺序小的节点ATL即可。因此,我们 使用贪心策略,优先访问字典顺序小的顶点。

                                                                        力扣—332重新安排行程

图 2 这个例子可以看出,我们别无选择必须先从 JFK 到 NRT 再回 JFK,最后到达 KUL 作为终点。如果我们按照字典顺序先到 KUL,就进入了 “死路”。但是上一个例子我们提到了,优先访问字典顺序小的顶点,那么我们第一次肯定是先到 KUL,这就走不通了,那怎么解决呢?当我们采用 DFS 方式遍历图时,需要将访问到的节点逆序插入到结果集。因此第一个访问到的节点将出现在结果集最后面,而我们是以顺序的方式来查看结果。如果第一个访问的节点是 “孤岛节点”,他会出现在结果集的最后。当我们顺序读取结果集时,这种 “孤岛节点” 是最后遇到的,是图遍历的终点,这样就没有问题了。

                                                    力扣—332重新安排行程

我们在图 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"]]))
相关标签: dfs