给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 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"] ，但是它字典排序更大更靠后。
思路：
直觉上来看 这道题和回溯法没有什么关系，更像是图论中的深度优先搜索。
实际上确实是深搜，但这是深搜中使用了回溯的例子，在查找路径的时候，如果不回溯，怎么能查到目标路径呢。
这道题目有几个难点：
- 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
- 有多种解法，字母序靠前排在前面，如何该记录映射关系呢 ？
- 使用回溯法 的话，那么终止条件是什么呢？
- 搜索的过程中，如何遍历一个机场所对应的所有机场。
残念です，第一次做的时候做错了，当时的思路是先把所有的路线情况写出来，相邻重复的机场（即终点和出发点）去重留一个，当路径元素数量和tickets.size()+1相等的时候返回，之后做排序，排第一的就是最终答案。
代码如下：
class Solution {
private:
vector<vector<string>> fakeRes;
vector<string> realRes;
vector<string> path;
int size;
void backtracking(vector<vector<string>>& tickets, vector<bool> used) {
if (path.size() == tickets.size() * 2) {
fakeRes.push_back(path);
}
for (int i = 0; i < tickets.size(); i++) {
if (used[i])
continue;
vector<string> Ticket = tickets[i];
path.push_back(Ticket[0]);
path.push_back(Ticket[1]);
used[i] = 1;
backtracking(tickets, used);
path.pop_back();
path.pop_back();
used[i] = 0;
}
}
vector<string> resort(vector<vector<string>>& vecs) {
vector<string> result;
for (vector<string>& vec : vecs) {
sort(vec.begin() + 1, vec.end());
}
result = vecs[0];
return result;
}
void resolve(vector<vector<string>>& res) {
vector<vector<string>> vec_res;
for (int i = 0; i < fakeRes.size(); i++) {
vector<string> cur = fakeRes[i];
for (int j = 1; j < cur.size(); j++) {
if (cur[j - 1] == cur[j]) {
cur.erase(cur.begin() + j);
j--;
}
}
if (cur.size() == size + 1) {
vec_res.push_back(cur);
}
}
realRes = resort(vec_res);
}
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
size = tickets.size();
vector<bool> used(tickets.size(), 0);
backtracking(tickets, used);
resolve(fakeRes);
return realRes;
}
};
但这个代码行不通。
目前很接近答案了，但没调试出来，相信后人的智慧！
这题正确的思路：一个机场映射多个机场，机场之间要靠字母序排列，一个机场映射多个机场，可以使用std::unordered_map，如果让多个机场之间再有顺序的话，就是用std::map 或者std::multimap 或者 std::multiset。
这样存放映射关系可以定义为 unordered_map<string, multiset<string>> targets 或者 unordered_map<string, map<string, int>> targets。
含义是：unordered_map<出发机场, map<到达机场, 航班次数>> targets。
还有一个重点是如何遍历出发机场：用到了
for (pair<const string, int>& target : targets[result[result.size() - 1]])其中result[result.size()-1]]就是当前所在机场（出发机场），每次到达把到达机场加入result，这样result[result.size()-1]]就是下一次的出发机场了。
代码如下：
class Solution {
private:
// unordered_map<出发机场, map<到达机场, 航班次数>> 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]]++; // 记录映射关系
}
result.push_back("JFK"); // 起始机场
backtracking(tickets.size(), result);
return result;
}
};
暂无评论