LeetCode 332. 重新安排行程

2023-02-01 HGNULB 约 7 分钟

文章信息 7 个分类 · 9 个标签

分类

LeetCode CodeTop 困难 未解决 2-5 字节跳动 美团

标签

数组 字符串 深度优先搜索 排序 堆（优先队列） 图 半欧拉图 欧拉回路 欧拉路径

目录 收起 展开

题目描述

✅ 332. 重新安排行程

题意分析

给一批单程机票，每张写明出发和到达机场。要求从 "JFK" 出发，把每张机票恰好用一次，排出完整的行程；如果有多种排法，返回字典序最小的那一个（把行程当作字符串数组整体比较）。

「每张恰好一次」是关键措辞：不是每个机场访问一次，而是每条边用一次。同一对机场之间可能有多张相同的机票，它们是不同的边，必须分别使用。

题目保证至少存在一个合法行程，所以不需要处理无解的情形。这个保证会大大简化实现——不必回溯，也不必检验连通性和度数条件。

输出的长度是确定的：机票数加一。起点固定为 "JFK"，终点则由图的结构决定，不由我们选择。

机票数量上限只有三百，规模很小，但这并不意味着可以枚举全排列——三百的阶乘是天文数字，暴力搜索必须被剪掉。

解法：排序邻接表 + Hierholzer 算法

核心思路

先把问题翻译成图论语言：机场是点，每张机票是一条有向边，要求找一条从 "JFK" 出发、恰好经过每条边一次的路径。这正是有向图欧拉路径的定义。

朴素做法是回溯：从 "JFK" 开始，每步在未使用的出边中按字典序挑最小的走，走不通就撤销换下一条。因为字典序最小的可行解一定优先被找到，正确性没问题；但一旦图中存在很多死路，回溯的分支会急剧膨胀。

关键观察在于：题目保证存在一条从 "JFK" 出发的欧拉路径。沿未使用的边走到当前点再也没有出边时，这个点就应放在当前行程后缀的末端：开放的欧拉路径第一次会停在度数意义上的终点；欧拉回路则会回到这段路的起点。图中尚未接入的边，会在递归回退时以支路或回路的形式拼到这个已确定的后缀之前，因此不需要撤销已经走过的边。

这就是 Hierholzer 算法的立足点：贪心地一直往前走，卡住了就把当前点记入一个后序列表，然后回退一格继续消耗剩余的边；被回退时记录下的点，其后续路径已经完整地压在后序列表里。整个过程结束后，把后序列表反转就是一条欧拉路径。每条边只被消耗一次，没有任何回溯撤销。

字典序的处理很自然：把每个机场的目的地列表排好序，每次总取当前最小的那个未用目的地。可以证明，在保证有解的前提下这样贪心不会失败——走进死胡同不是错误，那恰恰意味着找到了终点，算法会自动把它安置在路径末尾。

实现上有个小技巧：把目的地列表按字典序降序排列，这样每次从尾部弹出的就是字典序最小的，删除操作是 $O(1)$ 的；若按升序存再从头部删除，每次都要搬移整个数组。

解题步骤

• 遍历所有机票建邻接表，键是出发机场、值是目的地列表。重复的机票要保留为重复元素，因为它们是各自独立的边，合并会丢票。
• 把每个目的地列表按字典序降序排序。降序是为了配合从尾部弹出，弹出的正好是当前字典序最小的目的地。
• 从 "JFK" 进入递归。递归体是一个循环：只要当前机场还有未用出边，就弹出最小的那个并递归过去。弹出即代表这张票被消耗，不再放回——这是与回溯法最本质的区别。
• 循环退出说明当前机场的出边全部用完，此时把它追加到后序列表。它被记录的时刻，意味着从它出发的所有边都已铺设完毕，因此它在最终路径中的位置必然在这些边之后。
• 递归全部返回后反转后序列表。后序记录的顺序是「从终点往起点」，反转即得正序行程。
• 注意每次递归返回后要重新读取当前机场的目的地列表。在切片语义的语言里，递归过程中列表可能已被改写，用递归前的旧引用会漏掉或重复消耗边。

以 tickets = [["JFK","SFO"], ["JFK","ATL"], ["SFO","ATL"], ["ATL","JFK"], ["ATL","SFO"]] 走一遍：建表后 JFK 的目的地是 ["SFO", "ATL"]、SFO 是 ["ATL"]、ATL 是 ["JFK", "SFO"]。降序排序后 JFK 为 ["SFO", "ATL"]（尾部是最小的 ATL），ATL 为 ["SFO", "JFK"]（尾部是最小的 JFK），SFO 为 ["ATL"]。

进入 JFK，弹出尾部的 ATL，此时 JFK 剩 ["SFO"]，递归到 ATL。

在 ATL，弹出尾部的 JFK，ATL 剩 ["SFO"]，递归回 JFK。

