成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LeetCode] Reconstruct Itinerary

jubincn / 3266人閱讀

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

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

來(lái)自LC大神@dietpepsi的解答，只能膜拜。
題目確定了至少有一條valid的行程（不存在分支情況，一定有相同的最終目的地），而且對(duì)于多條valid的行程，要選取字母順序較小的一條。重構(gòu)的行程地點(diǎn)一定是有序的，
所以，使用深度優(yōu)先搜索，根據(jù)departure找到arrivals集合，并利用PriorityQueue對(duì)本航段的arrivals進(jìn)行字母順序排列，再將排列后的元素順序取出作為departure，繼續(xù)DFS，然后一層一層從內(nèi)而外地將起點(diǎn)departure放入path的首位。

HashMap和LinkedList的兩個(gè)關(guān)鍵用法如下：

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

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64774.html

相關(guān)文章

  • Leetcode[332] Reconstruct Itinerary

    摘要：復(fù)雜度思路重建，應(yīng)為要按進(jìn)行排序，所以用來(lái)決定下一個(gè)要出去的值。 Leetcode[332] Reconstruct Itinerary Given a list of airline tickets represented by pairs of departure andarrival airports [from, to], reconstruct the itinerary ...

    Flands 評(píng)論0 收藏0

  • 332. Reconstruct Itinerary

    摘要：題目解答都是用來(lái)解，一個(gè)用一個(gè)用來(lái)實(shí)現(xiàn)深度優(yōu)先搜索，搜索到一個(gè)城市只是的時(shí)候即沒(méi)有出度的時(shí)候，把這個(gè)記入中去，因?yàn)樗隙ㄊ亲詈蟮竭_(dá)的城市，然后依次向前類推的要求在存入的時(shí)候就用先存好先進(jìn)去的說(shuō)明是出發(fā)城市，那么最先出發(fā)的城市最后出來(lái) 題目：Given a list of airline tickets represented by pairs of departure and arri...

    greatwhole 評(píng)論0 收藏0

  • leetcode423. Reconstruct Original Digits from Engl

    摘要：如對(duì)應(yīng)的英文表達(dá)為并繼續(xù)亂序成。要求輸入亂序的英文表達(dá)式，找出其中包含的所有的數(shù)字，并按照從小到大輸出。思路和代碼首先將數(shù)字和英文表示列出來(lái)粗略一看，我們知道有許多字母只在一個(gè)英文數(shù)字中出現(xiàn)，比如只出現(xiàn)在中。 題目要求 Given a non-empty string containing an out-of-order English representation of digits...

    kviccn 評(píng)論0 收藏0

  • leetcode406. Queue Reconstruction by Height

    摘要：題目要求假設(shè)有一組人站成一堆，每個(gè)人都記錄下了自己的高度，以及在自己前面有多少個(gè)不比自己矮的人?，F(xiàn)在請(qǐng)按照這個(gè)信息將這組人放在隊(duì)列中正確的位置上并返回。但是這樣解決其實(shí)復(fù)雜化了問(wèn)題。即越大，則該同等高度的人一定在另一個(gè)同等高度的人后面。 題目要求 Suppose you have a random list of people standing in a queue. Each per...

    morgan 評(píng)論0 收藏0

  • [LintCode/LeetCode] Binary Tree Serialization

    摘要：這里要注意的是的用法。所以記住，用可以從自動(dòng)分離出數(shù)組。跳過(guò)第一個(gè)元素并放入數(shù)組最快捷語(yǔ)句建立的用意記錄處理過(guò)的結(jié)點(diǎn)并按處理所有結(jié)點(diǎn)和自己的連接下面先通過(guò)判斷，再修改的符號(hào)的順序，十分巧妙更輕便的解法 Problem Design an algorithm and write code to serialize and deserialize a binary tree. Writin...

    keithyau 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<