算法（回溯）-重新安排行程
本代码及其相关思路来自：https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html#%E6%80%9D%E8%B7%AF
即代码随想录的carl哥那里，我主要是进行相关学习，并进行对应总结。
题目要求：
https://leetcode.cn/problems/reconstruct-itinerary/description/
题目解析：
首先该题，主要使用了回溯法，其实核心还是深度搜索算法。
根据该题描述，乘客的航班要求是从JFK出发，把给出的每一个航班，即，每一个数组元素都遍历走一遍。
比如示例1：
首先选择JFK，然后JFK可以到达的地方有MUC，且只有MUC，所以选择MUC，接着MUC可以去的地方只有LHR，则选择LHR，以此类推，往后最后得到相应结果。
注意：题目要求只选择一条通路即可。所以在回溯遍历的终止条件中，我们使用result.size()==航班数+1，则符合我们的通路要求。
代码分析：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
private:
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;
}
};
|
上述代码分析如下：
1
| unordered_map<string, map<string, int>> targets;
|
该map映射主要用来存放对应一个出发地，及其对应的所有目的地的信息及其剩余还可以乘坐的航班次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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;
}
|
上述为回溯算法主体部分。
回溯函数的参数为总的航班数目，当前的结果通路result;
终止条件为航班数+1等于当前result的数目，即可。
循环体：即对应的回溯遍历树的同树层，判断该航班是否被用完了，然后将当前地点加入result，该航班的num-1，注意要引用，因为这里需要操作targets的数据，如果target不引用targets，那么对应的数据无法改变，在深层递归的时候就会出现错误。然后就是判断当前路径及其子路径是否符合条件，并进行深度搜索，然后回溯，最终继续循环该层的其他航班地点。
1
2
3
4
5
6
7
8
9
10
| 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;
}
|
主函数体，首先将所有票务信息存入targets,然后记录初始机场，进行回溯，得到答案。
上述就是该题的所有思路及其相关题解代码分析。
