重新安排行程

重新安排行程

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,因为只需要找到一个行程
        //路径长度等于机票数量+1
		if(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;
     }
 };