My code:
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class Solution {
private HashMap<String, List<String>> adj = new HashMap<String, List<String>>();
public List<String> findItinerary(String[][] tickets) {
for (int i = 0; i < tickets.length; i++) {
String from = tickets[i][0];
String to = tickets[i][1];
if (!adj.containsKey(from)) {
adj.put(from, new ArrayList<String>());
}
insert(to, adj.get(from));
}
int total = tickets.length + 1;
List<String> ret = new ArrayList<String>();
ret.add("JFK");
helper("JFK", ret, 1, total);
return ret;
}
private boolean helper(String from, List<String> ret, int num, int total) {
if (num >= total) {
return true;
}
else if (!adj.containsKey(from) || adj.get(from).size() == 0) {
return false;
}
for (int i = 0; i < adj.get(from).size(); i++) {
String to = adj.get(from).get(i);
ret.add(to);
adj.get(from).remove(i);
boolean flag = helper(to, ret, num + 1, total);
if (flag) {
return true;
}
else {
ret.remove(ret.size() - 1);
adj.get(from).add(i, to);
}
}
return false;
}
private void insert(String s, List<String> list) {
for (int i = 0; i < list.size(); i++) {
if (s.compareTo(list.get(i)) <= 0) {
list.add(i, s);
return;
}
}
list.add(s);
}
public static void main(String[] args) {
Solution test = new Solution();
String[][] tickets = new String[][]{{"EZE","AXA"},{"TIA","ANU"},{"ANU","JFK"},{"JFK","ANU"},{"ANU","EZE"},{"TIA","ANU"},{"AXA","TIA"},{"TIA","JFK"},{"ANU","TIA"},{"JFK","TIA"}};
List<String> ret = test.findItinerary(tickets);
System.out.println(ret.toString());
}
}
这道题目做完真的花了九牛二虎之力。。
原因是题目意思理解错了。我以为只要找到一条路径字典顺序最小就行了，不用用光所有机票。
然后就直接贪心。
后来发现是要用光所有机票，找出字典顺序最小的那一链。
其实思路还是很明显的，建 graph
然后DFS
需要注意的是。
1 。
什么时候停止dfs
我以前以为是，当这个城市没有飞往其他任何地方的机票时，停止。其实是错的。
因为条件是用光所有机票。所以当我们用的机票个数等于总机票个数时，就可以停止了。
2 。
遍历相邻结点，有序性的确保。
我一开始打算用TreeSet,然后他带来的一个问题是，每当我用完一张机票，我需要把它从set里面删掉，但是我遍历的时候不能删除，否则会有 concurrent exception
于是我采用简单的。
for (int i = 0; i < size; i++) {...}
来遍历，同时设置一个Hashset用来 存所有用过的机票，这样我就不用从set里面删除了。
String ticket = from + "->" + to;
if (set.contains(ticket)) {
continue;
}
else {...}
然后发现了一个致命问题，
机票可能会有重复，即，
JFK -> AMI 的机票可能会有两站，都得用了。
那么，我的set将不可能再被使用了。。。。
于是放弃了，看了答案，
reference:
https://discuss.leetcode.com/topic/36621/java-11ms-solution-hashmap-sorted-list
最关键的就是用，list，一开始构建图的时候，得确保邻居结点在链表中的有序性。所以单独写了一个函数。
还有就是 total = tickets.length + 1;
这个得自己体会下。
Anyway, Good luck, Richardo! -- 09/11/2016
