332. 重新安排行程 (opens new window)

1.第一版超时😭😭😭

关键在于按照字典序输出结果，这里两种思路都超时了：

• 第一种：dfs搜集所有的路径，然后使用Collections.sort对所有路径按照字典序进行排序。❌
• 第二种：经过前面的教训，没必要搜集所有的路径，只需要维护一个最小字典序路径。同一个索引下如果"当前目的地"比"最小路径中的目的地"的字典序还要大，那么当前新路径就不需要往下搜索了；否则更新最小路径。但是这种方法实现比较复杂，假设当前目的地不需要“进行过滤判断”，往下搜索时如果更新了最小路径，此时又需要进行“过滤判断”。❌(实际上这里已经有排序的意味了)

第一种方法代码实现如下：

class Solution {
    List<List<String>> res=new ArrayList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        List<String> path=new ArrayList<>();
        path.add("JFK");
        boolean[] visited=new boolean[tickets.size()];
        dfs(tickets,path,visited,"JFK");
        Collections.sort(res, new Comparator<List<String>>() {
            @Override
            public int compare(List<String> o1, List<String> o2) {
                for (int i = 0; i < o1.size(); i++) {
                    if(o1.get(i).compareTo(o2.get(i))!=0) return o1.get(i).compareTo(o2.get(i));
                }
                return -1;
            }
        });
        return res.get(0);
    }
    public void dfs(List<List<String>> tickets,List<String> path,boolean[] visited,String place){
        if(path.size()==tickets.size()+1){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<tickets.size();i++){
            List<String> list=tickets.get(i);
            if((!visited[i])&&(list.get(0).equals(place))){
                String destination=list.get(1);
                path.add(destination);
                visited[i]=true;
                dfs(tickets,path,visited,destination);
                path.remove(path.size()-1);
                visited[i]=false;
            }
        }
    }
}

2.排序+回溯

核心思路：已知出发点时，直接按照字典序顺序选择下一个目的地。

• ✨保证有序：直接对tickets所有目的地按照字典序进行排序，保证同一个出发地按照索引遍历时是有序的。
• 回溯时通过visited数组来判断是否重复搜索。
• 全局flag控制路径加入：因为每个地点加入时是按照字典序加入的，因此只要当前路径size包含所有机票，那么此时的路径就是最后的结果。

class Solution {
      List<String> res=new ArrayList<>();
     boolean flag = false;
    public  List<String> findItinerary(List<List<String>> tickets) {
        Collections.sort(tickets, new Comparator<List<String>>() {
            @Override
            public int compare(List<String> o1, List<String> o2) {
                return o1.get(1).compareTo(o2.get(1));
            }
        });
        res.add("JFK");
        dfs(tickets, new boolean[tickets.size()], "JFK");
        return res;
    }
    public  void dfs(List<List<String>> tickets, boolean[] visited,String place) {
        if(res.size()==tickets.size()+1){
            flag=true;
            return ;
        } 
        for (int i = 0; i < tickets.size(); i++) {
            List<String> list = tickets.get(i);
            if (list.get(0).equals(place) && !visited[i]&&!flag) {
                visited[i] = true;
                res.add(list.get(1));
                dfs(tickets, visited, list.get(1));
                //结束路径添加
                if(!flag){
                    visited[i] = false;
                res.remove(res.size() - 1);
                }
            }
        }
    }
}

3.Map聚合+优先级队列排序+逆序递归

核心：使用 Map<String,PriorityQueue<String>>对所有每个出发地的所有目的地进行聚合。聚合的所有目的地按照字典序排序。

实现的难点在于有序队列的搜索性判断如何处理？显然有序队列用不了回溯，回溯时入队元素又会放到首元素。这里递归时使用逆序输出的方法，先将队列所有地点按照字典序顺序出列，最后再将当前地点插入结果集。

PS：倒序插入这一手很难想，仅供参考。

class Solution {
    List<String> res=new ArrayList<>();
    Map<String,PriorityQueue<String>> map=new HashMap<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        for(int i=0;i<tickets.size();i++){
            List<String> list=tickets.get(i);
            if(!map.containsKey(list.get(0))) map.put(list.get(0),new PriorityQueue<String>());
            PriorityQueue<String> queue=map.get(list.get(0));
            queue.offer(list.get(1));
        }
        dfs(tickets,"JFK");
        Collections.reverse(res);
        return res;
    }
    public void dfs(List<List<String>> tickets,String place){
        if(!map.containsKey(place)){
            res.add(place);
            return;
        }
        PriorityQueue<String> queue=map.get(place);
        while(queue.size()>0){
            if(res.size()==tickets.size()+1) return;
            String str=queue.poll();
            dfs(tickets,str);
        }
        //画龙点睛
        res.add(place);
    }
}