重新安排行程

332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

• 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1：

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

提示：

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• fromi.length == 3
• toi.length == 3
• fromi 和 toi 由大写英文字母组成
• fromi != toi

解题思路

需要先将tickets按照字典排序

因为只需要1个行程，故回溯的返回值是true则表明找到了形成

使用used数组记录机票是否使用过

递归结束的条件是找到了4个机场，使用path存储机场的顺序

代码

class Solution {
    List<String> ans;
    List<String> path = new ArrayList<>();
    boolean[] used; //判断车票是否使用过

    public List<String> findItinerary(List<List<String>> tickets) {
        used = new boolean[tickets.size()]; 
        path.add("JFK");
        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
        traversal(tickets, used);
        return ans;

    }

    public boolean traversal(List<List<String>> tickets, boolean[] used){
        if(path.size() == tickets.size() + 1){ //机票数量+1 = 地点的数量，结束递归
            ans = new ArrayList<>(path);
            return true;
        }
        for(int i = 0; i < tickets.size(); i++){
            //该票的起始地点与path的最后一个地点相同
            String start = tickets.get(i).get(0);
            String end = tickets.get(i).get(1);
            if(start.equals(path.get(path.size()-1)) && used[i] == false){
                path.add(end);
                used[i] = true;
                if(traversal(tickets, used)){
                    return true;
                }
                used[i] = false;
                path.remove(path.size()-1);
            }
        }
        return false;
    }


}

优化

按照前面的方案，每次遍历一层的时候都需要进行很繁琐的判断，而且查找也要逐个查找，非常费时间。于是在刚才的基础上，能不能采取一个map集合，把我们所有的航班机票按序存储进去，这样我们在进行查找的时候就会很方便了，大大节省时间。

我们采取**Map<出发机场, map<到达机场, 航班次数>>的形式来存储，其中map<到达机场, 航班次数>**为TreeMap有序集合（会根据达到机场的字典顺序从小到大排序），我们再按顺序遍历这个map集合不就行了，还帮助我们完成了used数组的功能。

这样我们就可以只根据出发机场这一个信息，获取到我们从当前出发机场能到达的所有机场以及对应的票数了，

class Solution {
    List<String> res = new ArrayList<>();
    Map<String, Map<String,Integer>> map = new HashMap<>(); //Map<起始地址，Map<到达地址，航班次数>> ,航班次数就是票数，0说明已经没有到达该地址的票
    public List<String> findItinerary(List<List<String>> tickets) {
        for(List<String> ticket: tickets){
            String start = ticket.get(0);
            String end = ticket.get(1);
            Map<String,Integer> treeMap;
            if(map.containsKey(start)){  //如果map中有ticket中的起始地址
                treeMap = map.get(start); //获取该起始地址对应的map,使到达地址航班次数+1
                treeMap.put(end, treeMap.getOrDefault(end, 0) + 1 );
            }else{
                treeMap = new TreeMap<>(); //升序map
                treeMap.put(end, 1); //目的地址设为1
            }
            map.put(start, treeMap);
        }

        res.add("JFK"); //起始地址一定是JFK
        backTracking(tickets.size());
        return res;
    }

    public boolean backTracking(int ticketNum){
        if(res.size() == ticketNum+1){//最小航班次数是票数+1
            return true; 
        }
        String end = res.get(res.size()-1);
        if(map.containsKey(end)){ //防止出现null,因为last不一定有下一个地址
            for(Map.Entry<String, Integer> target : map.get(end).entrySet()){  //获取路程中最后一个地址的映射
                int count = target.getValue(); 
                if(count>0){
                    res.add(target.getKey()); //把该地址加入行程
                    target.setValue(count-1); //加入行程后，航班次数-1
                    if(backTracking(ticketNum)) return true;
                    res.remove(res.size()-1);
                    target.setValue(count);
                }
            }
        }
        return false;
    }
}