文章目录
- 一、题目
- 二、解法
- 三、完整代码
所有的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
