給你一份航線列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飛機出發(fā)和降落的機場地點。請你對該行程進行重新規(guī)劃排序。

所有這些機票都屬于一個從 JFK（肯尼迪國際機場）出發(fā)的先生，所以該行程必須從 JFK 開始。如果存在多種有效的行程，請你按字典排序返回最小的行程組合。

例如，行程 [“JFK”, “LGA”] 與 [“JFK”, “LGB”] 相比就更小，排序更靠前。
假定所有機票至少存在一種合理的行程。且所有的機票 必須都用一次 且 只能用一次。

示例 1：

輸入：tickets = [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]]
輸出：[“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]

示例 2：

輸入：tickets = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]
輸出：[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]
解釋：另一種有效的行程是 [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”] ，但是它字典排序更大更靠后。

提示：

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3 fromi 和 toi 由大寫英文字母組成
fromi != toi

這道題其實是一道深搜的題目，但是回溯實際上就是用到了深搜，這個題目中同樣也有回溯；

這個題目可能遇到的幾個主要問題及解析如下，

1，一個行程中，如果航班處理不好容易變成一個圈，成為死循環(huán)
為了避免這個情況，我們需要對每一個機場進行一個計數(shù)，走一次減一次，如果出現(xiàn)次數(shù)為0或小于0次，就說明走過了這個機場，就不能再走了，不然就會出現(xiàn)這個情況；

2，有多種解法，但是題目要字母序靠前排在前面，如何該記錄映射關系呢 ？
一個機場可以映射多個機場，所以可以用unordered_map容器，字母排序則需要一個map容器，這樣就可以通過出發(fā)的機場找到排序后的可以到達的機場了；

3，使用回溯法（也可以說深搜） 的話，那么終止條件是什么呢？
因為一開始一定會在JFK機場，然后通過的機場數(shù)就是所有的tickets數(shù)目，所以一旦走的航線數(shù)目等于tickets + 1時（這個1就是JFK起始機場）就可以結束；

4，搜索的過程中，如何遍歷一個機場所對應的所有機場？
這就需要對set和map非常非常熟悉了，這里選用的就是unordered_map容器和map容器，這里的映射關系如下：
unordered_map：
key：當前所處的機場（string）
value：當前所處的機場能到達所有機場（map）

map：
key：所能到達的機場（string）
value：所到達的機場出現(xiàn)次數(shù)（int）

所以這里就稍微復雜一點，我們代碼中定義為：unordered_map<string, map<string, int>> targets;

這就是主要會遇到的問題，代碼里還有詳細注釋，可以結合理解
代碼如下：

class Solution { private:// unordered_map<出發(fā)機場, map<到達機場, 航班次數(shù)>> targetsunordered_map<string, map<string, int>> targets;bool backTacking(int ticketSize, vector<string>& ans) {if (ans.size() == ticketSize + 1) {return true;}//這個for循環(huán)為了遍歷此時到達的機場所有的航班次數(shù)//targets[ans[ans.size - 1]]就是targets[此時到達的機場]//這時到達的機場可以說就是新的出發(fā)機場，就是看看能從這到哪些地方//這里的pair<const string, int>可以改成auto，但是為了方便理解，這里就寫了原格式for (pair<const string, int>& i : targets[ans[ans.size() - 1]]) {//如果此時到達的機場沒有來過，繼續(xù)執(zhí)行//如果此時到達的機場來過，即i.second <= 0，那么就直接跳過，防止出現(xiàn)死循環(huán)if (i.second > 0) {ans.push_back(i.first);i.second--;if (backTacking(ticketSize, ans)) return true;ans.pop_back();i.second++;}}return false;} public:vector<string> findItinerary(vector<vector<string>>& tickets) {vector<string> ans;//記錄每一個出發(fā)機場到所能到達的機場的航班次數(shù)for (auto i : tickets) {targets[i[0]][i[1]]++;}//起始行程必須從JFK開始ans.push_back("JFK");backTacking(tickets.size(), ans);return ans;} };

這道題對容器選擇和應用上是主要難點；

總結

以上是生活随笔為你收集整理的332. 重新安排行程（回溯算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。