这题做了一天。。一天。。上午拿到之后感觉挺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),
被他的第一篇计划燃得一塌糊涂,人的意志力、执行力强起来真让人感动。