FB面试原题:重新安排行程
LintCode 1288
重新安排行程
题目描述 给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 出发。 1.如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前。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"]。但是它自然排序更大更靠后。
解题思路
使用优先队列存储从一个机场出发可以到达的所有机场,再进行DFS找出答案
源代码
public classSolution{
public List<String> findItinerary(String[][] tickets) {
Map<String, PriorityQueue<String>> hashmap = new HashMap<String, PriorityQueue<String>>();
List<String> list = new ArrayList<String>();
String cur = "JFK";
int length = tickets.length;
for (int i = 0; i < length; i++) {
if (!hashmap.containsKey(tickets[i][0])) {
hashmap.put(tickets[i][0], new PriorityQueue<String>());
}
hashmap.get(tickets[i][0]).add(tickets[i][1]);
}
dfs(cur, hashmap, list);
Collections.reverse(list);
return list;
}
public void dfs(String cur, Map<String, PriorityQueue<String>> hashmap, List<String> list) {
while (hashmap.containsKey(cur) && !hashmap.get(cur).isEmpty()) {
dfs(hashmap.get(cur).poll(), hashmap, list);
}
list.add(cur);
}
}
查看完整代码,向左滑动
点击【阅读原文】,查看领扣原题。
阅读原文 关键词
数组
代码
行程
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。