LeetCode332. 重新安排行程

题目

分析

https://mp.weixin.qq.com/s/3kmbS4qDsa6bkyxR92XCTA

代码

 1 class Solution {
 2 public:
 3     unordered_map<string,map<string,int>>tar;//起点、<终点,次数>
 4     bool backtracking(vector<string> &res,int ticketNum){
 5         if(res.size() == ticketNum + 1){
 6             return true;
 7         }
 8         for(pair<const string,int> &target : tar[res[res.size()-1]]){
 9             if(target.second > 0){
10                 res.push_back(target.first);
11                 target.second--;
12                 if(backtracking(res,ticketNum)) return true;
13                 res.pop_back();
14                 target.second++;
15             }
16         }
17     return false;
18     }
19     vector<string> findItinerary(vector<vector<string>>& tickets) {
20         vector<string>res;
21         for(auto it : tickets){
22             tar[it[0]][it[1]]++;
23         }
24         res.push_back("JFK");
25         backtracking(res,tickets.size());
26         return res;
27     }
28 };

这个问题其实和上周周赛那个题一样，都可以看成无向树给出了边，返回遍历结果。

LeetCode332. 重新安排行程

题目

分析

代码

1743. 从相邻元素对还原数组