重新安排行程

重新安排行程

leetcode 332

本题题意为：给定一个n个点m条边的图，从指定的顶点出发，经过所有的边恰好一次，使得路径的字典序最小。

如何处理死循环：及时删除目的机场，利用回溯的终止条件，找到一个合理的行程即可。

含字典序的映射关系：一个机场映射多个机场，且机场之间依靠字典序排序，利用

unordered_map<string, map<string,int>>targets
//unordered_map<出发机场，map<到达机场，航班次数>>
//利用int型的航班次数记录，通过增减来标记机票是否使用过。

整个题目的树形结构如图。

完整代码为：

 class Solution{private://记录出发机场，到达机场还有航班次数的映射关系unordered_map<string,map<string,int>>targets;bool backtrack(int ticketsNum, vector<string>& result){//返回值类型为bool,因为只需要找到一个行程//路径长度等于机票数量+1if(result.size()==ticketsNum+1){return true;}//引用&target,单纯复制的话就无法记录结果for(auto& target:targets[result[result.size()-1]]){if(target.second > 0){//判断是否还有机票result.push_back(target.first);target.second--;if(backtrack(ticketsNum, result)) return true;result.pop_back();target.second++;}}return false;}public:vector<string> findItinerary(vector<vector<string>>& tickets){tragets.clear();vector<string> result;for(const auto& vec:tickets){targets[vec[0]][vec[1]]++;//记录映射关系}result.push_back("JFK");backtrack(tickets.size(),result);return result;}};