332. Reconstruct Itinerary

greatwhole 發(fā)布于2019-08-14 14:17 / 1307人閱讀

摘要：題目解答都是用來(lái)解，一個(gè)用一個(gè)用來(lái)實(shí)現(xiàn)深度優(yōu)先搜索，搜索到一個(gè)城市只是的時(shí)候即沒(méi)有出度的時(shí)候，把這個(gè)記入中去，因?yàn)樗隙ㄊ亲詈蟮竭_(dá)的城市，然后依次向前類推的要求在存入的時(shí)候就用先存好先進(jìn)去的說(shuō)明是出發(fā)城市，那么最先出發(fā)的城市最后出來(lái)

題目：
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來(lái)解，一個(gè)用recursion, 一個(gè)用stack來(lái)實(shí)現(xiàn)：
Recursion version:

public void dfs(String departure, Map> graph, List result) {
    //深度優(yōu)先搜索，搜索到一個(gè)城市只是arrival city的時(shí)候（即沒(méi)有出度的時(shí)候，把這個(gè)city記入list中去，因?yàn)樗隙ㄊ亲詈蟮竭_(dá)的城市，然后依次向前類推
    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的時(shí)候就用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()) {
        //先進(jìn)去的說(shuō)明是出發(fā)城市，那么最先出發(fā)的城市最后出來(lái)
            stack.push(graph.get(stack.peek()).poll());
        }
        result.add(0, stack.pop());
    }
    return result;
}