這題做了一天架馋。全闷。一天。屏鳍。上午拿到之后感覺挺easy的局服，我想像NQueens那樣先DFS找到所有的解。結(jié)果怎么也無法跟N-Queens類比上山涡，主要是backtracking的時候很難清空從前的狀態(tài)唆迁。最后投了，參考了這個人的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

投了投了抄罕。

另外于颖，今天發(fā)現(xiàn)一個人的刷題博客(http://www.reibang.com/u/d709e59ac317)，
被他的第一篇計劃燃得一塌糊涂榨崩，人的意志力、執(zhí)行力強起來真讓人感動母蛛。