跳转至

332. 重新安排行程

力扣链接(困难)：https://leetcode.cn/problems/reconstruct-itinerary

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

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

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

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

示例 1：

img

Text Only
1
2
输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

img

Text Only
1
2
3
输入：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

个人题解

该题解在 2025-07-23 已经实测会 TLE，评论区大部分题解也都过不了。所以这个题解只是做一个参考吧。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    // 用于记录当前机场有那些航班，map<string, int> 代表目的机场和航班数量
    unordered_map<string, map<string, int>> targets;
    vector<string> path;
    bool backtracking(int ticketNum) {
        // 如果要按照题目要求 「机票至少存在一种合理的行程且所有的机票必须都用一次且只能用一次」
        // 假如我有 4 张票
        // tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
        // path = ["JFK","MUC","LHR","SFO","SJC"]
        // 很明显我的 path 中会有 票数+1 个机场
        if(path.size() == ticketNum + 1) return true;

        // target[path.back()] 代表当前所处机场有哪些航班
        for(pair<const string, int>& target : targets[path.back()]) {
            if(target.second == 0) continue;
            path.push_back(target.first);
            target.second--;
            // 如果已经找到一条使用了所有机票的路径，那就收摊
            if(backtracking(ticketNum)) return true;
            target.second++;
            path.pop_back();
        }

        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(auto ticket : tickets) {
            // 将 ticket[0] 飞往 ticket[1]
            // 映射到 unordered_map<当前机场, map<坠机机场, 当前机场前往坠机机场到航班数量>> targets;
            targets[ticket[0]][ticket[1]]++;
        }
        // 把人先放到肯尼迪国际机场，准备起飞 🛫
        path.push_back("JFK");
        backtracking(tickets.size());
        return path;
    }
};