JAVA程序设计：重新安排行程（LeetCode：332）

程序设计：重新安排行程（LeetCode：332）"/>

JAVA程序设计：重新安排行程（LeetCode：332）

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。

说明:

如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
所有的机场都用三个大写字母表示（机场代码）。
假定所有机票至少存在一种合理的行程。
示例 1:

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2:

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

思路：从示例中我们可以看出，本题要求我们求出一条欧拉路径，和普通欧拉路径不同的是本路径每次所走的边一定是当前能走的字典序最小的边，因此我们需要弄清楚的是如何遍历这一有向图，因为肯定不是每次单纯走字典序最小的边这么简单，我们考虑下面这一种情况：

你会发现你的dfs一定会先去遍历KUL，但是这一节点明显是死路，导致你到最后无法形成正确的欧拉路径，但是如何我们不每次无脑走最小字典序的边的话这道题没法用O(N)以内的方法遍历了呀，我们换个角度想，既然走到了死路，呢么这条边一定是最后要经历的边，也就是这条边所指向的节点一定是我们答案最后添加的节点，so，问题迎刃而解了呀，我们只用将当前遍历到的点逆序加入结果集就好了呀。

class Solution {public List<String> findItinerary(List<List<String>> tickets) {List<String> ans=new ArrayList<>();if(tickets==null || tickets.size()==0)return ans;Map<String,List<String>> graph=new HashMap<>();for(List<String> pair:tickets){List<String>nbr=graphputeIfAbsent(pair.get(0), k->new LinkedList<>());nbr.add(pair.get(1));}graph.values().forEach(x->x.sort(String::compareTo));dfs(graph,"JFK",ans);return ans;}private void dfs(Map<String,List<String>> graph,String src,List<String> ans){List<String> nbr=graph.get(src);while(nbr!=null && nbr.size()>0){String dest=nbr.remove(0);dfs(graph,dest,ans);}//逆序插入结果集ans.add(0,src);}
}