宁波网站建设系统介绍,网站管理系统设置,河北保定网站建设,建筑模板怎么装文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;本题比较属于困难题目#xff0c;难点在于完成机票、出发机场和到达机场之间的映射关系#xff0c;再… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析本题比较属于困难题目难点在于完成机票、出发机场和到达机场之间的映射关系再一个难点就是在所有结果当中选择字典排序靠前的结果。为解决以上问题本题选择unordered_mapstring, mapstring, int作为映射数组第一个出发机场是JFK无需排序但是到达机场需要排序选择map它可以根据字典自动的进行字典排序。构造一个unordered_mapstring, mapstring, int targets数组分别代表 出发机场 到达机场 航班次数。关于hash表的有关内容可以看哈希表理论基础。至于映射关系unordered_map可以像数组一样用key值进行检索操作。targets[ vec[0] ][ vec[1] ]就进行了两次检索。有关unordered_map的博客资料C中的unordered_map用法详解。 程序如下
class Solution {
private:vectorstring result;vectorstring path;int nticket;unordered_mapstring, mapstring, int targets; // 出发机场 到达机场 航班次数 map会自动的字典排序(根据相同的出发机场就根据到达机场排序)bool backtracking(int nticket) {if (result.size() nticket 1) return true; // 终止条件为结果数组长度机票数加一for (pairconst string, int target : targets[result[result.size() - 1]]) { // 遍历相同出发机场的到达机场例如JFK有ATLSFO两种依次迭代//cout target.first target.second endl;if (target.second 0) { // 记录达到机场是否飞过 大于0说明没有飞过result.push_back(target.first); // 处理节点target.second--;if (backtracking(nticket)) return true; // 递归result.pop_back(); // 回溯target.second;}}return false;}
public:vectorstring findItinerary(vectorvectorstring tickets) {nticket tickets.size();for (const vectorstring vec : tickets) { // 用临时变量vec遍历tickets数组 例如第一次遍历会将tickets[0]中的JFK, SFO分别赋值给vec[0]和vec[1]// vec[0]和vec[1]分别代表出发机场和到达机场//cout vec[0] vec[1] endl;targets[ vec[0] ][ vec[1] ]; // 记录映射关系int 初始化时为0之后变为1// 查找key值为vec[0]的map value在从map中查找key值为vec[1]的value 令其value}result.push_back(JFK); // 起始机场backtracking(tickets.size());return result;}
};三、完整代码
# include iostream
# include string
# include vector
# include map
# include unordered_map
using namespace std;class Solution {
private:vectorstring result;vectorstring path;int nticket;unordered_mapstring, mapstring, int targets; // 出发机场 到达机场 航班次数 map会自动的字典排序(根据相同的出发机场就根据到达机场排序)bool backtracking(int nticket) {if (result.size() nticket 1) return true; // 终止条件为结果数组长度机票数加一for (pairconst string, int target : targets[result[result.size() - 1]]) { // 遍历相同出发机场的到达机场例如JFK有ATLSFO两种依次迭代//cout target.first target.second endl;if (target.second 0) { // 记录达到机场是否飞过 大于0说明没有飞过result.push_back(target.first); // 处理节点target.second--;if (backtracking(nticket)) return true; // 递归result.pop_back(); // 回溯target.second;}}return false;}
public:vectorstring findItinerary(vectorvectorstring tickets) {nticket tickets.size();for (const vectorstring vec : tickets) { // 用临时变量vec遍历tickets数组 例如第一次遍历会将tickets[0]中的JFK, SFO分别赋值给vec[0]和vec[1]// vec[0]和vec[1]分别代表出发机场和到达机场//cout vec[0] vec[1] endl;targets[ vec[0] ][ vec[1] ]; // 记录映射关系int 初始化时为0之后变为1// 查找key值为vec[0]的map value在从map中查找key值为vec[1]的value 令其value}result.push_back(JFK); // 起始机场backtracking(tickets.size());return result;}
};int main() {Solution s1;vectorvectorstring tickets { {JFK, SFO}, {JFK, ATL}, {SFO, ATL}, {ATL, JFK}, {ATL, SFO} };vectorstring result s1.findItinerary(tickets);for (vectorstring::iterator jt result.begin(); jt ! result.end(); jt) {cout *jt ;}system(pause);return 0;
}end
