Leetcode — 332. Reconstruct Itinerary (中文)

問題連結: https://leetcode.com/problems/reconstruct-itinerary/

給予一個tickets list, 裡面又包含很多list, 各list代表一張機票,會以[起點,終點]的方式呈現, 題目希望我們把這些機票排列成一個可行的路線, 且路線須從JFK開始, 目的地則看現有機票來決定, 並沒特別限制

Constraints:

1. 若現有機票可組成一個以上的路線, 則須回傳字母順序較小的路線, 比如路線["JFK", "LGA"] 的字母順序就比這個路線 ["JFK", "LGB"]會被優先決定
2. 所有機場代碼將為三個英文大寫字母 (IATA code).
3. 可假設給予的機票一定可以排成一個可行路線
4. 一張機票只能用一次, 每張機票都需用過

範例
Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

想法:

這題最難的地方在於- 當我們決定從機場A 出發後, 我們要怎麼確定我們選擇飛的機票是正確的? 會不會我們按照這張機票飛後 結果就遇到死路, 飛不出機場B害我們無法使用我們其他的機票?

因為給予的變數型態是list, 有點難一目了然的知道我們有哪些機票選擇, 讓我們試著把機票們畫成一個有向圖

假設我們的機票是這些 [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]

turn tickets into a directed graph

從圖中, 我們可以清楚的看見我們有兩張機票從JFK飛往不同的機場, 若我們只依照字母順序來選我們下個機場, 我們"有可能"就這樣結束我們的旅程, 而停在某個機場, 手上卻一堆我們不能用的機票, 我們有辦法避免這個情況嗎?
在這個例子中, 我們只能找到唯一的可行路線JFK -> NRT -> JFK -> KUL, 但我們到底要怎麼用演算法來找到這個路線?

想法:

當你看到我們把機場們跟機票飛行方向畫成有向圖的時候, 你可能想到了我們是不是可以用DFS來解這題, 但如果我們真的就用DFS來走訪節點的時候, 我們走訪節點順序就是 JFK -> KUL -> NRT, 因為在DFS中, 我們就是一碰到什麼節點, 就會拼命往碰到的那個點往下衝,直到衝到死路,才再回歸到原本的那個點, 去碰下一個還沒走訪過的節點

然而, 如果換個角度想, 我們不要找我們一開始起點JFK的下一個飛行點呢? 若我們改成找我們這個路線的最後一個機場, 是不是就簡單許多了? 更棒的是, 我們將會因為我們找到死路而開心, 因為這代表我們找到了我們的最後一個機場, 倒數第二個機場, 以此類推, 直到找到路線的第一個機場, 就組完我們的最終路線了

