[LeetCode] Reconstruct Itinerary

jubincn 發布于2019-08-14 14:02 / 3256人閱讀

摘要：來自大神的解答，只能膜拜。題目確定了至少有一條的行程不存在分支情況，一定有相同的最終目的地，而且對于多條的行程，要選取字母順序較小的一條。

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);
    }
}

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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