代码随想录训练营Day30

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、重新安排行程

前言

提示：这里可以添加本文要记录的大概内容：

今天是跟着代码随想录刷题的第30天，主要是复习了回溯算法、重新安排形成、N皇后的内容。

提示：以下是本篇文章正文内容，下面案例可供参考

一、重新安排行程

重新安排行程
思路：就是建立一个双层map，unordered_map<string, map> targets，第一个string存出发点，第二个string存飞到的地方，和次数（如果没用就是一次），然后把tickets的东西全部放入这个双层map以后，开始从开头遍历这个map对应的内层，比如说开头是jfk，就开始找哪些是开头jfk开始飞的，找到以后，把jfk飞到的对应地方放到result里，然后result中对应的这个地方当做开头，此时要把次数减1，因为不能重复飞，再去找以这个为开头能飞的，比如说有多个，第一个先看看后续怎么样，如果整个的行程等于航班＋1就相当于是结束了，把结果放到result里直接返回就行了，如果找到这个起飞的地方没有能飞的了，就直接返回false，把之前的那步再复原，看看上一个作为起飞点有没有可以飞的其他地方，再去其他地方试试，直到能找到一个有航班+1的一个形成就可以了。
这道题的几个难点：

1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
2. 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
3. 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
4. 搜索的过程中，如何遍历一个机场所对应的所有机场。
5. 咱们的递归可以解决死循环的问题，因为用过的不能再用了。
6. 所以搜索的过程中就是要不断的删multiset里的元素，那么推荐使用unordered_map<string, map> targets。
   在遍历 unordered_map<出发机场, map> targets的过程中，可以使用”航班次数”这个字段的数字做相应的增减，来标记到达机场是否使用过了。
   如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。
7. 我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了。
8. 用递归加回溯来遍历。
   代码：

class Solution {  
private:  
// 定义一个私有成员变量，用于存储从出发机场到其对应到达机场及其航班次数的映射  
// unordered_map<出发机场, map>  
unordered_map<string, map<string, int>> targets;  
// 定义一个私有回溯函数，用于寻找从指定起始机场出发，经过所有给定航班的行程  
bool backtracking(int ticketNum, vector<string>& result) {  
// 如果结果列表的大小等于给定的航班数量加1（因为起始机场已经加入），说明找到了一个完整的行程  
if (result.size() == ticketNum + 1) {  
return true;  
}  
// 遍历从当前机场出发的所有航班  
for (pair<const string, int>& target : targets[result[result.size() - 1]]) {  
// 如果当前航班的次数大于0（即该航班还没有被完全使用）  
if (target.second > 0) {   
// 将当前航班的到达机场加入到结果列表中  
result.push_back(target.first);  
// 将当前航班的次数减1，表示已经使用了该航班  
target.second--;  
// 递归调用backtracking函数，继续寻找下一个航班  
if (backtracking(ticketNum, result)) return true;  
// 如果递归调用返回false，说明当前路径不可行，需要回溯  
// 将之前加入的航班到达机场从结果列表中移除  
result.pop_back();  
// 恢复之前航班的次数  
target.second++;  
}  
}  
// 如果所有从当前机场出发的航班都尝试过了，仍然没有找到完整的行程，返回false  
return false;  
}  
public:  
// 定义一个公共函数，用于找到从"JFK"出发，经过所有给定航班的行程  
vector<string> findItinerary(vector<vector<string>>& tickets) {  
// 清空targets映射，确保没有之前的航班信息  
targets.clear();  
// 定义一个结果列表，用于存储找到的行程  
vector<string> result;  
// 遍历所有给定的航班信息  
for (const vector<string>& vec : tickets) {  
// 将航班的出发机场和到达机场及其次数记录到targets映射中  
targets[vec[0]][vec[1]]++;  
}  
// 假设起始机场是"JFK"，将其加入到结果列表中  
result.push_back("JFK");  
// 调用backtracking函数来寻找一个有效的行程  
backtracking(tickets.size(), result);  
// 返回找到的行程  
return result;  
}  
};