欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Reconstruct Itinerary 重新安排行程

程序员文章站 2022-03-04 19:01:16
...

给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 出发。

说明:

  1. 如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前
  2. 所有的机场都用三个大写字母表示(机场代码)。
  3. 假定所有机票至少存在一种合理的行程。

示例 1:

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]

示例 2:

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

思路:这道题可以用拓扑排序来做,参考这篇:Course Schedule 课程表,BFS,每次加入它的邻接点(邻接点按照字母顺序排序),然后对应该节点和邻接点的计数器减1(pair<currentVertex,neiborVertex> count),且总计数器减1,如果总计数器等于0,意味着所有边已经遍历完了,返回res,否则继续dfs。

参考代码:

class Solution {
public:
unordered_map<string, set<string>> make_graph(vector<pair<string, string>> tickets) {
	unordered_map<string, set<string>> res;
	for (auto p : tickets) {
		res[p.first].insert(p.second);
	}
	return res;
}
struct pair_hash {
	template <class T1, class T2>
	std::size_t operator () (const std::pair<T1, T2> &p) const{
		auto h1 = std::hash<T1>{}(p.first);
		auto h2 = std::hash<T2>{}(p.second);
		return h1 ^ h2;
	}
};
unordered_map<pair<string, string>, int, pair_hash> initial_hash_map(vector<pair<string, string>> tickets) {
	unordered_map<pair<string, string>, int, pair_hash> res;
	for (auto p : tickets) {
		pair<string, string> tmp = {p.first,p.second};
		res[tmp]++;
	}
	return res;
}
void dfs(unordered_map<string, set<string>> &graph, int n, vector<string> &res, unordered_map<pair<string, string>, int, pair_hash> memo,bool &flag) {
	if (n == 0) {
		flag = true;
		return;
	}
	for (auto set_node : graph[res.back()]) {
		if (memo[{res.back(), set_node}]!=0) {
			memo[{res.back(), set_node}]--;
			res.push_back(set_node);
			dfs(graph, n - 1, res, memo, flag);
			if (flag) return;
			res.pop_back();
			memo[{res.back(), set_node}]++;
		}
	}
}
vector<string> findItinerary(vector<pair<string, string>> tickets) {
	unordered_map<string,set<string>> graph = make_graph(tickets);
	unordered_map<pair<string, string>,int, pair_hash> memo = initial_hash_map(tickets);
	vector<string> res;
	res.push_back("JFK");
	bool flag = false;
	dfs(graph,tickets.size(),res,memo,flag);
	return res;
}
};

思路二:其实这道题是Eulerian path问题,即能否一笔把图的所有边连起来,前提是所有边只能访问一次。算法是

Hierholzer's algorithm解法

参考代码:

class Solution {
public:
void findItineraryCore(unordered_map<string, multiset<string>> &targets, vector<string> &route,string airport) {
	while (targets[airport].size()) {
		string tmp = *targets[airport].begin();
		targets[airport].erase(targets[airport].begin());
		findItineraryCore(targets, route, tmp);
	}
	route.push_back(airport);
}
vector<string> findItinerary(vector<pair<string, string>> tickets) {
	unordered_map<string, multiset<string>> targets;
	for (auto ticket : tickets) targets[ticket.first].insert(ticket.second);
	vector<string> route;
	findItineraryCore(targets, route,"JFK");
	return vector<string>(route.rbegin(), route.rend());
}
};

最后贴一下思路一和思路二的run time对比(我的代码和大神的代码,果然直播打脸。。。。):

Reconstruct Itinerary 重新安排行程

相关标签: leetcode