P183 行程安排

描述#

这个题目说的是，给你一组由出发机场与到达机场 [from, to] 表示的机票，你要按顺序把途经的机场排列出来。每个机场都由 3 个大写字母表示，并且一开始从 JFK 机场出发。

注意，所有的机票都要用上，并且它们至少可以组成一个有效的行程。如果存在多个有效行程，则返回字典序最小的那个行程。

为了方便演示，我们假设用单个大写字母来表示机场，并且一开始由 A 机场出发。

比如说，给你的机票是：
[B, D]
[A, B]
[C, E]
[D, C]
这 4 张机票只能构成一个有效行程：
[A, B, D, C, E]
再比如说，给你的机票是：
[A, C]
[A, B]
[C, B]
[B, A]
这 4 张机票可以组成两个有效的行程：
[A, B, A, C, B]
[A, C, B, A, B]
在这两个有效行程中，出发机场都是 A，然后第一个行程来到机场 B，而第二个行程来到机场 C。B 在字典序上是小于 C 的，因此我们要返回第一个有效行程：
[A, B, A, C, B]

代码#

public class AlgoCasts {

  class Pair<F, S> {
    public F first;
    public S second;
    Pair(F first, S second) {
      this.first = first;
      this.second = second;
    }
  }

  private boolean dfs(String from, int total, List<String> result,
                      Map<String, List<Pair<String, Boolean>>> map) {
    if (result.size() == total) return true;
    List<Pair<String, Boolean>> tos = map.get(from);
    if (tos == null) return false;

    for (Pair<String, Boolean> e: tos) {
      if (e.second) continue;
      e.second = true;
      result.add(e.first);
      if (dfs(e.first, total, result, map)) return true;
      result.remove(result.size()-1);
      e.second = false;
    }
    return false;
  }

  // Time: O(n!), Space: O(n)
  public List<String> findItineraryBruteForce(List<List<String>> tickets) {
    Map<String, List<Pair<String, Boolean>>> map = new HashMap<>();
    for (List<String> e: tickets) {
      if (!map.containsKey(e.get(0))) map.put(e.get(0), new ArrayList<>());
      map.get(e.get(0)).add(new Pair<>(e.get(1), false));
    }
    for (List<Pair<String, Boolean>> list: map.values())
      list.sort(Comparator.comparing(pair -> pair.first));
    int total = tickets.size() + 1;
    List<String> result = new ArrayList<>();
    result.add("JFK");
    dfs("JFK", total, result, map);
    return result;
  }

  private void hierholzer(String from, List<String> result,
                          Map<String, PriorityQueue<String>> map) {
    PriorityQueue<String> tos = map.get(from);
    while (tos != null && !tos.isEmpty())
      hierholzer(tos.poll(), result, map);
    result.add(0, from);
  }

  // Time: O(n*log(n)), Space: O(n)
  public List<String> findItineraryHierholzer(List<List<String>> tickets) {
    Map<String, PriorityQueue<String>> map = new HashMap<>();
    for (List<String> e: tickets) {
      if (!map.containsKey(e.get(0))) map.put(e.get(0), new PriorityQueue<>());
      map.get(e.get(0)).add(e.get(1));
    }
    List<String> result = new LinkedList<>();
    hierholzer("JFK", result, map);
    return result;
  }

}