Hard

题目描述

给你一份航线列表 tickets，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字符串自然排序返回最小的行程组合。

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

示例 1：

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]，但是它字典排序更大更靠后。

提示：

  • 1 <= tickets.length <= 300
  • tickets[i].length == 2
  • fromi.length == 3
  • toi.length == 3
  • fromi 和 toi 由大写英文字母组成
  • fromi != toi

解题思路

这是一个寻找欧拉路径的问题。我们需要找到一条使用所有边恰好一次的路径。

核心思路：

  1. 将机票看作有向图的边，机场看作节点
  2. 从JFK开始寻找欧拉路径，即遍历所有边且每条边只用一次
  3. 由于要求字典序最小，需要优先选择字典序小的目的地

算法步骤：

  1. 构建图：使用邻接表存储，每个机场对应一个目的地列表
  2. 排序：对每个机场的目的地按字典序排序，确保优先访问字典序小的机场
  3. DFS遍历：使用深度优先搜索，每次选择字典序最小的可达机场
  4. 后序遍历：当无法继续前进时，将当前机场加入结果（需要反转最终结果）

关键点：

  • 使用Hierholzer算法找欧拉路径
  • 通过后序遍历确保路径正确性
  • 优先队列或排序保证字典序最小

这种方法时间复杂度为O(ElogE)，其中E是边数，主要消耗在排序上。

代码实现

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph;
        
        // 构建图，使用最小堆确保字典序
        for (auto& ticket : tickets) {
            graph[ticket[0]].push(ticket[1]);
        }
        
        vector<string> result;
        
        function<void(string)> dfs = [&](string airport) {
            while (!graph[airport].empty()) {
                string next = graph[airport].top();
                graph[airport].pop();
                dfs(next);
            }
            result.push_back(airport);
        };
        
        dfs("JFK");
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        from collections import defaultdict
        import heapq
        
        # 构建图
        graph = defaultdict(list)
        for src, dst in tickets:
            graph[src].append(dst)
        
        # 对每个机场的目的地进行排序（字典序）
        for src in graph:
            graph[src].sort()
        
        result = []
        
        def dfs(airport):
            while graph[airport]:
                next_airport = graph[airport].pop(0)  # 取字典序最小的
                dfs(next_airport)
            result.append(airport)
        
        dfs("JFK")
        return result[::-1]  # 反转结果

public class Solution {
    public IList<string> FindItinerary(IList<IList<string>> tickets) {
        var graph = new Dictionary<string, List<string>>();
        
        // 构建图
        foreach (var ticket in tickets) {
            if (!graph.ContainsKey(ticket[0])) {
                graph[ticket[0]] = new List<string>();
            }
            graph[ticket[0]].Add(ticket[1]);
        }
        
        // 对目的地排序
        foreach (var src in graph.Keys) {
            graph[src].Sort();
        }
        
        var result = new List<string>();
        
        void DFS(string airport) {
            while (graph.ContainsKey(airport) && graph[airport].Count > 0) {
                var next = graph[airport][0];
                graph[airport].RemoveAt(0);
                DFS(next);
            }
            result.Add(airport);
        }
        
        DFS("JFK");
        result.Reverse();
        return result;
    }
}

var findItinerary = function(tickets) {
    const graph = new Map();
    
    // 构建图
    for (const [src, dst] of tickets) {
        if (!graph.has(src)) {
            graph.set(src, []);
        }
        graph.get(src).push(dst);
    }
    
    // 对目的地排序
    for (const [src, destinations] of graph) {
        destinations.sort();
    }
    
    const result = [];
    
    function dfs(airport) {
        while (graph.has(airport) && graph.get(airport).length > 0) {
            const next = graph.get(airport).shift();
            dfs(next);
        }
        result.push(airport);
    }
    
    dfs("JFK");
    return result.reverse();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(E log E)E为边数，主要消耗在对目的地排序
空间复杂度O(E)存储图的邻接表和递归栈空间

相关题目