332 重新安排行程
给定一个人坐过的一些飞机的起止机场,已知这个人从 JFK 起飞,那么这个人是按什么顺序飞的;如果存在多种可能性,返回字母序最小的那种。
输入是一个二维字符串数组,表示多个起止机场对子;输出是一个一维字符串数组,表示飞行顺序。
输入:tickets = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]
输出:[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]
解释:另一种有效的行程是 [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”] ,但是它字典排序更大更靠后。
解析:
本题可以使用哈希表记录机票的起飞机场和落地机场,由于可能存在多个不同落地机场,所以需要使用集合来存储。又由于可能存在重复路线,所以要保存落地机场的重复值,且要求结果的返回顺序是按照最小字母序,刚好可以使用多重集合 multiset
,不仅可以存储重复值,而且多重集合的默认元素保存顺序是递增的,例如"SFO","ATL","JFK"
在多重集合中的保存顺序是 "ATL","JFK","SFO"
。上例子的哈希表保存结果为:
JFK
{ATL, SFO}
SFO
{ATL}
ATL
{JFK, SFO}
保存好起飞机场和落地机场的关系后,我们使用栈来恢复一条完整的从最终落地机场到达起始机场的路线。从起始机场开始,按照转移顺序将机场逐个压入栈。取当前栈顶作为下一个落地机场,如果栈顶为空则说明到达一个终点,将其加入结果。如果不为空,则将其作为起飞机场对应的第一个落地机场入栈并移除。完成上述过程就恢复出了一条从终点到起点的飞行路线。上例恢复的路线为JFK->ATL->JFK->SFO->ATL->SFO
class Solution {
public:vector<string> findItinerary(vector<vector<string>>& tickets) {// 构建哈希表多重集合,保存起飞机场对应的落地机场unordered_map<string, multiset<string>> hash;for(const auto ticket: tickets){hash[ticket[0]].insert(ticket[1]);}// 使用栈恢复从终点到达起点的逆向路线vector<string> ans;stack<string> st;st.push("JFK");while(!st.empty()){string end = st.top();// 当前机场对应的落地机场为空,说明他是一个终点if(hash[end].empty()){ans.push_back(end);st.pop();}else{st.push(*hash[end].begin());hash[end].erase(hash[end].begin());}}reverse(ans.begin(),ans.end());return ans;}
};
参考资料
LeetCode 101:和你一起轻松刷题(C++) 第 11 章 妙用数据结构
更多推荐
算法,模板,笔记,标准,LeetCode
发布评论