问题

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始

提示：

  • 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
  • 所有的机场都用三个大写字母表示（机场代码）
  • 假定所有机票至少存在一种合理的行程
  • 所有的机票必须都用一次 且 只能用一次

示例 1：
输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出：["JFK", "MUC", "LHR", "SFO", "SJC"]

示例 2：
输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后

思路

之前我们用回溯法解决了如下问题：组合问题，分割问题，子集问题，排列问题

直觉上来看 这道题和回溯法没有什么关系，更像是图论中的深度优先搜索

实际上确实是深搜，但这是深搜中使用了回溯的例子，在查找路径的时候，如果不回溯，怎么能查到目标路径呢

所以我倾向于说本题应该使用回溯法，其实深搜一般都使用了回溯法的思路

这道题目有几个难点：

  • 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
  • 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢
  • 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢
  • 搜索的过程中，如何遍历一个机场所对应的所有机场

如何理解死循环

对于死循环，我来举一个有重复机场的例子：
leetcode-332：重新安排行程 - 图1
为什么要举这个例子呢，就是告诉大家，出发机场和到达机场也会重复的，如果在解题的过程中没有对集合元素处理好，就会死循环

该记录映射关系

字母序靠前排在前面，如何该记录映射关系呢

一个机场映射多个机场，机场之间要靠字母序排列，一个机场映射多个机场，可以使用HashMap，如果让多个机场之间再有顺序的话，就是用HashMap或者HashSet

这样存放映射关系可以定义为 HashMap<String, Set<String>> targets 或者 HashMap<String, Map<String, Integer>> targets

含义如下：
HashMap<String, Set<String>> targets：HashMap<出发机场, 到达机场的集合> targets
HashMap<String, Map<String, Integer>> targets：HashMap<出发机场, Map<到达机场, 航班次数>> targets

这两个结构，我选择了后者，因为如果使用HashMap<String, Set<String>> targets遍历的时候，不能删除元素，一旦删除元素，迭代器就失效了

再说一下为什么一定要增删元素呢，正如开篇图中所示，出发机场和到达机场是会重复的，搜索的过程没及时删除目的机场就会死循环

在遍历HashMap<出发机场, Map<到达机场, 航班次数>> targets的过程中，可以使用”航班次数”这个字段的数字做相应的增减，来标记到达机场是否使用过了

  • 如果“航班次数”大于零，说明目的地还可以飞，如果如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作，相当于说我不删，我就做一个标记

回溯法

  1. public void backtracking(参数) {
  2.     if (终止条件) {
  3.         存放结果;
  4.         return;
  5.     }
  7.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
  8.         处理节点;
  9.         backtracking(路径，选择列表); // 递归
  10.         回溯，撤销处理结果
  11.     }
  12. }

本题以输入：[["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]为例，抽象为树形结构如下：
leetcode-332：重新安排行程 - 图2

  • 递归函数参数

在讲解映射关系的时候，已经讲过了，使用unordered_map> targets; 来记录航班的映射关系，我定义为全局变量。
当然把参数放进函数里传进去也是可以的，我是尽量控制函数里参数的长度。
参数里还需要ticketNum，表示有多少个航班（终止条件会用上）。
代码如下：
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map> targets;
bool backtracking(int ticketNum, vector& result) {

「注意函数返回值我用的是bool！」
我们之前讲解回溯算法的时候，一般函数返回值都是void，这次为什么是bool呢？
因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，如图：
leetcode-332：重新安排行程 - 图3
所以找到了这个叶子节点了直接返回，这个递归函数的返回值问题我们在讲解二叉树的系列的时候，在这篇二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？详细介绍过。
当然本题的targets和result都需要初始化，代码如下：
for (const vector& vec : tickets) {
targets[vec[0]][vec[1]]++; // 记录映射关系
}
result.push_back(“JFK”); // 起始机场

  • 递归终止条件

拿题目中的示例为例，输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] ，这是有4个航班，那么只要找出一种行程，行程里的机场个数是5就可以了。
所以终止条件是：我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了。
代码如下：
if (result.size() == ticketNum + 1) {
return true;
}

已经看习惯回溯法代码的同学，到叶子节点了习惯性的想要收集结果，但发现并不需要，本题的result相当于 回溯算法：求组合总和！中的path，也就是本题的result就是记录路径的（就一条），在如下单层搜索的逻辑中result就添加元素了。

  • 单层搜索的逻辑

回溯的过程中，如何遍历一个机场所对应的所有机场呢？
这里刚刚说过，在选择映射函数的时候，不能选择unordered_map> targets， 因为一旦有元素增删multiset的迭代器就会失效，当然可能有牛逼的容器删除元素迭代器不会失效，这里就不在讨论了。
「可以说本题既要找到一个对数据进行排序的容器，而且还要容易增删元素，迭代器还不能失效」。
所以我选择了unordered_map> targets 来做机场之间的映射。
遍历过程如下：
for (pair& target : targets[result[result.size() - 1]]) {
if (target.second > 0 ) { // 记录到达机场是否飞过了
result.push_back(target.first);
target.second—;
if (backtracking(ticketNum, result)) return true;
result.pop_back();
target.second++;
}
}

可以看出 通过Map<String, Map<String, Integer>> map里的Integer字段来判断 这个集合里的机场是否使用过，这样避免了直接去删元素

  1. class Solution {
  2.     private Deque<String> res;
  3.     private Map<String, Map<String, Integer>> map;
  5.     private boolean backTracking(int ticketNum){
  6.         if(res.size() == ticketNum + 1){
  7.             return true;
  8.         }
  9.         String last = res.getLast();
  10.         if(map.containsKey(last)){//防止出现null
  11.             for(Map.Entry<String, Integer> target : map.get(last).entrySet()){
  12.                 int count = target.getValue();
  13.                 if(count > 0){
  14.                     res.add(target.getKey());
  15.                     target.setValue(count - 1);
  16.                     if(backTracking(ticketNum)) return true;
  17.                     res.removeLast();
  18.                     target.setValue(count);
  19.                 }
  20.             }
  21.         }
  22.         return false;
  23.     }
  25.     public List<String> findItinerary(List<List<String>> tickets) {
  26.         map = new HashMap<String, Map<String, Integer>>();
  27.         res = new LinkedList<>();
  28.         for(List<String> t : tickets){
  29.             Map<String, Integer> temp;
  30.             if(map.containsKey(t.get(0))){
  31.                 temp = map.get(t.get(0));
  32.                 temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
  33.             }else{
  34.                 temp = new TreeMap<>();//升序Map
  35.                 temp.put(t.get(1), 1);
  36.             }
  37.             map.put(t.get(0), temp);
  39.         }
  40.         res.add("JFK");
  41.         backTracking(tickets.size());
  42.         return new ArrayList<>(res);
  43.     }
  44. }

总结

本题其实可以算是一道hard的题目了，关于本题的难点我在文中已经列出了
如果单纯的回溯搜索（深搜）并不难，难还难在容器的选择和使用上
本题其实是一道深度优先搜索的题目，但是这次完全使用回溯法的思路来讲解这道题题目，其实深搜和回溯也是分不开的，毕竟最终都是用递归
如果最终代码，发现照着回溯法模板画的话好像也能画出来，但难就难如何知道可以使用回溯，以及如果套进去