题目 给定一个机票的字符串二维数组 [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 版权声明:本文为博主原创文章,转载请附上博文链接!
|