所有的LeetCode題解索引，可以看這篇文章——【算法和數據結構】LeetCode題解。

一、題目

二、解法

??思路分析：本題比較屬于困難題目，難點在于完成機票、出發機場和到達機場之間的映射關系，再一個難點就是在所有結果當中選擇字典排序靠前的結果。為解決以上問題，本題選擇unordered_map<string, map<string, int>>作為映射數組，第一個出發機場是JFK無需排序，但是到達機場需要排序，選擇map，它可以根據字典自動的進行字典排序。構造一個unordered_map<string, map<string, int>> targets數組，分別代表 <出發機場， <到達機場， 航班次數>>。關于hash表的有關內容，可以看哈希表理論基礎。至于映射關系，unordered_map可以像數組一樣用key值進行檢索操作。targets[ vec[0] ][ vec[1] ]就進行了兩次檢索。有關unordered_map的博客資料：C++中的unordered_map用法詳解。
??程序如下：

class Solution {
private:vector<string> result;vector<string> path;int nticket;unordered_map<string, map<string, int>> targets; // <出發機場， <到達機場， 航班次數>>， map會自動的字典排序(根據相同的出發機場就根據到達機場排序)bool backtracking(int nticket) {if (result.size() == nticket + 1) return true;	// 終止條件為結果數組長度=機票數加一for (pair<const string, int>& target : targets[result[result.size() - 1]]) { // 遍歷相同出發機場的到達機場，例如JFK有ATL，SFO兩種，依次迭代//cout << target.first << " " << target.second << endl;if (target.second > 0) {	// 記錄達到機場是否飛過， 大于0說明沒有飛過result.push_back(target.first);	// 處理節點target.second--;if (backtracking(nticket)) return true;	// 遞歸result.pop_back();				// 回溯target.second++;}}return false;}
public:vector<string> findItinerary(vector<vector<string>>& tickets) {nticket = tickets.size();for (const vector<string>& vec : tickets) {		// 用臨時變量vec遍歷tickets數組， 例如，第一次遍歷會將tickets[0]中的"JFK", "SFO"分別賦值給vec[0]和vec[1]// vec[0]和vec[1]分別代表出發機場和到達機場//cout << vec[0] << " " << vec[1] << endl;targets[ vec[0] ][ vec[1] ]++;	// 記錄映射關系，int 初始化時為0，++之后變為1// 查找key值為vec[0]的map value，在從map中查找key值為vec[1]的value， 令其value++}result.push_back("JFK");	// 起始機場backtracking(tickets.size());return result;}
};

三、完整代碼

# include <iostream>
# include <string>
# include <vector>
# include <map>
# include <unordered_map>
using namespace std;class Solution {
private:vector<string> result;vector<string> path;int nticket;unordered_map<string, map<string, int>> targets; // <出發機場， <到達機場， 航班次數>>， map會自動的字典排序(根據相同的出發機場就根據到達機場排序)bool backtracking(int nticket) {if (result.size() == nticket + 1) return true;	// 終止條件為結果數組長度=機票數加一for (pair<const string, int>& target : targets[result[result.size() - 1]]) { // 遍歷相同出發機場的到達機場，例如JFK有ATL，SFO兩種，依次迭代//cout << target.first << " " << target.second << endl;if (target.second > 0) {	// 記錄達到機場是否飛過， 大于0說明沒有飛過result.push_back(target.first);	// 處理節點target.second--;if (backtracking(nticket)) return true;	// 遞歸result.pop_back();				// 回溯target.second++;}}return false;}
public:vector<string> findItinerary(vector<vector<string>>& tickets) {nticket = tickets.size();for (const vector<string>& vec : tickets) {		// 用臨時變量vec遍歷tickets數組， 例如，第一次遍歷會將tickets[0]中的"JFK", "SFO"分別賦值給vec[0]和vec[1]// vec[0]和vec[1]分別代表出發機場和到達機場//cout << vec[0] << " " << vec[1] << endl;targets[ vec[0] ][ vec[1] ]++;	// 記錄映射關系，int 初始化時為0，++之后變為1// 查找key值為vec[0]的map value，在從map中查找key值為vec[1]的value， 令其value++}result.push_back("JFK");	// 起始機場backtracking(tickets.size());return result;}
};int main() {Solution s1;vector<vector<string>> tickets = { {"JFK", "SFO"}, {"JFK", "ATL"}, {"SFO", "ATL"}, {"ATL", "JFK"}, {"ATL", "SFO"} };vector<string> result = s1.findItinerary(tickets);for (vector<string>::iterator jt = result.begin(); jt != result.end(); jt++) {cout << *jt << " ";}system("pause");return 0;
}

end