LeetCode 332 - Reconstruct Itinerary

作者 QIFAN 日期 2017-01-26
LeetCode 332 - Reconstruct Itinerary

原题链接: 332. Reconstruct Itinerary


题干

给定一个人的(出发地,目的地)形式的飞机票,要求重新他的整理行程,返回一个从“ JFK ” 机场的一整串行程,所有机票都要用。如果有多条行程,则选择 lexicographical order 较小的。假设必然有一条可行路径。

举例
输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]
输出: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”].

输入: [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
输出: [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
解释:另一条可行的行程为 [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”] ,但它的 lexical order 更大。

思路

概括的说就是寻找图中以“ JFK ”开头的且用完所有飞机票(遍历 egdes exactly once )。

首先我要先根据给定关系对构建图。
图节点:因为一个出发地可能会有很多目的地,然后用一个 minPQ 。

建立关系:用一个 Hashmap<String, PriorityQueue<String>> 来保存已经进入图的节点。

遍历图,先从 “JFK” ,依次按照字母较小的顺序来遍历。如果走到了尽头,但并没有遍历所有点,需要返回到上一个点,进行新一轮 DFS ,直到无重复遍历完。
要解决的问题:
1. 如何知道没有遍历所有点?
使用一个 count ,访问一条边加 1 ,撤销一条边减 1 。当 count == input.length 则结束。
2. 怎么返回上一个点并使得刚撤销的 edge 重新变成没有访问?
使用一个 stack ,curr 若有下一个地点( PQ 不为空),则推入栈(就像树的遍历一样),若为空且没有满足遍历,则 curr 成为栈首的下一条,再将当前的重新推入 PQ 。

思路卡在了上面,最后有给出自己的解法,不过很累赘。DFS 和图的确很不熟,即使看了大神的代码也没有理解的很透彻。
参考:@StefanPochmann Short Ruby / Python / Java / C++

代码:

Map<String, PriorityQueue<String>> targets = new HashMap<>();
List<String> route = new LinkedList();
public List<String> findItinerary(String[][] tickets) {
for (String[] ticket : tickets)
targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
visit("JFK");
return route;
}
void visit(String airport) {
while(targets.containsKey(airport) && !targets.get(airport).isEmpty()) // 还有别的出度
visit(targets.get(airport).poll());
route.add(0, airport); // 加入最先没有出度的机场
}

有一点需要反思的是,用完所有的机票 就是说图里面只有一个起点和终点。也就是说,除了这两个点,其他中转站的出度和入度都是偶数。因为机票都是(出发 –> 到达),也就是说 map 包含了所有的出度。所以 map 中没有的 key 一定是最后的终点。或者有进无出 (PQ) 为空的一定是最后的。这里就可以用递归的思想,当最后出口从图中去除,它和它上一个起点的关系也没有了,那就继续回到图中去找下一个有进无出的点。直到所有关系都访问了一遍,然后一层层的回溯就是行程了。也可以用一个 stack 和迭代来完成递归的功能。

最后是我自己的解法,思路是对的,但是太多重复的进站出站, TLE 了。

public List<String> findItinerary(String[][] tickets) {
List<String> res = new ArrayList<>();
if (tickets == null || tickets.length == 0) {
return res;
}
HashMap<String, PriorityQueue<String>> nodesMap = new HashMap<>();
int totalTickets = tickets.length;
for (int i = 0; i < totalTickets; i++) {
if (!nodesMap.containsKey(tickets[i][0])) {
nodesMap.put(tickets[i][0], new PriorityQueue<>());
}
nodesMap.get(tickets[i][0]).add(tickets[i][1]);
}
String curr = "JFK";
while (res.size() < totalTickets) {
if (!nodesMap.containsKey(curr) || nodesMap.get(curr).size() == 0) {
String lastNode = res.get(res.size() - 1);
while (res.size() > 0 && nodesMap.get(lastNode).size() == 0) {
nodesMap.get(lastNode).add(curr);
curr = lastNode;
res.remove(res.size() - 1);
lastNode = res.get(res.size() - 1);
}
String tempcurr = nodesMap.get(lastNode).poll();
nodesMap.get(lastNode).add(curr);
curr = tempcurr;
} else {
res.add(curr); // 上一个点存入栈
curr = nodesMap.get(curr).poll();
}
}
res.add(curr);
return res;
}