Leetcode[332] Reconstruct Itinerary

Flands 发布于2019-08-14 15:57 / 3458人阅读

摘要：复杂度思路重建，应为要按进行排序，所以用来决定下一个要出去的值。

Leetcode[332] Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and
arrival airports [from, to], reconstruct the itinerary in order. All
of the tickets belong to a man who departs from JFK. Thus, the
itinerary must begin with JFK.
Note: If there are multiple valid itineraries, you should return the
itinerary that has the smallest lexical order when read as a single
For example, the itinerary

["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
All airports are represented by three capital letters (IATA code). You
may assume all tickets form at least one valid itinerary.
Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

DFS + Topological Sort

复杂度
O(N), O(N)

思路
重建graph，应为要按lexical order进行排序，所以用priorityqueue来决定下一个要poll出去的值。

代码

public List findItinerary(String[][] tickets) {
    HashMap> map = new HashMap<>();
    LinkedList res = new LinkedList<>();
    for(int i = 0; i < tickets.length; i ++) {
        String key = tickets[i][0];
        if(map.get(key) == null) {
            map.put(key, new PriorityQueue());
        }
        map.get(key).offer(tickets[i][1]);
    }
    //
    Stack stack = new Stack<>();
    stack.push("JFK");
    while(!stack.isEmpty()) {
        String cur = stack.peek();
        if(map.containsKey(cur) && map.get(cur).size() > 0) {
            stack.push(map.get(cur).poll());
        }
        else {
            res.addFirst(stack.pop());
        }
    }
    return res;
}

云服务器 GPU云服务器 Itinerary Reconstruct LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66138.html

332. Reconstruct Itinerary

摘要：题目解答都是用来解，一个用一个用来实现深度优先搜索，搜索到一个城市只是的时候即没有出度的时候，把这个记入中去，因为它肯定是最后到达的城市，然后依次向前类推的要求在存入的时候就用先存好先进去的说明是出发城市，那么最先出发的城市最后出来题目：Given a list of airline tickets represented by pairs of departure and arri...

greatwhole 2019-08-14 14:17 评论0 收藏0
[LeetCode] Reconstruct Itinerary

摘要：来自大神的解答，只能膜拜。题目确定了至少有一条的行程不存在分支情况，一定有相同的最终目的地，而且对于多条的行程，要选取字母顺序较小的一条。 Problem Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the i...

jubincn 2019-08-14 14:02 评论0 收藏0
leetcode423. Reconstruct Original Digits from Engl

摘要：如对应的英文表达为并继续乱序成。要求输入乱序的英文表达式，找出其中包含的所有的数字，并按照从小到大输出。思路和代码首先将数字和英文表示列出来粗略一看，我们知道有许多字母只在一个英文数字中出现，比如只出现在中。题目要求 Given a non-empty string containing an out-of-order English representation of digits...

kviccn 2019-08-16 16:49 评论0 收藏0
leetcode406. Queue Reconstruction by Height

摘要：题目要求假设有一组人站成一堆，每个人都记录下了自己的高度，以及在自己前面有多少个不比自己矮的人。现在请按照这个信息将这组人放在队列中正确的位置上并返回。但是这样解决其实复杂化了问题。即越大，则该同等高度的人一定在另一个同等高度的人后面。题目要求 Suppose you have a random list of people standing in a queue. Each per...

morgan 2019-08-16 15:42 评论0 收藏0
[LintCode/LeetCode] Binary Tree Serialization

摘要：这里要注意的是的用法。所以记住，用可以从自动分离出数组。跳过第一个元素并放入数组最快捷语句建立的用意记录处理过的结点并按处理所有结点和自己的连接下面先通过判断，再修改的符号的顺序，十分巧妙更轻便的解法 Problem Design an algorithm and write code to serialize and deserialize a binary tree. Writin...

keithyau 2019-08-14 15:12 评论0 收藏0