332.重新安排行程

我就是我 2023-10-16 14:29 45阅读 0赞

#### 332.重新安排行程 ####

*  题干描述
 *  解题思路
 *  如何理解死循环
 *  该记录映射关系
 *  回溯法
 *   *  开始回溯三部曲讲解
     *   *  1. 递归函数参数
         *  2. 递归终止条件
         *  3. 单层搜索的逻辑
 *  总结
 *  代码实现

## 题干描述 ##

给定一个机票的字符串二维数组 \[from, to\]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

提示：

*  如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 \[“JFK”, “LGA”\] 与 \[“JFK”, “LGB”\] 相比就更小，排序更靠前。
 *  所有的机场都用三个大写字母表示（机场代码）。
 *  假定所有机票至少存在一种合理的行程。
 *  所有的机票必须都用一次 且 只能用一次。

示例 1：  
![在这里插入图片描述][8ea58baae16641af9806315ce1109bc4.png]

*  输入：\[\[“MUC”, “LHR”\], \[“JFK”, “MUC”\], \[“SFO”, “SJC”\], \[“LHR”, “SFO”\]\]
 *  输出：\[“JFK”, “MUC”, “LHR”, “SFO”, “SJC”\]

示例 2：  
![在这里插入图片描述][977788926d754186a9ac7a1f4ae551f2.png]

*  输入：\[\[“JFK”,“SFO”\],\[“JFK”,“ATL”\],\[“SFO”,“ATL”\],\[“ATL”,“JFK”\],\[“ATL”,“SFO”\]\]
 *  输出：\[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”\]
 *  解释：另一种有效的行程是 \[“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”\]。但是它自然排序更大更靠后。

提示：

*  1 <= tickets.length <= 300
 *  tickets\[i\].length == 2
 *  fromi.length == 3
 *  toi.length == 3 fromi 和 toi 由大写英文字母组成
 *  fromi != toi

## 解题思路 ##

这道题目还是很难的，之前我们用回溯法解决了如下问题：**组合问题** ，**分割问题** ，**子集问题** ，**排列问题**。

直觉上来看这道题和回溯法没有什么关系，更像是图论中的深度优先搜索。

实际上确实是深搜，但这是深搜中使用了回溯的例子，在查找路径的时候，如果不回溯，怎么能查到目标路径呢。

所以我倾向于说本题应该使用回溯法，那么我也用回溯法的思路来讲解本题，其实深搜一般都使用了回溯法的思路，在图论系列中我会再详细讲解深搜。

**这里就是先给大家拓展一下，原来回溯法还可以这么玩！**

**这道题目有几个难点：**

1.  一个行程中，如果航班处理不好容易变成一个圈，成为死循环。
2.  有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
3.  使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
4.  搜索的过程中，如何遍历一个机场所对应的所有机场。

## 如何理解死循环 ##

对于死循环，我来举一个有重复机场的例子：  
![在这里插入图片描述][6b9a6c641fb948289042273fb76b06a2.png]  
为什么要举这个例子呢，就是告诉大家，出发机场和到达机场也会重复的，**如果在解题的过程中没有对集合元素处理好，就会死循环**。

## 该记录映射关系 ##

有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？

一个机场映射多个机场，机场之间要靠字母序排列，一个机场映射多个机场。

如果对map 和 set 的实现机制不太了解，也不清楚为什么 map、multimap就是有序的同学，可以看这篇文章**关于哈希表，你该了解这些！**。

如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。

**相当于说我不删，我就做一个标记！**

## 回溯法 ##

这道题目我使用回溯法，那么下面按照我总结的回溯模板来：

void backtracking(参数){
        
    	if(终止条件){
        
    		存放结果;
    		return;
    	}
    	for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){
        
    	处理节点;
    	backtracking(路径，选择列表); // 递归
    	回溯，撤销处理结果
    }

