重新安排行程Java

重新安排行程Java

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

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

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次

 

 

class Solution {
    private Deque res;
    private Map> map;

    private boolean backTracking(int ticketNum){
        if(res.size()==ticketNum+1){
            return true;
        }
        String last=res.getLast();
        if(map.containsKey(last)){
            for(Map.Entry 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 findItinerary(List> tickets) {
            map=new HashMap>();
            res=new linkedList<>();
            for(Listt:tickets){
                Map temp;
                if(map.containsKey(t.get(0))){
                    temp=map.get(t.get(0));
                    temp.put(t.get(1),temp.getOrDefault(t.get(1),0)+1);
                }else{
                    temp=new TreeMap<>();
                    temp.put(t.get(1),1);
                }
                map.put(t.get(0),temp);
            }
            res.add("JFK");
            backTracking(tickets.size());
            return new ArrayList<>(res);
    }
}

我自己用IDEA跑了一下，结果更容易理解代码的循环是如何进行的