【算法与数据结构】332、LeetCode重新安排行程

2023-12-15 13:14:32

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解

一、题目

在这里插入图片描述
在这里插入图片描述

二、解法

??思路分析:本题比较属于困难题目,难点在于完成机票、出发机场和到达机场之间的映射关系,再一个难点就是在所有结果当中选择字典排序靠前的结果。为解决以上问题,本题选择unordered_map<string, map<string, int>>作为映射数组,第一个出发机场是JFK无需排序,但是到达机场需要排序,选择map,它可以根据字典自动的进行字典排序。构造一个unordered_map<string, map<string, int>> targets数组,分别代表 <出发机场, <到达机场, 航班次数>>。关于hash表的有关内容,可以看哈希表理论基础。至于映射关系,unordered_map可以像数组一样用key值进行检索操作。targets[ vec[0] ][ vec[1] ]就进行了两次检索。有关unordered_map的博客资料:C++中的unordered_map用法详解
??程序如下

class Solution {
private:
	vector<string> result;
	vector<string> path;
	int nticket;
	unordered_map<string, map<string, int>> targets; // <出发机场, <到达机场, 航班次数>>, map会自动的字典排序(根据相同的出发机场就根据到达机场排序)
	bool backtracking(int nticket) {
		if (result.size() == nticket + 1) return true;	// 终止条件为结果数组长度=机票数加一
		for (pair<const string, int>& target : targets[result[result.size() - 1]]) { // 遍历相同出发机场的到达机场,例如JFK有ATL,SFO两种,依次迭代
			//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:
	vector<string> findItinerary(vector<vector<string>>& tickets) {
		nticket = tickets.size();
		for (const vector<string>& 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:
	vector<string> result;
	vector<string> path;
	int nticket;
	unordered_map<string, map<string, int>> targets; // <出发机场, <到达机场, 航班次数>>, map会自动的字典排序(根据相同的出发机场就根据到达机场排序)
	bool backtracking(int nticket) {
		if (result.size() == nticket + 1) return true;	// 终止条件为结果数组长度=机票数加一
		for (pair<const string, int>& target : targets[result[result.size() - 1]]) { // 遍历相同出发机场的到达机场,例如JFK有ATL,SFO两种,依次迭代
			//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:
	vector<string> findItinerary(vector<vector<string>>& tickets) {
		nticket = tickets.size();
		for (const vector<string>& 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;
	vector<vector<string>> tickets = { {"JFK", "SFO"}, {"JFK", "ATL"}, {"SFO", "ATL"}, {"ATL", "JFK"}, {"ATL", "SFO"} };
	vector<string> result = s1.findItinerary(tickets);
	for (vector<string>::iterator jt = result.begin(); jt != result.end(); jt++) {
		cout << *jt << " ";
	}
	system("pause");
	return 0;
}

end

文章来源:https://blog.csdn.net/qq_45765437/article/details/134921683
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。