332-重新安排行程

LeetCode 332. Reconstruct Itinerary

LeetCode-332

You are given a list of airline tickets where tickets[i] = [from, to] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

• For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Example 1:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

Example 2:

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

method: 回溯

难点一：回溯三部曲

• 递归函数参数
  机票总数，作为结束条件判断，也可以作为全局变量
• 递归结束条件
  最终行程数组比机票数大1，说明找到了一组可行的解，返回true，因为只需要一组解
• 单层循环逻辑
  因为每个起始点可能有多个终点，所以要遍历这些终点

难点二：选择合适的数据结构

首先一个起点对应多个终点，可以想到用unordered_map
其次，机票是可以重复的，所以还需要记录每个起止点出现的次数，也需要一个映射关系，而且用了一次之后次数要减少，也就是还要可以删改

所以选择用unordered_map<string, map<string, int>>，后面用map是因为需要对终点进行排序，字典序小的放在前面

例如有三张票是[A->B],[A->C],[A->C]，那么targets["A"]就对应了这三张票，可以对他们进行遍历

for (auto& target : targets["A"]) {
    cout << target.first << "->" << target.second << endl;
}
B->1    // A到B有一张票   已经排好序了
C->2    // A到C有两张票

因为要对票数直接修改，所以遍历的时候要用引用

unordered_map<string, map<string, int>> targets;
vector<string> res;
bool dfs(int ticketNum) {
    if (res.size() == ticketNum + 1) {
        return true;    // 站点数等于票数+1
    }
    // 要用前面的终点作为当前的起点，来找票
    for (auto& target : targets[res.back()]) {  // 这里要用引用
        if (target.second > 0) {    // 如果有票就用，已经排好序了
            target.second--;
            res.push_back(target.first);
            if (dfs(ticketNum)) return true;
            target.second++;
            res.pop_back();
        }
    }
    return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
    for (auto t : tickets) {
        targets[t[0]][t[1]]++;
    }
    res.push_back("JFK");   // 把起点放进来
    dfs(tickets.size());
    return res;
}