有向图 Directed Graph


332. Reconstruct Itinerary

这道题我一看描述乱七八糟一大坨,再一看贡献者 dietpepsi,瞬间懂了。

这题其实和之前用 DFS 处理 topological sort 的代码非常像,主要区别在于存 graph 的方式不同,这里是一个 String 直接连着对应的 next nodes,而且形式是 min heap:

  • 原题给的是 edges,所以图是自己用 hashmap 建的。

  • min heap 可以自动保证先访问 lexicographical order 较小的;

  • 同时 poll 出来的 node 自动删除,免去了用 List 的话要先 collections.sort 再 remove 的麻烦。

  • 这种以 “edge” 为重心的算法多靠 heap,比如 dijkstra.

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        LinkedList<String> result = new LinkedList<>();

        if (tickets == null || tickets.length == 0) return result;

        Map<String, PriorityQueue<String>> map = new HashMap<>();
        for (String[] ticket : tickets) {
            if (!map.containsKey(ticket[0])) map.put(ticket[0], new PriorityQueue<>());

            map.get(ticket[0]).add(ticket[1]);
        }
        dfs(map, result, "JFK");

        return new ArrayList<String>(result);
    }
    private void dfs(Map<String, PriorityQueue<String>> map, LinkedList<String> result, String start) {
        while (map.containsKey(start) && !map.get(start).isEmpty()) {
            dfs(map, result, map.get(start).poll());
        }
        result.addFirst(start);
    }
}

results matching ""

    No results matching ""