国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

332. Reconstruct Itinerary

greatwhole / 1301人閱讀

摘要:題目解答都是用來解,一個用一個用來實現深度優先搜索,搜索到一個城市只是的時候即沒有出度的時候,把這個記入中去,因為它肯定是最后到達的城市,然后依次向前類推的要求在存入的時候就用先存好先進去的說明是出發城市,那么最先出發的城市最后出來

題目:
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.

解答:
都是用DFS來解,一個用recursion, 一個用stack來實現:
Recursion version:

public void dfs(String departure, Map> graph, List result) {
    //深度優先搜索,搜索到一個城市只是arrival city的時候(即沒有出度的時候,把這個city記入list中去,因為它肯定是最后到達的城市,然后依次向前類推
    PriorityQueue arrivals = graph.get(departure);
    while (arrivals != null && !arrivals.isEmpty()) {
        dfs(arrivals.poll(), graph, result);
    }
    result.add(0, departure);
}

public List findItinerary(String[][] tickets) {
    List result = new ArrayList();
    //lexical order的要求在存入graph的時候就用priority queue先存好
    Map> graph = new HashMap<>();
    for (String[] iter : tickets) {
        graph.putIfAbsent(iter[0], new PriorityQueue());
        graph.get(iter[0]).add(iter[1]);
    }
    
    dfs("JFK", graph, result);
    return result;
}

Stack version:

public List findItinerary(String[][] tickets) {
    List result = new ArrayList();
    Map> graph = new HashMap();
    for (String[] iter : tickets) {
        graph.putIfAbsent(iter[0], new PriorityQueue());
        graph.get(iter[0]).add(iter[1]);
    }
    
    Stack stack = new Stack();
    stack.push("JFK");
    while (!stack.isEmpty()) {
        while (graph.containsKey(stack.peek()) && !graph.get(stack.peek()).isEmpty()) {
        //先進去的說明是出發城市,那么最先出發的城市最后出來
            stack.push(graph.get(stack.peek()).poll());
        }
        result.add(0, stack.pop());
    }
    return result;
}

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

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64923.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 評論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 評論0 收藏0
  • leetcode423. Reconstruct Original Digits from Engl

    摘要:如對應的英文表達為并繼續亂序成。要求輸入亂序的英文表達式,找出其中包含的所有的數字,并按照從小到大輸出。思路和代碼首先將數字和英文表示列出來粗略一看,我們知道有許多字母只在一個英文數字中出現,比如只出現在中。 題目要求 Given a non-empty string containing an out-of-order English representation of digits...

    kviccn 評論0 收藏0
  • 基于Keras實現加密卷積神經網絡

    摘要:奧胡斯大學密碼學機器學習工程師介紹了如何實現基于加密數據進行訓練和預測的卷積神經網絡。通過卷積神經網絡分析圖像在最近幾年極為流行,因為在圖像相關任務上的表現超過了其他許多方法。 奧胡斯大學密碼學PhD、Datadog機器學習工程師Morten Dahl介紹了如何實現基于加密數據進行訓練和預測的卷積神經網絡。TL;DR 我們選取了一個經典的CNN深度學習模型,經過一系列步驟的改造,使其得以基于...

    fjcgreat 評論0 收藏0
  • 【問題】從一長串數字中找到重復多次的三個數字

    摘要:問題描述假設給定一個很長的數字,比如精確到萬位,找到其中重復出現相鄰三個數字。最后我們只要把新序列里統計值大于的打印出來即可。我們可以用更加優雅的方式來呈現以上算法,簡潔但不簡單。以上便是上原題的最佳答案。 問題描述 https://stackoverflow.com/que... 假設給定一個很長的數字,比如PI精確到100萬位,找到其中重復出現相鄰三個數字。比如給定的數字是1233...

    afishhhhh 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<