力扣 332. 重新安排行程

一、题目描述

给你一份航线列表 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"] ，但是它字典排序更大更靠后。

二、题解

通过回溯法求解，因为要求最优解，因此在回溯前需要进行排序，同时在得到第一个满足条件的解后直接返回，因为排序后的第一个解即为最优解。

class Solution {
public:
    vector<string> result = {"JFK"};
    unordered_map<string, int> src_index_map;

    vector<string> findItinerary(vector<vector<string>> &tickets) {
        /* 记录每张机票的使用情况 */
        vector<bool> records(tickets.size(), false);

        /* 按照字典序对机票进行排序 */
        sort(tickets.begin(), tickets.end(), my_cmp);

        /* 通过哈希表记录每张机票出发机场在数组中的位置，避免重复遍历 */
        for (int i = 0; i < tickets.size(); i++) {
            if (i > 0 && tickets.at(i).at(0) == tickets.at(i - 1).at(0)) { continue; }
            src_index_map.emplace(tickets.at(i).at(0), i);
        }

        backtracking(tickets, records, "JFK");

        return result;
    }

    void backtracking(vector<vector<string>> &tickets, vector<bool> &records, string src) {
        if (result.size() == tickets.size() + 1) { 
            return;
        }

        auto ans = src_index_map.find(src);
        if (ans != src_index_map.end()) { 
            for (int begin = ans->second; begin < tickets.size() && src == tickets.at(begin).at(0); begin++) {
                if (!records.at(begin)) { 
                    result.emplace_back(tickets.at(begin).at(1));
                    records.at(begin) = true;
                    
                    backtracking(tickets, records, tickets.at(begin).at(1));

                    /* 只需要字典序最小的情况，因此满足条件后直接返回 */
                    if (result.size() == tickets.size() + 1) { 
                        return; 
                    }

                    result.pop_back();
                    records.at(begin) = false;
                }
            }
        }
    }

    static bool my_cmp(vector<string> &a, vector<string> &b) {
        if (a.at(0) == b.at(0)) {
            return a.at(1) < b.at(1);
        } else {
            return a.at(0) < b.at(0);
        }
    }
};