你好,欢迎来到电脑编程技巧与维护杂志社! 杂志社简介广告服务读者反馈编程社区  
合订本订阅
 
 
您的位置:技术专栏 / Web开发
LeetCode332. 重新安排行程
 

题目
给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 出发。

说明:

如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前
所有的机场都用三个大写字母表示(机场代码)。
假定所有机票至少存在一种合理的行程。
1
2
3
示例 1:

输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]
输出: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”]

示例 2:

输入: [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]
输出: [“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]
解释: 另一种有效的行程是 [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”]。但是它自然排序更大更靠后。

分析
最近算法课上讲了图,所以想着这周练习下有关图的算法题。
这个题一开始没有看太懂,坐着飞机几个地方绕来绕去,我真是搞不懂为什么要拿这个东西做例题。。。。。
好啦大概题意就是说,我找到一条路径,可以把这几条路径一次走完,而且,要按照机场的代码排序,也就是按照字符串abc排序。

这个题有两个地方要解决的,第一个就是要把所有路径一次走完,第二个是走的过程我还要先走代码尽量小的。
也就是第一个问题深度优先遍历,第二个排序。

那深度优先遍历还好说,就一直去找下一节点,没有了就返回,但是排序这个我就有点懵圈了,我要把所有结果都走出来再排么,这时间怕是很长吧。。
然后看了网上解题报告,嗯,大家用的是优先队列来解决的。

首先我们要把二维字符串数组保存到一个map里,代表一个 from—— [to1,to2 …] , 在保存from对应的to地点的时候,我们把它保存到优先队列里,自然排序小的在前面,这样,我们在dfs的时候,就可以通过poll来取到最小的啦。

图构建好了之后就是去dfs,按照题目要求从"JFK"开始,找下一个地点, 当发现某个from没有在map里或者某个from对应的优先队列为空,这就代表它没有了下一个节点,放到最后结果的list集合里。
当from对应的队列长度>0,那么就依次去dfs队列里面的地点, 全部dfs完之后记得list.add上from,因为它终要回到这里。

代码
class Solution {
    static Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
    static List<String> list = new ArrayList<String>();

    public static List<String> findItinerary(String[][] tickets) {
        map.clear();
        list.clear();
        for (String[] strings : tickets) {
            if (map.containsKey(strings[0])){
                map.get(strings[0]).add(strings[1]);
            }else{
                PriorityQueue<String> pqt = new PriorityQueue<String>();
                pqt.add(strings[1]);
                map.put(strings[0],pqt);
            }
        }

        dfs("JFK");
        Collections.reverse(list);

        return list;
    }

    public static void dfs(String s){
        if (map.containsKey(s) == false){
            list.add(s);
            return;
        }
        PriorityQueue<String> pq = map.get(s);
        if (pq.size() == 0){
            list.add(s);
            return;
        }else{
            while(pq.size() != 0){
                dfs(pq.poll());
            }
            list.add(s);
        }
    }
}
---------------------
作者:Pi_dan
来源:CSDN
原文:https://blog.csdn.net/qq_38595487/article/details/84479913
版权声明:本文为博主原创文章,转载请附上博文链接!

  推荐精品文章

·2024年2月目录 
·2024年1月目录
·2023年12月目录
·2023年11月目录
·2023年10月目录
·2023年9月目录 
·2023年8月目录 
·2023年7月目录
·2023年6月目录 
·2023年5月目录
·2023年4月目录 
·2023年3月目录 
·2023年2月目录 
·2023年1月目录 

  联系方式
TEL:010-82561037
Fax: 010-82561614
QQ: 100164630
Mail:gaojian@comprg.com.cn

  友情链接
 
Copyright 2001-2010, www.comprg.com.cn, All Rights Reserved
京ICP备14022230号-1,电话/传真:010-82561037 82561614 ,Mail:gaojian@comprg.com.cn
地址:北京市海淀区远大路20号宝蓝大厦E座704,邮编:100089