原题链接: 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; }
|