LeetCode 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;
}

题干
思路

LeetCode 332 - Reconstruct Itinerary

题干

思路

FEATURED TAGS

FRIENDS