第二次到 JFK，它还剩 ["SFO"]，弹出 SFO，JFK 变空，递归到 SFO。

在 SFO，弹出 ATL，SFO 变空，递归到 ATL。

第二次到 ATL，它还剩 ["SFO"]，弹出 SFO，ATL 变空，递归到 SFO。

第二次到 SFO，它已经没有出边，卡住。后序列表记下 SFO，列表为 [SFO]。这个位置就是整条行程的终点。

逐层返回：上一层的 ATL 出边已空，记下 ATL，列表为 [SFO, ATL]；再上一层的 SFO 出边已空，记下，列表为 [SFO, ATL, SFO]；再上一层的 JFK 出边已空，记下，列表为 [SFO, ATL, SFO, JFK]；再上一层的 ATL 出边已空，记下，列表为 [SFO, ATL, SFO, JFK, ATL]；最外层的 JFK 此时出边也已被内层消耗干净，记下，列表为 [SFO, ATL, SFO, JFK, ATL, JFK]。

反转得到 ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]，长度为机票数 5 加 1，与预期一致。对照另一个候选行程 ["JFK", "SFO", "ATL", "JFK", "ATL", "SFO"]，第二个元素 ATL 小于 SFO，所以我们的结果确实是字典序更小的那个。

代码实现

class Solution {
    // 字典序要求影响的是同一出发点的边选择顺序，因此每个邻接表都要按目的地排序。
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, List<String>> graph = new HashMap<>();
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            graph.computeIfAbsent(from, key -> new ArrayList<>()).add(to);
        }
        for (List<String> dests : graph.values()) {
            dests.sort(Collections.reverseOrder());
        }

        List<String> path = new ArrayList<>();
        dfs("JFK", graph, path);
        Collections.reverse(path);
        return path;
    }

    private void dfs(String airport, Map<String, List<String>> graph, List<String> path) {
        List<String> dests = graph.get(airport);
        while (dests != null && !dests.isEmpty()) {
            String next = dests.remove(dests.size() - 1);
            dfs(next, graph, path);
        }
        path.add(airport);
    }
}

func findItinerary(tickets [][]string) []string {
    // 字典序要求影响的是同一出发点的边选择顺序，因此每个邻接表都要按目的地排序。
    graph := make(map[string][]string)
    for _, ticket := range tickets {
        from, to := ticket[0], ticket[1]
        graph[from] = append(graph[from], to)
    }
    for from := range graph {
        sort.Sort(sort.Reverse(sort.StringSlice(graph[from])))
    }

    path := make([]string, 0, len(tickets)+1)
    var dfs func(airport string)
    dfs = func(airport string) {
        dests := graph[airport]
        for len(dests) > 0 {
            next := dests[len(dests)-1]
            graph[airport] = dests[:len(dests)-1]
            dfs(next)
            dests = graph[airport]
        }
        path = append(path, airport)
    }

    dfs("JFK")

    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }

    return path
}

复杂度分析

• 时间复杂度：$O(E \log E)$，其中 $E$ 为机票数。构建图为 $O(E)$；各邻接表分别排序的总代价不超过 $O(E \log E)$；DFS 中每张机票恰好被弹出一次，为 $O(E)$。
• 空间复杂度：$O(E)$。邻接表保存全部机票，结果包含 $E + 1$ 个机场；递归栈最坏也会沿一条包含全部边的行程增长到 $O(E)$。

关键点总结

• 字典序要求影响的是同一出发点的边选择顺序，因此每个邻接表都要按目的地排序。
• Hierholzer 算法会在一条路走到无法继续后回退接上其它边，适合处理局部死路而不需要暴力回溯所有排列。
• 节点必须在“所有出边耗尽后”加入答案；得到的是逆序欧拉路径，最后统一反转。
• 面试时要把机票解释为可重复的有向边：机场是点，使用全部机票一次就是求从 JFK 出发的欧拉路径。

易错点总结

• 按字典序贪心后立刻把机场写入答案：JFK -> KUL、JFK -> NRT、NRT -> JFK 中若先选较小的 KUL 会提前走入死路；应在回溯时后序记录，最终得到 JFK,NRT,JFK,KUL。
• 把重复机票去重：两张完全相同的机票仍是两条独立边，放进 Set 会少用一张票，结果长度也不再是 E + 1。
• 邻接表升序排序却从尾部弹出：这样每次取得的是字典序最大的目的地；要么降序后弹尾部，要么使用小根堆。
• 前序加入结果或忘记最终反转：Hierholzer 记录的是“死路回退顺序”，天然从终点到起点，直接返回会整条颠倒。

相似题目

题目	难度	与本题的联系
2097. 合法重新排列数对	困难	同样求有向图欧拉路径，但不再附带字典序要求
753. 破解保险箱	困难	把字符串状态建成 De Bruijn 图后求欧拉回路