332. Reconstruct Itinerary[PriorityQueue]

这题做了一天。。一天。。上午拿到之后感觉挺easy的，我想像NQueens那样先DFS找到所有的解。结果怎么也无法跟N-Queens类比上，主要是backtracking的时候很难清空从前的状态。最后投了，参考了这个人的dfs。

    public List<String> findItinerary(String[][] tickets) {
        Map<String, List<String>> map = new HashMap<>();
        for (String[] ticket : tickets) {
            List<String> dests = map.get(ticket[0]);
            if (dests == null) {
                dests = new ArrayList<>();
                dests.add(ticket[1]);
                map.put(ticket[0], dests);
            } else {
                dests.add(ticket[1]);
            }
        }
        for (List<String> dests : map.values()) {
            Collections.sort(dests);
        }

        List<String> res = new ArrayList<>();
        res.add("JFK");
        dfs(res, map, "JFK", tickets.length);
        return res;
    }

    //
    public void dfs(List<String> res, Map<String, List<String>> map, String src, int length) {
        if (res.size() == length + 1) {
            return;
        }
        List<String> dests = map.get(src);

        if (dests != null && dests.size() > 0) {
            for (int i = 0; i < dests.size(); i++) {
                String dest = dests.remove(i);
                res.add(dest);
                dfs(res,  map, dest, length);
                if (res.size() == length + 1) return;
                dests.add(i, dest);
                res.remove(res.size() - 1);
            }
        }
    }

上面的代码挺长的。摘抄一个programcreek的 priorityqueue的答案：

public class Solution{
    HashMap<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
    LinkedList<String> result = new LinkedList<String>();
 
    public List<String> findItinerary(String[][] tickets) {
        for (String[] ticket : tickets) {
            if (!map.containsKey(ticket[0])) {
                PriorityQueue<String> q = new PriorityQueue<String>();
                map.put(ticket[0], q);
            }
            map.get(ticket[0]).offer(ticket[1]);
        }
 
        dfs("JFK");
        return result;
    }
 
    public void dfs(String s) {
        PriorityQueue<String> q = map.get(s);
 
        while (q != null && !q.isEmpty()) {
            dfs(q.poll());
        }
 
        result.addFirst(s);
    }
}

另外这题还可以用欧拉通路来做：
https://leetcode.com/discuss/84659/short-ruby-python-java-c

投了投了。

另外，今天发现一个人的刷题博客(http://www.jianshu.com/u/d709e59ac317)，
被他的第一篇计划燃得一塌糊涂，人的意志力、执行力强起来真让人感动。