摘要：题目解答都是用来解，一个用一个用来实现深度优先搜索，搜索到一个城市只是的时候即没有出度的时候，把这个记入中去，因为它肯定是最后到达的城市，然后依次向前类推的要求在存入的时候就用先存好先进去的说明是出发城市，那么最先出发的城市最后出来
题目：
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.
解答：
都是用DFS来解，一个用recursion, 一个用stack来实现：
Recursion version:
public void dfs(String departure, Map> graph, List result) {
//深度优先搜索，搜索到一个城市只是arrival city的时候（即没有出度的时候，把这个city记入list中去，因为它肯定是最后到达的城市，然后依次向前类推
PriorityQueue arrivals = graph.get(departure);
while (arrivals != null && !arrivals.isEmpty()) {
dfs(arrivals.poll(), graph, result);
}
result.add(0, departure);
}
public List findItinerary(String[][] tickets) {
List result = new ArrayList();
//lexical order的要求在存入graph的时候就用priority queue先存好
Map> graph = new HashMap<>();
for (String[] iter : tickets) {
graph.putIfAbsent(iter[0], new PriorityQueue());
graph.get(iter[0]).add(iter[1]);
}
dfs("JFK", graph, result);
return result;
}
Stack version:
public List findItinerary(String[][] tickets) {
List result = new ArrayList();
Map> graph = new HashMap();
for (String[] iter : tickets) {
graph.putIfAbsent(iter[0], new PriorityQueue());
graph.get(iter[0]).add(iter[1]);
}
Stack stack = new Stack();
stack.push("JFK");
while (!stack.isEmpty()) {
while (graph.containsKey(stack.peek()) && !graph.get(stack.peek()).isEmpty()) {
//先进去的说明是出发城市，那么最先出发的城市最后出来
stack.push(graph.get(stack.peek()).poll());
}
result.add(0, stack.pop());
}
return result;
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/64923.html
