力扣 332. 重新安排行程

这道题目有几个难点：

1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环。解决：用 map<string, int> 中的 int 对使用过的机票进行标记。
2. 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？解决：map 可以对key值进行排序。
3. 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？解决：行程站点等于ticket数目+1，因为有首发站。找到即返回true，不用遍历其它节点。
4. 搜索的过程中，如何遍历一个机场所对应的所有机场。解决：使用 unordered_map<string, map<string, int>> ，表示unordered_map<出发机场, map<到达机场, 航班次数>> 。

class Solution {
public:
    unordered_map<string, map<string, int>> targets;
    vector<string> res;
    bool backtracking(int ticketNum) {
        if(ticketNum + 1  == res.size()) return true;
        //for (pair<const string, int>& nexttarget : targets[res[res.size()-1]]) {
        for (auto nexttarget = targets[res[res.size()-1]].begin(); nexttarget != targets[res[res.size()-1]].end(); nexttarget++) {
            cout<<nexttarget->first<<" ";
            if(nexttarget->second > 0) {
                nexttarget->second--;
                res.push_back(nexttarget->first);
                if(backtracking(ticketNum)) return true;
                res.pop_back();
                nexttarget->second++;
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(auto ticket:tickets) {
            targets[ticket[0]][ticket[1]]++;
        }
        res.push_back("JFK");
        backtracking(tickets.size());
        return res;
    }
};

这里对tickets的遍历用到了迭代器，指向first要用‘->’；也可使用如下：target.first。注意加const和引用符号&，因为map中的key是不可修改的（虽然这个用法我不太理解，但它真的不加会变，导致循环）。

pair<const string, int>& target : targets[result[result.size() - 1]]

好难。。