我們一起聊聊重新安排行程！
這也可以用回溯法?其實深搜和回溯也是相輔相成的，畢竟都用遞歸。
給定一個機票的字符串二維數(shù)組 [from, to]，子數(shù)組中的兩個成員分別表示飛機出發(fā)和降落的機場地點，對該行程進行重新規(guī)劃排序。所有這些機票都屬于一個從 JFK(肯尼迪國際機場)出發(fā)的先生，所以該行程必須從 JFK 開始。
提示：
- 如果存在多種有效的行程，請你按字符自然排序返回最小的行程組合。例如，行程 ["JFK", "LGA"] 與 ["JFK", "LGB"] 相比就更小，排序更靠前
- 所有的機場都用三個大寫字母表示(機場代碼)。
- 假定所有機票至少存在一種合理的行程。
- 所有的機票必須都用一次 且 只能用一次。
示例 1：
- 輸入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
- 輸出：["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2：
- 輸入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
- 輸出：["JFK","ATL","JFK","SFO","ATL","SFO"]
- 解釋：另一種有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
思路
這道題目還是很難的，之前我們用回溯法解決了如下問題：組合問題，分割問題，子集問題，排列問題。
直覺上來看 這道題和回溯法沒有什么關(guān)系，更像是圖論中的深度優(yōu)先搜索。
實際上確實是深搜，但這是深搜中使用了回溯的例子，在查找路徑的時候，如果不回溯，怎么能查到目標路徑呢。
所以我傾向于說本題應(yīng)該使用回溯法，那么我也用回溯法的思路來講解本題，其實深搜一般都使用了回溯法的思路，在圖論系列中我會再詳細講解深搜。
這里就是先給大家拓展一下，原來回溯法還可以這么玩!
這道題目有幾個難點：
- 一個行程中，如果航班處理不好容易變成一個圈，成為死循環(huán)
- 有多種解法，字母序靠前排在前面，讓很多同學(xué)望而退步，如何該記錄映射關(guān)系呢 ?
- 使用回溯法(也可以說深搜) 的話，那么終止條件是什么呢?
- 搜索的過程中，如何遍歷一個機場所對應(yīng)的所有機場。
針對以上問題我來逐一解答!
如何理解死循環(huán)
對于死循環(huán)，我來舉一個有重復(fù)機場的例子：
重新安排行程
為什么要舉這個例子呢，就是告訴大家，出發(fā)機場和到達機場也會重復(fù)的，如果在解題的過程中沒有對集合元素處理好，就會死循環(huán)。
該記錄映射關(guān)系
有多種解法，字母序靠前排在前面，讓很多同學(xué)望而退步，如何該記錄映射關(guān)系呢 ?
一個機場映射多個機場，機場之間要靠字母序排列，一個機場映射多個機場，可以使用std::unordered_map，如果讓多個機場之間再有順序的話，就是用std::map 或者std::multimap 或者 std::multiset。
如果對map 和 set 的實現(xiàn)機制不太了解，也不清楚為什么 map、multimap就是有序的同學(xué)，可以看這篇文章關(guān)于哈希表，你該了解這些!。
這樣存放映射關(guān)系可以定義為 unordered_map
含義如下：
這兩個結(jié)構(gòu)，我選擇了后者，因為如果使用unordered_map
再說一下為什么一定要增刪元素呢，正如開篇我給出的圖中所示，出發(fā)機場和到達機場是會重復(fù)的，搜索的過程沒及時刪除目的機場就會死循環(huán)。
所以搜索的過程中就是要不斷的刪multiset里的元素，那么推薦使用unordered_map
在遍歷 unordered_map<出發(fā)機場, map<到達機場, 航班次數(shù)>> targets的過程中，可以使用"航班次數(shù)"這個字段的數(shù)字做相應(yīng)的增減，來標記到達機場是否使用過了。
如果“航班次數(shù)”大于零，說明目的地還可以飛，如果如果“航班次數(shù)”等于零說明目的地不能飛了，而不用對集合做刪除元素或者增加元素的操作。
相當于說我不刪，我就做一個標記!
回溯法
這道題目我使用回溯法，那么下面按照我總結(jié)的回溯模板來：
- void backtracking(參數(shù)) {
- if (終止條件) {
- 存放結(jié)果;
- return;
- }
- for (選擇：本層集合中元素（樹中節(jié)點孩子的數(shù)量就是集合的大?。? {
- 處理節(jié)點;
- backtracking(路徑，選擇列表); // 遞歸
- 回溯，撤銷處理結(jié)果
- }
- }
本題以輸入：[["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]為例，抽象為樹形結(jié)構(gòu)如下：
.重新安排行程1
開始回溯三部曲講解：
- 遞歸函數(shù)參數(shù)
在講解映射關(guān)系的時候，已經(jīng)講過了，使用unordered_map
當然把參數(shù)放進函數(shù)里傳進去也是可以的，我是盡量控制函數(shù)里參數(shù)的長度。
參數(shù)里還需要ticketNum，表示有多少個航班(終止條件會用上)。
代碼如下：
- // unordered_map<出發(fā)機場, map<到達機場, 航班次數(shù)>> targets
- unordered_map<string, map<string, int>> targets;
- bool backtracking(int ticketNum, vector<string>& result) {
注意函數(shù)返回值我用的是bool!
我們之前講解回溯算法的時候，一般函數(shù)返回值都是void，這次為什么是bool呢?
因為我們只需要找到一個行程，就是在樹形結(jié)構(gòu)中唯一的一條通向葉子節(jié)點的路線，如圖：
重新安排行程1
所以找到了這個葉子節(jié)點了直接返回，這個遞歸函數(shù)的返回值問題我們在講解二叉樹的系列的時候，在這篇二叉樹：遞歸函數(shù)究竟什么時候需要返回值，什么時候不要返回值?詳細介紹過。
當然本題的targets和result都需要初始化，代碼如下：
- for (const vector<string>& vec : tickets) {
- targets[vec[0]][vec[1]]++; // 記錄映射關(guān)系
- }
- result.push_back("JFK"); // 起始機場
- 遞歸終止條件
拿題目中的示例為例，輸入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] ，這是有4個航班，那么只要找出一種行程，行程里的機場個數(shù)是5就可以了。
所以終止條件是：我們回溯遍歷的過程中，遇到的機場個數(shù)，如果達到了(航班數(shù)量+1)，那么我們就找到了一個行程，把所有航班串在一起了。
代碼如下：
- if (result.size() == ticketNum + 1) {
- return true;
- }
已經(jīng)看習(xí)慣回溯法代碼的同學(xué)，到葉子節(jié)點了習(xí)慣性的想要收集結(jié)果，但發(fā)現(xiàn)并不需要，本題的result相當于 回溯算法：求組合總和!中的path，也就是本題的result就是記錄路徑的(就一條)，在如下單層搜索的邏輯中result就添加元素了。
- 單層搜索的邏輯
回溯的過程中，如何遍歷一個機場所對應(yīng)的所有機場呢?
這里剛剛說過，在選擇映射函數(shù)的時候，不能選擇unordered_map
可以說本題既要找到一個對數(shù)據(jù)進行排序的容器，而且還要容易增刪元素，迭代器還不能失效。
所以我選擇了unordered_map
遍歷過程如下：
- for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
- if (target.second > 0 ) { // 記錄到達機場是否飛過了
- result.push_back(target.first);
- target.second--;
- if (backtracking(ticketNum, result)) return true;
- result.pop_back();
- target.second++;
- }
- }
可以看出 通過unordered_map
分析完畢，此時完整C++代碼如下：
- class Solution {
- private:
- // unordered_map<出發(fā)機場, map<到達機場, 航班次數(shù)>> targets
- unordered_map<string, map<string, int>> targets;
- bool backtracking(int ticketNum, vector<string>& result) {
- if (result.size() == ticketNum + 1) {
- return true;
- }
- for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
- if (target.second > 0 ) { // 記錄到達機場是否飛過了
- result.push_back(target.first);
- target.second--;
- if (backtracking(ticketNum, result)) return true;
- result.pop_back();
- target.second++;
- }
- }
- return false;
- }
- public:
- vector<string> findItinerary(vector<vector<string>>& tickets) {
- targets.clear();
- vector<string> result;
- for (const vector<string>& vec : tickets) {
- targets[vec[0]][vec[1]]++; // 記錄映射關(guān)系
- }
- result.push_back("JFK"); // 起始機場
- backtracking(tickets.size(), result);
- return result;
- }
- };
一波分析之后，可以看出我就是按照回溯算法的模板來的。
代碼中
- for (pair<const string, int>& target : targets[result[result.size() - 1]])
pair里要有const，因為map中的key是不可修改的，所以是pair
如果不加const，也可以復(fù)制一份pair，例如這么寫：
- for (pairtarget : targets[result[result.size() - 1]])
總結(jié)
本題其實可以算是一道hard的題目了，關(guān)于本題的難點我在文中已經(jīng)列出了。
如果單純的回溯搜索(深搜)并不難，難還難在容器的選擇和使用上。
本題其實是一道深度優(yōu)先搜索的題目，但是我完全使用回溯法的思路來講解這道題題目，算是給大家拓展一下思維方式，其實深搜和回溯也是分不開的，畢竟最終都是用遞歸。
如果最終代碼，發(fā)現(xiàn)照著回溯法模板畫的話好像也能畫出來，但難就難如何知道可以使用回溯，以及如果套進去，所以我再寫了這么長的一篇來詳細講解。
