代码随想录训练营Day30
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、重新安排行程
前言
提示：这里可以添加本文要记录的大概内容：
今天是跟着代码随想录刷题的第30天，主要是复习了回溯算法、重新安排形成、N皇后的内容。
提示：以下是本篇文章正文内容，下面案例可供参考
一、重新安排行程
重新安排行程
思路：就是建立一个双层map，unordered_map<string, map<string, int>> targets，第一个string存出发点，第二个string存飞到的地方，和次数（如果没用就是一次），然后把tickets的东西全部放入这个双层map以后，开始从开头遍历这个map对应的内层，比如说开头是jfk，就开始找哪些是开头jfk开始飞的，找到以后，把jfk飞到的对应地方放到result里，然后result中对应的这个地方当做开头，此时要把次数减1，因为不能重复飞，再去找以这个为开头能飞的，比如说有多个，第一个先看看后续怎么样，如果整个的行程等于航班＋1就相当于是结束了，把结果放到result里直接返回就行了，如果找到这个起飞的地方没有能飞的了，就直接返回false，把之前的那步再复原，看看上一个作为起飞点有没有可以飞的其他地方，再去其他地方试试，直到能找到一个有航班+1的一个形成就可以了。
这道题的几个难点：
- 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
- 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
- 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
- 搜索的过程中，如何遍历一个机场所对应的所有机场。
- 咱们的递归可以解决死循环的问题，因为用过的不能再用了。
- 所以搜索的过程中就是要不断的删multiset里的元素，那么推荐使用unordered_map<string, map<string, int>> targets。
在遍历 unordered_map<出发机场, map<到达机场, 航班次数>> targets的过程中，可以使用"航班次数"这个字段的数字做相应的增减，来标记到达机场是否使用过了。
如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。 - 我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了。
- 用递归加回溯来遍历。
代码：
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; }
};