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());
}
}
這道題目做完真的花了九牛二虎之力。屯耸。
原因是題目意思理解錯(cuò)了。我以為只要找到一條路徑字典順序最小就行了蹭劈，不用用光所有機(jī)票疗绣。
然后就直接貪心。
后來(lái)發(fā)現(xiàn)是要用光所有機(jī)票铺韧，找出字典順序最小的那一鏈多矮。
其實(shí)思路還是很明顯的，建 graph
然后DFS
需要注意的是哈打。
1 塔逃。
什么時(shí)候停止dfs
我以前以為是，當(dāng)這個(gè)城市沒有飛往其他任何地方的機(jī)票時(shí)料仗，停止湾盗。其實(shí)是錯(cuò)的。
因?yàn)闂l件是用光所有機(jī)票罢维。所以當(dāng)我們用的機(jī)票個(gè)數(shù)等于總機(jī)票個(gè)數(shù)時(shí)淹仑，就可以停止了。
2 肺孵。
遍歷相鄰結(jié)點(diǎn)匀借，有序性的確保。
我一開始打算用TreeSet,然后他帶來(lái)的一個(gè)問題是平窘，每當(dāng)我用完一張機(jī)票吓肋，我需要把它從set里面刪掉，但是我遍歷的時(shí)候不能刪除瑰艘，否則會(huì)有 concurrent exception
于是我采用簡(jiǎn)單的是鬼。
for (int i = 0; i < size; i++) {...}
來(lái)遍歷，同時(shí)設(shè)置一個(gè)Hashset用來(lái) 存所有用過(guò)的機(jī)票紫新，這樣我就不用從set里面刪除了均蜜。
String ticket = from + "->" + to;
if (set.contains(ticket)) {
continue;
}
else {...}
然后發(fā)現(xiàn)了一個(gè)致命問題，
機(jī)票可能會(huì)有重復(fù)芒率，即囤耳，
JFK -> AMI 的機(jī)票可能會(huì)有兩站，都得用了。
那么充择，我的set將不可能再被使用了德玫。。椎麦。宰僧。
于是放棄了，看了答案观挎，
reference:
https://discuss.leetcode.com/topic/36621/java-11ms-solution-hashmap-sorted-list
最關(guān)鍵的就是用琴儿，list，一開始構(gòu)建圖的時(shí)候键兜，得確保鄰居結(jié)點(diǎn)在鏈表中的有序性凤类。所以單獨(dú)寫了一個(gè)函數(shù)。
還有就是 total = tickets.length + 1;
這個(gè)得自己體會(huì)下普气。
Anyway, Good luck, Richardo! -- 09/11/2016
