【LeetCode】332. 重新安排行程-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode】332. 重新安排行程。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

332. 重新安排行程（困难）

【LeetCode】332. 重新安排行程,LeetCode刷题,leetcode,哈希算法,算法

思路

由于题目保证了存在一条合法的旅行路线，并要求按照字典序返回完整的路线。该方法通过深度优先搜索和栈的结合，可以保证每次选择字典序最小的终点进行访问，从而得到按照字典序排列的完整旅行路线。
具体来说，首先创建一个无序映射hash，用于存储每个出发地对应的目的地集合。遍历给定的机票列表，将每个出发地和目的地添加到hash中。
接着通过使用栈来模拟递归的过程，可以保证每次都选择字典序最小的终点进行访问。在每次循环中，如果当前终点的终点集合为空，说明已经到达终点，将当前终点插入到结果数组中，并将其从栈中弹出。如果当前终点的终点集合不为空，说明还有未访问的终点，选择其中一个终点压入栈中，并从终点集合中删除。通过这样的方式，可以按照字典序排列完整的旅行路线。
最后，将答案ans进行反转，得到正确的行程路线。文章来源地址https://www.toymoban.com/news/detail-530765.html

代码

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, multiset<string>> hash;
        vector<string> ans;

        for(auto ticket : tickets){
            hash[ticket[0]].insert(ticket[1]);
        }
        stack<string> s;
        s.push("JFK");
        while(!s.empty()){
            string next = s.top();
            if(hash[next].empty()){
                ans.push_back(next);
                s.pop();
            }
            else{
                s.push(*hash[next].begin());
                hash[next].erase(hash[next].begin());
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};