332. 重新安排行程

题目描述

解题思路

记录一个机战到另一个机战的票数的映射关系，使用Map> 表示 Map<出发机场, Map<到达机场, 航班次数>> targets。可以使用”航班次数”这个字段的数字做相应的增减，来标记到达机场是否使用过了。如果“航班次数”大于零，说明目的地还可以飞，如果如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。也就不用删除已经使用过的票。也就是如果使用Map> targets，那么在删除一条使用过的路线的时候，那么该集合就失效了，下一次递归也就没了该路线。

• 递归函数参数

参数里还需要ticketNum，表示有多少个航班（终止条件会用上）。返回值类型使用boolean，表 示如果找到一条航班那就返回，不再递归，因为我们只需要找到一个行程，就是在树形结构中唯一 的一条通向叶子节点的路线。

• 递归终止条件

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

• 单层搜索的逻辑

回溯的过程中，如何遍历一个机场所对应的所有机场呢？
这里刚刚说过，在选择映射函数的时候，不能选择Map> targets， 因为一旦有元素增删multiset的迭代器就会失效，当然可能有牛逼的容器删除元素迭代器不会失效，这里就不在讨论了。
可以说本题既要找到一个对数据进行排序的容器，而且还要容易增删元素，迭代器还不能失效。

public List<String> findItinerary(List<List<String>> tickets) {
    // 封装数据为 Map<出发机场, map<到达机场, 航班次数>>
    for (List<String> ticket : tickets) {   // 防止出现null
        Map<String, Integer> tempMap;
        if (map.containsKey(ticket.get(0))) {
            tempMap = map.get(ticket.get(0));
            tempMap.put(ticket.get(1), tempMap.getOrDefault(ticket.get(1), 0) + 1);
        } else {
            tempMap = new TreeMap<>();  // 升序Map
            tempMap.put(ticket.get(1), 1);
        }
        map.put(ticket.get(0), tempMap);
    }
    path.add("JFK");    // 开始地方
    backtracking(tickets.size());
    return new ArrayList<>(path);
}
Map<String, Map<String, Integer>> map = new HashMap<>();
LinkedList<String> path = new LinkedList<>();
/**
         * 回溯求线路
         *
         * @param ticketNum 表示有多少个航班
         * @return 此时只需要一条线路，返回值为Boolean即可
         */
public boolean backtracking(int ticketNum) {
    if (path.size() == ticketNum + 1) {
        return true;    // 线路等于航班加一时满足一圈航程
    }
    String last = path.get(path.size() - 1);  // 获取上一个站台，来进行下一次的选择
    if (map.containsKey(last)) {
        for (Map.Entry<String, Integer> entry : map.get(last).entrySet()) { // 这个站台的航班
            Integer count = entry.getValue(); // 表示航班数量
            if (count > 0) {    // 此时可以飞到此站
                path.add(entry.getKey());
                entry.setValue(count - 1);// 此路程的票数减一
                if (backtracking(ticketNum)) return true;   // 如果此时搜索到一条线路则停止搜索
                path.removeLast();  // 回溯
                entry.setValue(count);// 恢复路程的票数
            }
        }
    }
    return false;
}