首页 > 其他 > 详细

332. Reconstruct Itinerary

时间:2019-07-10 15:25:39      阅读:99      评论:0      收藏:0      [点我收藏+]


July-10-2019

这个题,有点像course schedule,然后初始点是JFK已经告诉你了。用node, list来建图,正常DFS就行。 这个2个需要注意:

  • 要求排序,LIST需要排序,所以用了PQ
  • 有[JFK, PDX][JFK, DUB][PDX, NRT]这样,DUB放在最后,所以从JFK开始的DFS,要遍历JFK的整个PQ。
class Solution {
    
    private static final String START_CITY = "JFK";
    
    public List<String> findItinerary(List<List<String>> tickets) {
        
        if (tickets == null || tickets.isEmpty()) return Arrays.asList(START_CITY);
        List<String> res = new ArrayList<>();
        
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        tickets.stream().forEach(path -> {
            String from = path.get(0);
            String to = path.get(1);
            if (!graph.containsKey(from)) {
                graph.put(from, new PriorityQueue<String>());
            }
            graph.get(from).add(to);
        });
        
        dfs(graph, START_CITY , res);
        
        return res;
    }
    
    public void dfs(Map<String, PriorityQueue<String>> graph, String city, List<String> res) {
        while (graph.containsKey(city) && !graph.get(city).isEmpty()) {
            dfs(graph, graph.get(city).poll(), res);
        }

        res.add(0, city);
    }
     
}

332. Reconstruct Itinerary

原文:https://www.cnblogs.com/reboot329/p/11164055.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!