[LeetCode] Reconstruct Itinerary

jubincn 发布于2019-08-14 14:02 / 3161人阅读

摘要：来自大神的解答，只能膜拜。题目确定了至少有一条的行程不存在分支情况，一定有相同的最终目的地，而且对于多条的行程，要选取字母顺序较小的一条。

Problem

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 string. 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"].

Example 2:

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].

Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Note

来自LC大神@dietpepsi的解答，只能膜拜。
题目确定了至少有一条valid的行程（不存在分支情况，一定有相同的最终目的地），而且对于多条valid的行程，要选取字母顺序较小的一条。重构的行程地点一定是有序的，
所以，使用深度优先搜索，根据departure找到arrivals集合，并利用PriorityQueue对本航段的arrivals进行字母顺序排列，再将排列后的元素顺序取出作为departure，继续DFS，然后一层一层从内而外地将起点departure放入path的首位。

HashMap和LinkedList的两个关键用法如下：

putIfAbsent Method Detail:

V putIfAbsent(K key, V value)

If the specified key is not already associated with a value, associate it with the given value. This is equivalent to

if (!map.containsKey(key))
       return map.put(key, value);
   else
       return map.get(key);

except that the action is performed atomically.

Parameters:

key - key with which the specified value is to be associated
value - value to be associated with the specified key

Returns:

the previous value associated with the specified key, or null if there was no mapping for the key. (A null return can also indicate that the map previously associated null with the key, if the implementation supports null values.)

addFirst

public void addFirst(E e)

Inserts the specified element at the beginning of this list.

Specified by:

addFirst in interface Deque

Parameters:

e - the element to add

Solution

public class Solution {
    Map> flights = new HashMap();
    LinkedList path = new LinkedList();
    public List findItinerary(String[][] tickets) {
        for (String[] oneway: tickets) {
            flights.putIfAbsent(oneway[0], new PriorityQueue());
            flights.get(oneway[0]).add(oneway[1]);
        }
        dfs("JFK");
        return path;
    }
    public void dfs(String departure) {
        PriorityQueue arrivals = flights.get(departure);
        while (arrivals != null && !arrivals.isEmpty()) dfs(arrivals.poll());
        path.addFirst(departure);
    }
}

云服务器私有云 Itinerary Reconstruct LeetCode LeetCode_String

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

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

Leetcode[332] Reconstruct Itinerary

摘要：复杂度思路重建，应为要按进行排序，所以用来决定下一个要出去的值。 Leetcode[332] Reconstruct Itinerary Given a list of airline tickets represented by pairs of departure andarrival airports [from, to], reconstruct the itinerary ...

Flands 2019-08-14 15:57 评论0 收藏0
332. Reconstruct Itinerary

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

greatwhole 2019-08-14 14:17 评论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