九章演算法 | Google面試題 : 路線重現

01-26

撰文 | JZ

專欄 | 九章演算法

題目描述

某次旅行後小九留下了若干張飛機票，每張飛機票上寫有出發和到達的機場名。他出發的機場是「JFK」，他希望知道自己旅行時的準確路線。

數據保證有解。當有多組解時輸出字典序最小的一組。

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

分析解答

根據題目要求，一種貪心加深度優先搜索的方法是：從JFK機場出發，每次都選擇一個可以到達的且字典序最小的機場，進行下一步的搜索。搜索的終止條件為所有的飛機票都使用完畢。這種暴力搜索演算法理論上是可行的，但時間複雜度是指數級別的。

此題有一種更好的做法，把機場想像成點，飛機票想像成有向邊，問題就轉化成了在一個有向圖中求一條經過所有邊的路徑。求歐拉路徑有一種O(M)(M為邊數)的Fleury演算法：首先深度優先搜索遍歷整個圖，標記已經遍歷過的邊不再遍歷；當一個點無法再經過未遍歷的邊到達其他點時把該點加入棧中；最後把棧中序列輸出得到歐拉路徑。

簡單證明如下：首先定義割邊，去掉該邊原圖不連通則該邊為割邊；在搜索歐拉路徑的過程中一旦遇到割邊就意味著當前的搜索路徑需要改進，即提前經過其他某一聯通子圖內的邊。回溯添加節點的方法可以保證割邊一定最先加入棧，也就是出現在歐拉路徑的最後，因此可以通過一次深度優先搜索得到完整的歐拉路徑。

參考代碼

參考答案鏈接

面試官角度分析

本題使用的最優演算法求圖歐拉路徑演算法是圖論中的經典演算法。但是對於普通求職者來說，要求此演算法在面試中解出是不合理的。這個題對於大部分人來說，只需要做出暴力dfs的演算法就可以拿到hire了。做出歐拉路徑的做法自然是strong hire。但是如果你沒有太多時間，建議不要花太多時間學習該演算法。介於此題是來自Google，因此根據筆者經驗，一般只給簡歷上有競賽經歷的人來進行面試。

LintCode 相關練習

Word ladder ii