332 Reconstruct Itinerary
题目内容
ref: leecode Ref
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
Note:
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"]. All airports are represented by three capital letters (IATA code). You may assume all tickets form at least one valid itinerary.
Example 1: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
Example 2: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Return ["JFK","ATL","JFK","SFO","ATL","SFO"]. Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
分析
首先感觉就是普通的backtracking(dfs)，但是写的时候疯狂在corner case报错
问题出在，
比如jfk->sfo，还可以有jfk->atl,还可以有sfo->jfk，就是说可以有同一段旅程好几次倒腾，但是如果只是用普通的map的话，很难检测出重复的票。
如果用tickets[][]里面的index表示的话，每次对tickets从头到尾找一遍太慢了，会tle
这个里面的点：
- 我认为这道题的特别之处是，我知道这个不会有死路，就是这些机票确定是肯定是对的，只要沿着
<from, to>走，就一定是对的，但是只是可能不是Lexical order上的最优，所以我认为不存在wrong path要回退
- 用
map<String PriorityQueue<String>>来实现同一个站greedy的走法，只要找到头了，就是对的
还有一点自己的， 就是看到有人留言说Stack这个已经被Java官方标记成的deprecated的类了，官方现在对于queue和stack建议统一使用Deque。
stack中的push() => offerFirst(). pop() => pollFirst(), peek()=> peekFirst()
queue中的 add() => offerLast(), remove() => pollFirst(), peek() => peekFirst()
我省略了add/remove一组，直接用offer/poll，第一组也存在，此处不写
代码