本题以输入：\[\[“JFK”, “KUL”\], \[“JFK”, “NRT”\], \[“NRT”, “JFK”\]为例，抽象为树形结构如下：  
![在这里插入图片描述][4203ab84347b4f8dacf2c21795f15c0b.png]

### 开始回溯三部曲讲解 ###

#### 1. 递归函数参数 ####

在讲解映射关系的时候，已经讲过了，使用`unordered_map<string, map<string, int>> targets;`来记录航班的映射关系，我定义为全局变量。

当然把参数放进函数里传进去也是可以的，我是尽量控制函数里参数的长度。

参数里还需要ticketNum，表示有多少个航班（终止条件会用上）。

注意函数返回值这里使用的是bool！

我们之前讲解回溯算法的时候，一般函数返回值都是void，这次为什么是bool呢？

因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，如图：  
![在这里插入图片描述][4277e05e21c742d9bc93e5cb3cffd280.png]  
所以找到了这个叶子节点了直接返回，这个递归函数的返回值问题我们在讲解二叉树的系列的时候，在这篇\*\*二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？\*\*详细介绍过。

当然本题的targets和result都需要初始化。

#### 2. 递归终止条件 ####

拿题目中的示例为例，输入: \[\[“MUC”, “LHR”\], \[“JFK”, “MUC”\], \[“SFO”, “SJC”\], \[“LHR”, “SFO”\]\] ，这是有4个航班，那么只要找出一种行程，行程里的机场个数是5就可以了。

所以终止条件是：我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了。

代码如下：

if(result.size() == ticketNum + 1){
        
    	return true;
    }

已经看习惯回溯法代码的同学，到叶子节点了习惯性的想要收集结果，但发现并不需要，本题的result相当于 \*\*回溯算法：求组合总和！\*\*中的path，也就是本题的result就是记录路径的（就一条），在如下单层搜索的逻辑中result就添加元素了。

#### 3. 单层搜索的逻辑 ####

回溯的过程中，如何遍历一个机场所对应的所有机场呢？

**可以说本题既要找到一个对数据进行排序的容器，而且还要容易增删元素，迭代器还不能失效**。

## 总结 ##

本题其实可以算是一道hard的题目了。

**如果单纯的回溯搜索（深搜）并不难，难还难在容器的选择和使用上**。

本题其实是一道深度优先搜索的题目，但是我完全使用回溯法的思路来讲解这道题题目，**算是给大家拓展一下思维方式，其实深搜和回溯也是分不开的，毕竟最终都是用递归**。

如果最终代码，发现照着回溯法模板画的话好像也能画出来，但难就难如何知道可以使用回溯，以及如果套进去，所以我再写了这么长的一篇来详细讲解。

## 代码实现 ##

class Solution {
        
        // 332.重新安排行程
        private LinkedList<String> res;
        private LinkedList<String> path13 = new LinkedList<>();
    
        public List<String> findItinerary(List<List<String>> tickets) {
        
            Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
            path13.add("JFK");
            boolean[] used = new boolean[tickets.size()];
            backTracking((ArrayList) tickets, used);
            return res;
        }
    
        public boolean backTracking(ArrayList<List<String>> tickets, boolean[] used) {
        
            if (path13.size() == tickets.size() + 1) {
        
                res = new LinkedList(path13);
                return true;
            }
    
            for (int i = 0; i < tickets.size(); i++) {
        
                if (!used[i] && tickets.get(i).get(0).equals(path13.getLast())) {
        
                    path13.add(tickets.get(i).get(1));
                    used[i] = true;
    
                    if (backTracking(tickets, used)) {
        
                        return true;
                    }
    
                    used[i] = false;
                    path13.removeLast();
                }
            }
            return false;
        }
    }

**参考资料**：[代码随想录-332.重新安排行程][-332.]

[8ea58baae16641af9806315ce1109bc4.png]: https://img-blog.csdnimg.cn/8ea58baae16641af9806315ce1109bc4.png
[977788926d754186a9ac7a1f4ae551f2.png]: https://img-blog.csdnimg.cn/977788926d754186a9ac7a1f4ae551f2.png
[6b9a6c641fb948289042273fb76b06a2.png]: https://img-blog.csdnimg.cn/6b9a6c641fb948289042273fb76b06a2.png
[4203ab84347b4f8dacf2c21795f15c0b.png]: https://img-blog.csdnimg.cn/4203ab84347b4f8dacf2c21795f15c0b.png
[4277e05e21c742d9bc93e5cb3cffd280.png]: https://img-blog.csdnimg.cn/4277e05e21c742d9bc93e5cb3cffd280.png
[-332.]: https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE