😭332.重新安排行程
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
示例
提示：
- 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
- 所有的机场都用三个大写字母表示（机场代码）。
- 假定所有机票至少存在一种合理的行程。
- 所有的机票必须都用一次 且 只能用一次。
示例 ：
- 输入：[[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]
- 输出：[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]
- 解释：另一种有效的行程是 [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”]。但是它自然排序更大更靠后。
思路
基本想法
需要明确以下问题：
如何搜索：从出发机场x开始搜索，判断x可以到哪些y，进行统计。之后再从y出发，判断y可以到哪些z。。。
如何排序：
题中要求对于同一个出发机场的不同到达机场，字母排序在前面的到达机场需要先选择
一定要理解这一句，所以在记录一个出发机场的所有到达机场时，需要将到达机场排序，可以使用map，因为他自动给元素排序
何时终止：给定一个tickets的集合，一共有ticketNum种行程，最终形成的行程序列长度一定是ticketNum+1
如何避免死循环：tickets中的一个元素只能使用一次，如果到达机场中出现起飞机场并且使用多次，那么就会出现死循环。避免的方法就是每一张票都有一个标签，使用过之后标签减一，为零就无法使用
这里为什么不用true和false呢，因为可能多张相同的票，所以需要记录相同的票出现的次数，然后使用过一张票，对应的票数就减一，票数为0就无法使用
总结：一个起飞机场对应多个降落机场，降落机场也可能重复，所以是一个一对多的关系，降落机场重复几次就是几张有效的机票
执行流程
首先统计所有的票，统计出现的次数，也就是上面说的标签。
统计完成之后，从肯尼迪机场出发，从统计的集合中遍历所有的到达机场，选取字母序排在前面的机场x加入结果集。
然后再从x出发，看x能到达哪些机场，选择一个字母序在前面的y。
再从y出发。。。
直到形成大小为ticketNum+1的结果集，此时可以直接返回答案。
但是由于是递归，只能一层一层的退出，所以给递归一个标志，当出现大小为ticketNum+1的结果集就返回true，当遇到true再返回true。一层一层向上最终回到开始位置，再返回结果集。
如果没有这个返回true的话，那么就会统计出所有符合要求的结果，最终的res会成为最后一种合法的结果，想要res保存的是第一种合法的结果，那么就需要在一出现这种合法的结果就向上返回，并且建立标志，便于程序提前结束
代码
根据以上分析，从回溯法的基本框架中得出以下代码：
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
51
52
53
| class Solution {
public:
//定义一个全局变量存放结果集
vector<string> res;
vector<string> findItinerary(vector<vector<string>>& tickets) {
//定义存放所有机票的集合
//集合元素的结构为
//<起飞机场，<降落机场，机票数>>
unordered_map<string,map<string,int>> targets;
//每次从tickets中拿一张机票统计
for(vector<string> vec:tickets){
//其中targets[vec[0]]是一个map
//map[vec[1]]取出的是map的第二个int类型的元素
//机票数++
targets[vec[0]][vec[1]]++;
}
//从肯尼迪出发
res.push_back("JFK");
backtrack(targets,tickets.size());
return res;
}
bool backtrack(unordered_map<string,map<string,int>> targets,int ticketNum){
if(res.size()==ticketNum+1){
return true;
}
//进行横向遍历，从起飞机场的所有到达机场中选择一个字典序排在前面的
//并且没有使用过的机票，也就是遍历map
//以结果集的最后一个元素当起飞机场继续航行
//也就是x到y，再从y出发
//res[res.size()-1]就是吧y当成起飞机场
for(map<string,int>::iterator ticket=targets[res[res.size()-1]].begin(); ticket!=targets[res[res.size()-1]].end(); ++ticket){
//机票还能使用
if(ticket->second>0){
//使用机票
res.push_back(ticket->first);
//机票销毁
ticket->second--;
//纵向遍历：从y开始
//不管if是不是为真，backtrack都会执行
if(backtrack(targets,ticketNum))
return true;
//进行回溯
res.pop_back();
ticket->second++;
}
}
//到这里返回false是什么意思
//还没有到叶子节点，不能一直向上返回
//但是当前的搜索结果又无法满足条件
return false;//必须要有这个，不然上面的if无法判断
}
};
|
其实for循环遍历所有的降落机场可以改为范围for循环，也就是：
1
2
3
4
5
6
7
8
9
| for (pair<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++;
}
}
|
此时直接取出了一个一个的队组，不用使用指针可以直接遍历到first和second
根据代码分析搜索树：
有两种情况都需要向上返回，第一种情况是无法找到合法的行程，从KUL出发无法降落。只能向上返回一层，所以return false，第二种是找到了合法的行程，此时return true。
并且从当前机场出发，搜索所有的降落机场时，机票有效才能使用这个机票，
也就是ticket->second > 0
java代码为：
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
| class Solution {
//tickets中的每一个list都是一个机票，1其中存储了起始点和终止点
//为了每次找到的行程都是当前能到达的行程中字典序最小的，先将终点进行排序
List<String> path=new ArrayList<>();
List<String> res;
public List<String> findItinerary(List<List<String>> tickets) {
//按照终点对票进行排序，每次找到最先符合要求的终点，然后是第二个，第三个
Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));
path.add("JFK");
//标记当前票据被使用过没
boolean[] used=new boolean[tickets.size()];
backtrack(tickets,used);
return res;
}
private boolean backtrack(List<List<String>> tickets,boolean[] used){
if(path.size()==tickets.size()+1){
res=new ArrayList(path);
return true;
}
//从中找到一个从当前起点出发的
for(int i=0;i<tickets.size();++i){
//当前起点是上一份路径的终点并且没访问过，可以向下尝试
if(!used[i]&&tickets.get(i).get(0).equals(path.get(path.size()-1))){
//加入终点
path.add(tickets.get(i).get(1));
used[i]=true;
if(backtrack(tickets,used)){
return true;
}
//回溯
used[i]=false;
path.remove(path.size()-1);
}
}
return false;
}
}
|
总结
主要是根据回溯法的框架形成的代码，有几个难点
统计所有的机票，依次取出tickets给出的vector集合，第一个元素是起飞机场，第二个元素是降落机场，也就是看懂：targets[vec[0]] [vec[1]]++
选取合适的数据结构，主要是target形成的复合unordered_map<string,map<string,int>>
分别代表<起飞机场，<降落机场，机票数»
如何遍历target，将当前降落的机场y当作==跳板==，也就是当成新的起飞机场，代码中体现为：result[result.size() - 1]],
之后筛选所有以y出发的机票信息，选择未使用的并且降落机场字典序排在前面的机票使用，所以使用map存储降落机场的信息，因为它可以排序
看懂for循环的遍历条件，遍历的是map
何时递归返回，需要区分是得到最终结果返回，还是遇到无法向下递归需要返回回溯一步的情况，具体可以看搜索树，出现无法降落的情况就无法递归