LeetCode 332. 重新安排行程

约 5 分钟
文章信息 7 个分类 7 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 美团
标签
数组 字符串 深度优先搜索 排序 堆（优先队列） 图 欧拉回路

题目描述

✅ 332. 重新安排行程

image-20260928223819746

image-20260928223819747

题意分析

从 JFK 出发，把每张机票恰好使用一次，返回经过的机场序列；若有多种完整行程，选择字典序最小的一条。题目保证至少存在一种合法行程。

机场可以重复经过，两张起终点相同的机票也必须分别使用。把机场看作顶点、机票看作有向边，要求的就是从指定起点出发、经过每条边一次的欧拉路径，而不是每个顶点只访问一次的路径。

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

核心思路

[!blue]

为每个机场建立可用目的地列表，按字典序降序排序。之后从列表尾部取出目的地，就能以常数时间取走当前最小的出边；删除的是一张具体机票，重复票仍保留各自的一项。

不能把贪心走到的机场立即固定为正向答案，因为较小的目的地可能提前走到终点，留下其他票未用。Hierholzer 算法改为先消耗边、递归走下去，只有当前机场已经没有剩余出边时，才把它追加到结果中。

这样先确定的是行程尾部。递归退回到仍有出边的机场时，继续遍历尚未使用的边，把其他绕行接入已有路线；所有出边处理完后再记录当前机场。最后反转记录顺序，就把这些路段拼成连续的完整行程。每张边只删除一次，所有票用完后结果有 机票数 + 1 个机场。

字典序选择与后序拼接共同起作用：从同一机场出发、还能返回该机场的绕行，可以放在最终离开的路段之前，按较小目的地优先探索；若先走进了不能返回的终点路段，它会先写入逆序结果，最终被放到后面。这样较小的可行选择优先出现，又不会为了贪心提前结束行程。

这里的递归不是“失败后撤销机票”的回溯。消耗的边不会恢复，靠后序记录与最终反转调整路段的拼接顺序。

解题步骤

  1. 将每张票加入出发机场的邻接列表，保留重复边，再把每个列表按目的地降序排序。
  2. 从 JFK 调用 dfs。只要当前机场仍有出边，就从尾部删除一张票，并递归处理它的目的地。
  3. 递归返回后继续检查当前机场的剩余出边，直到全部消耗完。
  4. 此时把当前机场加入逆序结果。没有出边的终点会先被记录。
  5. 最后将整个结果反转，得到从 JFK 开始的正向行程。

代码实现

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);
    }
}

import "sort"

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+1))$，邻接排序主导，遍历每条票一次。
  • 空间复杂度：$O(E)$，邻接表、结果及递归栈。

关键点总结

[!green]

  • 边代表机票，顶点代表机场；机票不能重复使用，机场却可以反复经过。
  • 按字典序选择出边，按后序确定结果位置，两者配合才能兼顾最小字典序和用完所有票。
  • 先记录无出边的节点，相当于先确定尾部，再把剩余路段拼到它前面。

易错点总结

[!yellow]

  • 不能用集合保存机票，也不能给机场设置“访问一次就不再进入”的标记，否则会丢掉重复票或重复经过机场的合法路线。
  • 邻接表降序排序后才应从尾部取最小值；升序排序再取尾部会优先选择最大目的地。
  • 前序直接输出或忘记最终反转，都无法得到这里需要的路段拼接顺序。
  • Go 的 dests 是切片头的副本，递归可能再次进入同一机场并改变其剩余出边长度，所以返回后必须重新读取 graph[airport]；Java 列表引用则能直接观察同一对象的变化。

相似题目

题目 难度 关联与区别
2097. 合法重新排列数对 困难 同样要求每条有向边恰好使用一次，可用欧拉路径；本题还需满足指定起点和字典序要求。
753. 破解保险箱 困难 同样可以把覆盖全部对象转成遍历图中每条边一次，原题用欧拉回路构造最短覆盖串。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/53257675
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！