Leetcode[332] Reconstruct Itinerary

Flands 發(fā)布于2019-08-14 15:57 / 3459人閱讀

摘要：復雜度思路重建，應為要按進行排序，所以用來決定下一個要出去的值。

Leetcode[332] Reconstruct Itinerary

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
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"].

DFS + Topological Sort

復雜度
O(N), O(N)

思路
重建graph，應為要按lexical order進行排序，所以用priorityqueue來決定下一個要poll出去的值。

代碼

public List findItinerary(String[][] tickets) {
    HashMap> map = new HashMap<>();
    LinkedList res = new LinkedList<>();
    for(int i = 0; i < tickets.length; i ++) {
        String key = tickets[i][0];
        if(map.get(key) == null) {
            map.put(key, new PriorityQueue());
        }
        map.get(key).offer(tickets[i][1]);
    }
    //
    Stack stack = new Stack<>();
    stack.push("JFK");
    while(!stack.isEmpty()) {
        String cur = stack.peek();
        if(map.containsKey(cur) && map.get(cur).size() > 0) {
            stack.push(map.get(cur).poll());
        }
        else {
            res.addFirst(stack.pop());
        }
    }
    return res;
}