332.重新安排行程

基本思想：

回溯

具体实现：

 

 

1.参数

 Map<String, Map<String, Integer>> map   记录航班的映射关系

ticketNum，表示有多少个航班（终止条件会用上）

2.递归终止条件

回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1）

代码：

class Solution {
    private Deque<String> res;
    private Map<String, Map<String, Integer>> map;//<出发机场, map<到达机场, 航班次数>> 

    private boolean backTracking(int ticketNum){
        if(res.size() == ticketNum + 1){
            return true;
        }
        String last = res.getLast();
        if(map.containsKey(last)){//防止出现null
            for(Map.Entry<String, Integer> target : map.get(last).entrySet()){
                int count = target.getValue();
                if(count > 0){
                    res.add(target.getKey());
                    target.setValue(count - 1);
                    if(backTracking(ticketNum)) return true;
                    res.removeLast();
                    target.setValue(count);
                }
            }
        }
        return false;
    }

    public List<String> findItinerary(List<List<String>> tickets) {
        map = new HashMap<String, Map<String, Integer>>();
        res = new LinkedList<>();
        for(List<String> t : tickets){
            Map<String, Integer> temp;
            if(map.containsKey(t.get(0))){//map中包含遍历到的出发机场
                temp = map.get(t.get(0));//该出发机场对应的<到达机场，航班次数>赋给temp
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
                //修改temp<到达机场，航班次数>
            }else{
                temp = new TreeMap<>();//升序Map
                temp.put(t.get(1), 1);
            }
            map.put(t.get(0), temp);

        }
        res.add("JFK");
        backTracking(tickets.size());
        return new ArrayList<>(res);
    }
}