Leetcode 332. 重新安排行程

Leetcode 332. 重新安排行程

Leetcode 332. 重新安排行程（困难）
题目地址：Leetcode 332. 重新安排行程

目录

• • • 思路
    • 举例分析
    • Java代码：

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

思路：图论的深度优先搜索
重难点：存储两点之间的映射关系，深搜的顺序，深搜结束条件，避免深搜过程中的死循环

思路

文本较长，请结合下面的例子阅读（推荐理解题意之后先阅读例子，再结合代码看思路）

1. 全局变量：
   HashMap> itinerary_list ：存储机票的出发地和到达地（相当于机票槽，存储多张机票，相同出发地的机票放在同一个机票槽中），TreeMap以字母顺序排序，Integer存储到达的次数（相当于相同出发地和目的地的机票数量，维护这个值能够避免死循环）
   linkedList res_list ：存储行程序列，当作队列来使用很方便

2. 递归返回值：boolean值，由于递归过程中通过子树的递归结果判断是否需要继续回溯和搜索；递归参数：ticketNum 存储机票数

3. 结束条件：res_list == ticketNum + 1 行程序列等于机票数 + 1

4. 单层循环：获取行程序列res_list的末尾节点，作为新的出发机场startAirport，然后在映射关系中查找出发机场startAirport能够到达的目的机场endAirport，将目的机场加入res_list，同时修改映射关系（机票）的值为value-1；递归查找下一个目的机场，如果递归返回的结果为true，结束查找；回溯时从res_list中将endAirport删除，该机票映射关系的值恢复为value

5. 初始化：

    查找映射关系中是否有出发机场：{
    	若没有则新建一个映射关系；（新建一个机票槽）
    	若有，查找是否有到达机场：（在已有的机票槽中搜索）{
    		若没有则新建一个映射关系，数量初始化为1（新建一张机票）
    		若有，更新映射关系的数量：原来的值+1（相同出发地和目的地的机票多一张）
    		}
    	}
   

举例分析

输入用例：tickets = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]

图示：

• 初始化
  HashMap> itinerary_list
  linkedList res_list
  

• 进入递归函数：

第一轮递归：把 JFK 作为起始地点，查找itinerary_list，发现第一个value不为 0 的目的地点是ATL，那么将ATL加入行程序列res_list，同时将ATL的value值减 1，如下图所示

第二轮递归：把 ATL 作为起始地点，查找itinerary_list，发现第一个value不为 0 的目的地点是 JFK，那么将 JFK 加入行程序列res_list，同时将 JFK 的value值减 1，如下图所示

以此类推，最终结果为：

Java代码：

class Solution {

    //机票槽
    HashMap> itinerary_list = new HashMap<>();
    //用于存储行程序列，需要获取末尾值作为新的出发地来寻找下一个目的地
    linkedList res_list = new linkedList<>();

    public List findItinerary(List> tickets) {
        if(tickets == null || tickets.size() == 0) return res_list;
        for(List ticket: tickets) {     //获取机票
            String departure = ticket.get(0);   //出发地
            String arrival = ticket.get(1);     //到达地
            if(itinerary_list.containsKey(departure)) { //映射表中有该出发地
                TreeMap departure_count = itinerary_list.get(departure);
                departure_count.put(arrival, departure_count.getOrDefault(arrival, 0) + 1);
            }else {                             //映射表中没有该出发地
                TreeMap departure_count = new TreeMap<>();
                departure_count.put(arrival, 1);
                itinerary_list.put(departure, departure_count);
            }
        }
        res_list.add("JFK");    //路程序列初始化
        backTracking(tickets.size());
        return res_list;
    }

    //由于需要用到递归的返回值，所以返回值不能为void
    public boolean backTracking(int ticketNum) {
        if(res_list.size() == ticketNum + 1) {
            return true;
        }
        String startAirport = res_list.getLast();
        //判断有没有出发地为startAirport的机票，防止对NULL进行 *** 作，报异常
        if(itinerary_list.containsKey(startAirport)) {
            TreeMap departure_count = itinerary_list.get(startAirport);
            for(Map.Entry dc_entry: departure_count.entrySet()) {	
                int count = dc_entry.getValue();
                //寻找有效的映射关系（value > 0 表示机票没用过）
                if(count > 0) {
                    dc_entry.setValue(count - 1);
                    res_list.add(dc_entry.getKey());
                    //判断是否已经找到正确行程序列了，如果找到了直接返回，不用回溯了
                    if(backTracking(ticketNum)) return true;
                    res_list.removeLast();
                    dc_entry.setValue(count);
                }
            }
        }
         //该出发地没有下一站，但是还有机票没用完，机票排序不正确，返回false
        return false;
    }
}

参考：Carl 哥的代码随想录
真的超级好的算法学习文档！强力推荐！