题目简介：
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
说明:
- 如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”]相比就更小，排序更靠前
- 所有的机场都用三个大写字母表示（机场代码）。
- 假定所有机票至少存在一种合理的行程。
示例 1:
1
2
| 输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
|
示例 2:
1
2
3
| 输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
|
思路：
还是深搜+回溯的做法，深搜的终止条件是结果数组中的元素数量等于行程数量+1，即res.size() == tickets.size() + 1。
我们需要用到哈希表unordered_map<string, map<string, int>> targets来存储出发机场到多个降落机场的映射，由于使用了map，降落机场的排序将从小至大，满足题目要求，而map中的int用来判断该机场是否已被使用(防止重复循环)。
将哈希表初始化后便可进行深搜回溯，最后返回res即可。
tips:
- 哈希表的选择很重要
- 要使用
const string的格式，不然会报错
代码如下：
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
38
39
40
41
42
43
| class Solution {
public:
vector<string> res;
unordered_map<string, map<string, int>> targets;
bool dfs(const string& target, int num){
if(res.size() == num)
return true;
for(pair<const string, int>& fly : targets[target]){
if(fly.second > 0){
res.push_back(fly.first);
fly.second--;
if(dfs(fly.first, num))
return true;
res.pop_back();
fly.second++;
}
}
return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
for(int i = 0; i < tickets.size(); i++){
targets[tickets[i][0]][tickets[i][1]]++;
}
res.push_back("JFK");
dfs("JFK", tickets.size() + 1);
return res;
}
};
|
