【LeetCode】Day201

LeetCode】Day201"/>

【LeetCode】Day201

题目

332.重新安排行程【困难】

题解

这道题的几个难点：

1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
2. 有多种解法，字母序靠前排在前面，应该如何记录映射关系？
3. 使用回溯法，终止条件是什么？
4. 搜索的过程中，如何遍历一个机场所对应的所有机场？

如何理解死循环

如图情况，若没有处理好，可能在JFK和NRT之间形成死循环

如何记录映射关系

一个机场映射多个机场，机场之间要靠字母序排列，可以使用HashMap记录
定义如下：

Map<String,Map<String, Integer>>map：Map<出发机场，Map<到达机场，航班次数>>map

为什么一定要增删元素呢？因为出发机场和到达机场会重复，搜索的过程没及时删除目的机场就会死循环。

在遍历Map<出发机场，Map<到达机场，航班次数>>map过程中，可以使用“航班次数”这个字段做加减，来标记到达机场是否使用过了。

如果“航班次数”大于0，说明目的地还可以飞，如果“航班次数”等于0说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。（相当于说我不删，我就做一个标记！）

回溯法

递归树

回溯三部曲

1. 递归函数参数
   使用Map<出发机场，Map<到达机场，航班次数>>map记录航班的映射关系

注意这里函数返回值是boolean！而不是通常用的void！

因为我们只需要找到一个行程，就是在树形结构中唯一一条通向叶子节点的路线，如上递归树所示。

2. 递归终止条件
   回溯过程中遇到的机场个数，达到了（航班数量+1），就找到了一个行程，将所有航班串在一起了。

if(res.size()==n+1){return;
}

3. 单层搜索过程
   回溯的过程中，如何遍历一个机场所对应的所有机场呢？

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++;}
}

完整代码

回溯法代码实在是太麻烦了，还是换成官方题解的“Hierholzer 算法" 了，用于在连通图中找欧拉路径。

对于航班映射关系的存储和上面不同，对于java来说这种写法简便很多，也方便删除！

class Solution {List<String>res=new ArrayList<>();Map<String,PriorityQueue<String>>map=new HashMap<>();//记录航班映射关系public List<String> findItinerary(List<List<String>> tickets){int n=tickets.size();//初始化航班映射关系for(List<String>ticket:tickets){String src=ticket.get(0),dest=ticket.get(1);//首次存入新建优先队列if(!map.containsKey(src))map.put(src,new PriorityQueue<>());map.get(src).add(dest);}//深搜dfs("JFK");Collections.reverse(res);//最先找到的是最深的不能再走的目的地，所以要反转过来return res;}public void dfs(String src){//当传入的参数是始发地而且还有边的时候，取边出队删除并且继续递归深搜这条边的点，一直到不能再走再返回while(map.containsKey(src)&&map.get(src).size()>0)dfs(map.get(src).poll());res.add(src);}
}

时间复杂度： O ( m l o g m ) O(mlogm) O(mlogm)，m是边的数量，对于每一条边需要O(logm)删除它。

空间复杂度： O ( m ) O(m) O(m)，需要存储每一条边。

p.s 最近一直在攻回溯，在二刷有些题，力扣系列都没有更新
p.p.s 力扣终于刷到300题了！按理说一天一道应该早就到了，可惜中间摸鱼了太多天，最近要抓紧进度了