回溯算法——LeetCode332 重新安排行程

题目

力扣题目链接

思路

332.重写安排行程

代码

class Solution {
private:unordered_map<string, map<string, int>> targets;bool backtracking(int ticketNum, vector<string>& res) {if (res.size() == ticketNum + 1) {return true;}// 这里为什么要const，为什么要&，看卡哥解析// 写auto的话，也要写成auto&for (pair<const string, int>& target : targets[res[res.size() - 1]]) {if (target.second > 0) {res.push_back(target.first);target.second--;if (backtracking(ticketNum, res)) {return true;}res.pop_back();target.second++;}}return false;}public:vector<string> findItinerary(vector<vector<string>>& tickets) {targets.clear();vector<string> res;for (const vector<string>& vec : tickets) {targets[vec[0]][vec[1]]++;}res.push_back("JFK");backtracking(tickets.size(), res);return res;}
};