算法(回溯)-重新安排行程
本代码及其相关思路来自: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,然后记录初始机场,进行回溯,得到答案。
上述就是该题的所有思路及其相关题解代码分析。