舉例來說, 若我們有這些機票: [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"],["NRT","ATL"],["ATL","NRT"],["SFO","LAX"],["LAX","SFO"],["KUL","LAX"],["LAX","TPE"]].

我們可以用下圖所示—

Example Graph

👷讓我們來看看我們怎麼用我們剛剛想到的方法 來幫我們找到我們最終的可行路線! 👇

我們的目標就是一直用掉可用的機票, 直到我們無法離開我們到達的機場, 且我們會優先選擇字母小的機場當作下個目的地機場

🔧Step 1.我們在步驟1的目標就是一直飛到我們不能再飛
從JFK開始, 我們將會走這樣的路線JFK -> KUL -> LAX -> SFO -> LAX -> TPE, 我們發現當我們飛到TPE的時候, 沒有從TPE飛出去的機票, 因此這將會是我們最終路線的最後一個機場
✈️Current itinerary: [TPE]

step 1

🔧Step 2. 在我們飛到TPE前的一個機場是在LAX, 因此現在我們要來看我們在LAX是否還可以飛去別的地方, 而因為我們已用掉LAX-SFO跟LAX-TPE的機票了, 我們也在LAX無別處可去, 因此LAX就會是我們倒數第二個的目的地機場
✈️Current itinerary: [LAX->TPE]

step 2

因為已知我們總共有九個機票, 找到兩個機場後代表我們已知我們在最終路線中會用的的第九個機票是LAX-TPE

🔧Step 3. 在飛到LAX之前的機場是SFO, 因此現在我們要來看我們在SFO是否還可以飛去別的地方, 而因為我們已用掉SFO-LAX的機票了, 我們在SFO無別處可去, 因此SFO就會是我們下個倒過來數的目的地機場
✈️Current itinerary: [SFO->LAX->TPE]

step 3

我們在最終路線中會用的的第八個機票是SFO-LAX

🔧Step 4. 在飛到SFO之前的機場是LAX, 因此現在我們要來看我們在LAX是否還可以飛去別的地方, 而因為我們已用掉所有從LAX起飛的機票了, 我們在LAX無別處可去, 因此LAX是我們下個倒過來數的目的地機場
✈️Current itinerary: [LAX->SFO->LAX->TPE]

Step 4

我們在最終路線中會用的的第七個機票是LAX-SFO

🔧Step 5. 在飛到LAX之前的機場是KUL, 因此現在我們要來看我們在KUL是否還可以飛去別的地方, 而因為我們已用掉所有從KUL起飛的機票了, 我們在KUL無別處可去, 因此KUL是我們下個倒過來數的目的地機場
✈️Current itinerary: [KUL->LAX->SFO->LAX->TPE]

step 5

我們在最終路線中會用的的第六個機票是KUL-LAX

🔧Step 6. 在飛到KUL之前的機場是JFK, 因此現在我們要來看我們在JFK是否還可以飛去別的地方, 我們發現我們還有機票還沒用, 因此我們決定用掉目前還能用的機票們, 我們一次飛 JFK -> NRT -> ATL -> NRT ->JFK, 而飛到JFK的時候我們已經沒有從JFK起飛的機票了, 我們在JFK無別處可去, 因此JFK是我們下個倒過來數的目的地機場
✈️Current itinerary: [JFK->KUL->LAX->SFO->LAX->TPE]

step 6

我們在最終路線中會用的的第五個機票是JFK-KUL

🔧Step 7. 在飛到JFK之前的機場是NRT, 因此現在我們要來看我們在NRT是否還可以飛去別的地方, 而因為我們已用掉所有從NRT起飛的機票了, 我們在NRT無別處可去, 因此NRT是我們下個倒過來數的目的地機場
✈️Current itinerary: [NRT->JFK->KUL->LAX->SFO->LAX->TPE]

step 7

我們在最終路線中會用的的第四個機票是NRT-JFK

🔧Step 8. 在飛到NRT之前的機場是ATL, 因此現在我們要來看我們在ATL是否還可以飛去別的地方, 而因為我們已用掉所有從ATL起飛的機票了, 我們在ATL無別處可去, 因此ATL是我們下個倒過來數的目的地機場
✈️Current itinerary: [ATL->NRT->JFK->KUL->LAX->SFO->LAX->TPE]

step 8

我們在最終路線中會用的的第三個機票是ATL-NRT

🔧Step 9. 在飛到ATL之前的機場是NRT, 因此現在我們要來看我們在NRT是否還可以飛去別的地方, 而因為我們已用掉所有從NRT起飛的機票了, 我們在NRT無別處可去, 因此NRT是我們下個倒過來數的目的地機場
✈️Current itinerary: [NRT->ATL->NRT->JFK->KUL->LAX->SFO->LAX->TPE]

step 9

我們在最終路線中會用的的第二個機票是NRT-ATL

🔧Step 10. 在飛到NRT之前的機場是JFK, 因此現在我們要來看我們在JFK是否還可以飛去別的地方, 而因為我們已用掉所有從JFK起飛的機票了, 我們在JFK無別處可去, 因此JFK是我們下個倒過來數的目的地機場, 也就是我們的起點機場
✈️Current itinerary: [JFK->NRT->ATL->NRT->JFK->KUL->LAX->SFO->LAX->TPE]

我們在最終路線中會用的的第一個機票是JFK-NRT

👷我們已找完所有機票 並完成排列這趟旅行的路線!

讓我們來看下面我們如何用上述方法來寫成程式 👇

程式邏輯:

一開始題目給的機票型態是list, 因此我們第一步就是先把我們的list轉換成有向圖, 我們將用一個Map 來存資料, 每個機場名字將都會有一個list來搭配, list裡面就存所有我們從這個機場可以飛到其他的機場名字 (所以有幾個從這個機場飛出去的機票, 就代表我們的list裡面的機場名字有幾個), 當我們存好每個機場的list後, 我們再將這些list裡面的機場名字用字母大小來排序

在我們創好我們的有向圖後 我們就可以真正開始我們的演算法了

從JFK開始, 我們將會盡量去用掉我們目前可以用的所有機票, 直到我們到了某個機場發現我們沒有從這個機場出發的機票了(也就是在map中 這個機場的list為空), 我們就會停下來, 把現在的機場加進我們最終的路程中
⚠️因此,我們將會用倒過來的方式來拼湊我們的最終路程, 因此每次把現在的機場加進最終路程時, 都是把機場加進現有路程的第一個位置

以下為4ms的程式碼, 贏過 99% —

public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, List<String>> map = new HashMap<>();
        for(List<String> ticket: tickets)
        {
            String start = ticket.get(0);
            String end = ticket.get(1);
            List<String> inner = map.getOrDefault(start, new ArrayList<>());
            inner.add(end);
            map.put(start,inner);
        }
        for(String s: map.keySet())
            Collections.sort(map.get(s));
        
        List<String> list = new ArrayList<>();
        helper(map,list,"JFK");
        
        return list;
    }
    public void helper(Map<String,List<String>> map, List<String> rst, String cur){
        List<String> nexts = map.get(cur);
        while(nexts!=null && nexts.size()>0)
        {
            String next = nexts.get(0);
            nexts.remove(0);
            helper(map,rst,next);
        }
        rst.add(0,cur);
    }

我們也可在Map中用PriorityQueue來幫我們存每個機場的下個飛行點, 因為是PriorityQueue, 機場都會自動存成字母排序, 我們也可以省下最後再用Collections.sort()來排序, 也可以省下用list.remove()的時間 (因為在Java, list.remove()需要花O(n)的時間; 而queue的移除元素只需花O(1))

public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> map = new HashMap<>();
        for(List<String> ticket: tickets)
        {
            String start = ticket.get(0);
            String end = ticket.get(1);
            PriorityQueue<String> inner = map.getOrDefault(start, new PriorityQueue<>());
            inner.offer(end);
            map.put(start,inner);
        }
        
        List<String> list = new ArrayList<>();
        helper(map,list,"JFK");
        
        return list;
    }
    public void helper(Map<String, PriorityQueue<String>> map, List<String> rst, String cur){
        PriorityQueue<String> nexts = map.get(cur);
        while(nexts!=null && !nexts.isEmpty())
        {
            String next = nexts.poll();
            helper(map,rst,next);
        }
        rst.add(0,cur);
    }