LeetCode-重新安排行程（C++）

332. 重新安排行程

题目描述：

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1：

输入：tickets = [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]]
输出：[“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]

解题思路：

本题使用回溯算法。

一个机场对应多个机场，可以使用unordered_map，然后多个机场需要有个先后顺序，可以使用map<string,int>，第二个值用来记录到达机场的次数。次数大于0，说明目的地还可以飞。

定义全局变量unordered_map<string, map<string, int>> targets，将一个机场和多个机场的映射记录下来。首先将JFK加入结果集result。

回溯三部曲

1. 确定回溯函数参数和返回值：需要传入机票数量和结果集，返回类型为bool类型，因为只有唯一一条路径，其他路径返回false。
2. 确定终止条件：如果结果集里的元素个数等于机票数量加1，就说明找到了唯一的一条路径，返回true。
3. 确定单层回溯逻辑：将结果集最后一个元素作为targets的key值，遍历对应的value值（可能有多个，因为一个机场对应多个机场），然后看目的机场的次数是否大于0（目的机场已排好序，所以结果符合按字典排序返回最小的行程组合要求），大于说明可以到达目的机场，将目的机场加入结果集，目的机场次数减1，然后往下一层递归。接下来回溯，结果集弹出最后一个元素，目的机场加1。

代码：

class Solution {	//332. 重新安排行程
public:
	unordered_map<string, map<string, int>> targets;

	bool backtracking(int ticketNum, vector<string>& result) {
		if (result.size() == ticketNum + 1) return true;

		for (pair<const string,int>& target:targets[result[result.size() - 1]]) {
			if (target.second > 0) {
				result.push_back(target.first);
				target.second--;
				if (backtracking(ticketNum, result)) return true;
				result.pop_back();
				target.second++;
			}
		}
		return false;
	}

	vector<string> findItinerary(vector<vector<string>>& tickets) {
		targets.clear();
		vector<string> result;
		for (const vector<string>& vec : tickets) {
			targets[vec[0]][vec[1]]++;
		}
		result.push_back("JFK");
		backtracking(tickets.size(), result);
		return result;
	}
};

int main() {
	vector<vector<string>> tickets = { { "JFK", "SFO" }, { "JFK", "ATL" }, { "SFO", "ATL" }, { "ATL", "JFK" }, { "ATL", "SFO" } };
	Solution s;
	vector<string> result = s.findItinerary(tickets);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

参考资料：

代码随想录