LeetCode 332 重新安排行程
332.重新安排行程
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
- 例如，行程
["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。
暴力回溯递归
最简单的方式为，穷举出全部合法的情况，然后筛选出字典序最小的：一个hash记录票的使用，一个string记录行程，一个 vector<string> 记录全部的合法序列，然后使用回溯的方式暴力递归。
但是在LeetCode中将会超出时间限制。
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
44
45
46
47
48
49
50
| class Solution {
public:
bool used[300]={false};
vector<string> res;
string path;
bool flag=false;
void DFS(vector<vector<string>>& tickets,int cur,string pre){
if(cur==tickets.size()){
res.push_back(path);
flag=true;
return;
}
string min="ZZZ";
if(cur==0){
for(int i=0;i<tickets.size();i++){
if(tickets[i].front()=="JFK"&&tickets[i].back()<=min){
path+="JFK";
path+=tickets[i].back();
used[i]=true;
DFS(tickets,cur+1,tickets[i].back());
if(flag) min=tickets[i].back();
used[i]=false;
path="";
}
}
}
for(int i=0;i<tickets.size();i++){
if(tickets[i].front()==pre&&!used[i]&&tickets[i].back()<=min){
used[i]=true;
path+=tickets[i].back();
DFS(tickets,cur+1,tickets[i].back());
used[i]=false;
if(flag) min=tickets[i].back();
for(int j=0;j<3;path.pop_back(),j++);
}
}
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
DFS(tickets,0,"");
string min=res.front();
for(int i=1;i<res.size();i++){
min = min>res[i]?res[i]:min;
}
vector<string> journey;
for(int i=0;i<min.size()/3;i++){
journey.push_back(min.substr(i*3,3));
}
return journey;
}
};
|
空间换时间
使用一个 map 完成有序地映射，从而在每一层根据出发地选取机票时，都能够优先选取目的地字典序最小的机票，此处本质上是一个图，并且题设告知存在路径。使用一个 unordered_map<string,map<string,int>> tic_map 去进行记录，本质上是 unordered_map<出发地,map<目的地,机票数>> tic_map 。
那么首先在结果数组 res 中加入一个 JFK 作为出发地，那么在每一层递归中只需要在 tic_map[res.back()] 中选取机票，此时优先选到的机票一定是字典序在前的。那么在每次优先选取最优的基础上，那么就一定能够找到最有路径。在找到最有路径后递归结束。
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
| class Solution {
public:
unordered_map<string,map<string,int>> tic_map;
vector<string> res;
bool backtracking(int ticnum){
if(res.size()==ticnum+1){
return true;
}
string dep=res.back();
for(auto &a:tic_map[dep]){
if(a.second>0){
res.push_back(a.first);
a.second--;
if(backtracking(ticnum))
return true;
res.pop_back();
a.second++;
}
}
return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
for (const vector<string>& vec : tickets) {
tic_map[vec[0]][vec[1]]++;
}
res.push_back("JFK");
backtracking(tickets.size());
return res;
}
};
|