【LeetCode】332. 重新安排行程
力扣332题,重新安排行程...
【LeetCode】332. 重新安排行程
前言
最近在刷回溯专题的题目,前几种题型(排列、组合、子集、子序列)如果直接套用模板,加一些剪枝,随便过的那种
但是这一题如果带入普通的回溯模板,可能无从下手,主要原因是从数组类型的题目转为图论的题目,需要构建图,相对来说比较麻烦,这题我是用回溯模板进行解答调试了2小时才搞完,写完之后发现很多东西其实没必要写上去,没搞懂就开始写那还是挺憨的
这一题能用回溯做出来的前置条件就是——第一次回溯到的结果一定要是字典序最小的情况,否则如果想把所有的路程跑出来,数据量大了根本不可能。这就涉及到了一些贪心的算法了,到下面的算法部分细讲
当然这一题最好的做法当然不是回溯
,而是使用欧拉图
的知识来进行解答,在算法部分我会详细讲解两种做法
题目
给你一份航线列表 tickets ,其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。如果存在多种有效的行程,请你按字典排序返回最小的行程组合。
- 例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
示例 1:
输入:tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] 输出:["JFK","MUC","LHR","SFO","SJC"]
示例 2:
输入:tickets = [["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
思路
回溯
处理图
先使用一个map
来存放from
和to
,其中from
指向to
,这样每次取到一个点,都可以查看它的指向。
需要注意的是,这个map
的类型是Map<string, string[]>
,也就是一个from
点,可以指向多个to
的点
处理坐标
在我们回溯的过程中,要对每个from
的to
列表进行所有的路径进行回溯,如何让路径从上一条路走向下一条路,同时又可以回来呢?
我这里定义了一个idx_map
,专门用来处理from
这个点当前回溯到了哪一个to
的路径,所以这个类型是Map<string[], number>
,初始每个from
点的对应的to列表
的初始下标都是0
,等到开始回溯一条路之后,这个值就加1,会u完成后进行减一,如果回溯过程中这个值超过了to
的下标长度,那么直接结束回溯
处理次数
这里的次数指的是,同一点到另一点有几次,例如[["EZE","AXA"],["TIA","ANU"],["ANU","JFK"],["JFK","ANU"],["ANU","EZE"],["TIA","ANU"],["AXA","TIA"],["TIA","JFK"],["ANU","TIA"],["JFK","TIA"]]
其中["TIA","ANU"]
出现了两次,也就是说需要经过两次才可以
所以定义一个cnt_map
用来存放每个from
点要去的to
点的次数
,定义的格式是Map<string, number>
,其中,这里的key,也就是这个string
存放的是出发点+到达点
的形式,例如上述的例子中TIAANU --> 2
,也就是表示TIA到ANU需要两次
判断是否经过了某条路线
这里处理的就是回溯中典型的used
,其他题目中的used
非常简单,一般使用一个数组来存储boolean值就可以了
但是这里需要处理图中经过的路线,所以我的处理方式是,将这个used
写成一个Map<string, number>
的形式,和上面的处理次数的cnt_map
一样,每次回溯进过的from
和to
都会变成from+to --> cnt
的键值对形式,如果我们的cnt
超过了cnt_map
中记录的最大经过数量,那么就直接结束回溯(道理很简单,如果不结束,那么就可以在两个点之间互相走来走去,成为死循环)
所以在回溯的过程中,判断是否走过该条路的used
使用这种方式来判断就可以
判断回溯终止
回溯必定会有一个终止条件
,如果到达这个条件就结束回溯
这题中的回溯终止条件就是经过的点的数量 == 飞机票的数量+1
可以自己先想想为啥这样就可以结束回溯了?
把飞机票当作边用来连接两个点,点肯定是比边多一个的(无论多复杂的路径都可以被简化成一条边
处理图的代码
为了让代码更清楚,我这里将处理图和处理回溯分开来将
首先是去处理图的code
function findItinerary(tickets: string[][]): string[] {
const map: Map<string, string[]> = new Map()
const idx_map: Map<string[], number> = new Map()
const used: Map<string, number> = new Map()
const cnt_map: Map<string, number> = new Map()
tickets.forEach(([from, to]) => {
const from_to: string = from+to
if (cnt_map.has(from_to)) cnt_map.set(from_to, cnt_map.get(from_to)! + 1)
else cnt_map.set(from_to, 1)
if (!map.has(from)) {
const arr: string[] = [to]
map.set(from, arr)
idx_map.set(arr, 0) // 设置初始下标为0
}
else map.get(from)!.push(to)
})
...
}
以上代码就是处理图的部分,如何理解?
首先遍历所有的tickets
,进去后对出现的from+to
进行次数累加,同时判断map
中是否存在这样的路线,不存在就新建一个数组存放,存在就在原先的数组中添加当前的to
同时,在第一次建立map
的key的时候,把当前的idx_map
对应的下标初始化成0
回溯的代码
我写的flashback
函数就是回溯函数,判断结束的条件就是arr.length == tickets.length + 1
同时,如果map
中存在当前开始走的点,那么就可以往下走,取出这个开始的点称为start
,这个start
点肯定对应一个to
的数组,将这个数组称为nexts
数组,也就是下一步可以去的地点的数组
这里有一个非常重要的点,nexts
数组需要进行排序
!
排序的方式就是按照字典序升序排序,为啥要这样排序?
因为对每个nexts数组而言,如果下一次去的点的字典序最小,那么首次找到的完整路线一定是整个字典序最小的
所以排序
是这一题的回溯算法的最重要的一环(如果没有排序这个步骤,那么会进行找很多次的过程,直到找到所有的路径,但实际很多案例有很多很多的路径,根本找不完,直接超时!)
理解了排序
这个点之后,剩下的就直接套回溯的模板就行了
遍历所有的nexts
节点,判断每次走是否走了回头路,是否走的路超过了对应路程机票的数量,同时判断处理下一步走的位置,回溯完成后将位置还原,将used还原...需要注意的是,每一层的时候,需要让idx_map
的开始值重置为0
,否则会找不到很多路径
这里还有一个细节,如果让回溯函数的返回值定为boolean
类型,那么一旦找到第一个符合的路径,直接返回true
就可以将后续的所有路径全部省略不走了,找不到就返回false
具体细节直接看代码:
const lens: number = tickets.length + 1
let res: string[] = []
const flashback = (arr: string[], start: string) => {
if (arr.length == lens) {
res = [...arr]
return true
}
if (map.has(start)) {
// 如果可以往下走
const nexts: string[] = map.get(start)!
nexts.sort((a,b) => a < b ? -1 : 1)
// 重置每次的map,否则idx会累加导致越界异常
for (let key of idx_map.keys()) idx_map.set(key, 0)
const idx: number = idx_map.get(nexts)!
for (let i = idx; i < nexts.length; i++) {
// 不能走回头路
if (used.has(start+nexts[i]) && used.get(start+nexts[i])! >= cnt_map.get(start+nexts[i])!) continue
idx_map.set(nexts, i+1) // to列表的下标+1
arr.push(nexts[i])
const cnt: number = used.has(start+nexts[i]) ? used.get(start+nexts[i])! : 0
used.set(start+nexts[i], cnt+1)
if (flashback(arr, nexts[i])) return true
idx_map.set(nexts, i)
arr.pop()
used.set(start+nexts[i], cnt)
}
}
return false
}
完整代码
需要注意的是,这里回溯的调用是:flashback(["JFK"],"JFK")
,表示每次开始从JFK
开始走
function findItinerary(tickets: string[][]): string[] {
const map: Map<string, string[]> = new Map()
const idx_map: Map<string[], number> = new Map()
const used: Map<string, number> = new Map()
const cnt_map: Map<string, number> = new Map()
tickets.forEach(([from, to]) => {
const from_to: string = from+to
if (cnt_map.has(from_to)) cnt_map.set(from_to, cnt_map.get(from_to)! + 1)
else cnt_map.set(from_to, 1)
if (!map.has(from)) {
const arr: string[] = [to]
map.set(from, arr)
idx_map.set(arr, 0) // 设置初始下标为0
}
else map.get(from)!.push(to)
})
const lens: number = tickets.length + 1
let res: string[] = []
const flashback = (arr: string[], start: string) => {
if (arr.length == lens) {
res = [...arr]
return true
}
if (map.has(start)) {
// 如果可以往下走
const nexts: string[] = map.get(start)!
nexts.sort((a,b) => a < b ? -1 : 1)
// 重置每次的map,否则idx会累加导致越界异常
for (let key of idx_map.keys()) idx_map.set(key, 0)
const idx: number = idx_map.get(nexts)!
for (let i = idx; i < nexts.length; i++) {
// 不能走回头路
if (used.has(start+nexts[i]) && used.get(start+nexts[i])! >= cnt_map.get(start+nexts[i])!) continue
idx_map.set(nexts, i+1) // to列表的下标+1
arr.push(nexts[i])
const cnt: number = used.has(start+nexts[i]) ? used.get(start+nexts[i])! : 0
used.set(start+nexts[i], cnt+1)
if (flashback(arr, nexts[i])) return true
idx_map.set(nexts, i)
arr.pop()
used.set(start+nexts[i], cnt)
}
}
return false
}
flashback(["JFK"],"JFK") // 从JFK开始走
return res
}
回溯的效率感人,但是能过!(而且我这里处理图用了太多的map,导致内存消耗也很大)
欧拉通路
为什么和欧拉图扯上关系?
回想一下欧拉图
的定义?
简答来说就是一笔画
问题,一笔可以经过所有的边且不重复
具有欧拉回路的称为欧拉图
具有欧拉通路但没欧拉回路称为半欧拉图
回想完了再思考思考本题,为啥可以用欧拉图来解?
所有的机票看成 边, 我们需要将所有的 边 走完, 并且必须走一次且只能走一次
这不就是欧拉图的定义吗?
题目要求我们给出走过每个顶点的路径,不就是欧拉回路中走过的点的次序吗,只要找到一条字典序最短的欧拉回路
就是我们想要的答案
同时由于规定了一定从JFK
开始,只要从JFK开始找一条欧拉通路就可以了
如何解欧拉图中的欧拉回路?
著名的Hierholzer
算法就可以用来解有向欧拉图中的欧拉回路(通路)
过程:
- 选择任一顶点为起点,遍历所有相邻边
- 深度搜索,访问相邻顶点。将经过的边都删除(重点
- 如果当前顶点没有相邻边,则将顶点入栈
- 栈中的顶点倒序输出,就是从起点出发的欧拉回路(通路)
当然如果将本题带入,起点一定是JFK
Hierholzer伪代码
可以当作一个模板记一下,使用递归非常的简单
const map: Map<string, string[]> = ...
const res: string[] = []
const dfs = (node: string) => {
while (map.get(node).length) {
dfs(map.get(node).pop())
}
res.push(node)
}
dfs(node)
res.reverse() // 逆序后就是欧拉回路
上述伪代码的重点就是map.get(node).pop()
,每次经过的边都去pop删除,这样下次dfs就不会有该边的记录
如何建图?
我们已经直到如何在欧拉图中使用Hierholzer
来获取欧拉回路
现在的问题就是如何构建这个图,其实和回溯中的建图是一样的,只不过少了很多其他的内容,只需要记录from
和tos
就行了
建图的代码
const map: Map<string, string[]> = new Map() // 图
tickets.forEach(([from, to]) => {
// 设置from和to的映射关系
if (map.has(from)) map.get(from).push(to)
else map.set(from, [to])
})
for (const val of map.values()) {
// 按照字典序降序,tos中的最后一个字典序最小
val.sort((a,b) => a < b ? 1 : -1)
}
建完图,这一题的一半就做完了,剩下的一半就是确定最小的字典序
如何保证字典序?
在回溯的算法中,我们是每次对即将遍历的所有tos
,在回溯之前进行了一次sort
我们在这里也需要进行sort,但是是按照什么方式排序呢?
其实我们sort完毕后的状态是一个降序状态,为什么是降序
?
因为在Hierholzer算法中,每次都是pop出栈顶元素,也就是list中最后的一个元素,我们想要保证每次走的路线的字典序最小,就要保证list中的最后一个元素的字典序最小,也就是降序
于是我们可以对刚刚建完图中的map进行一个列表元素降序排序
for (const val of map.values()) {
// 按照字典序降序,tos中的最后一个字典序最小
val.sort((a,b) => a < b ? 1 : -1)
}
写道这一部分,将map带入到我们的Hierholzer算法中,就可以求出字典序最小的欧拉回路啦!
带入Hierholzer
因为起点一定是JFK
,我们直接从这个点开始进行dfs
let start: string = "JFK"
const res: string[] = []
const dfs = (node: string) => {
while (map.has(node) && map.get(node).length) dfs(map.get(node).pop())
res.push(node)
}
dfs(start)
这样就得到了最终的结果,只需要将res逆序输出就是最终的路径了!
完整代码
function findItinerary(tickets: string[][]): string[] {
const map: Map<string, string[]> = new Map() // 图
tickets.forEach(([from, to]) => {
// 设置from和to的映射关系
if (map.has(from)) map.get(from).push(to)
else map.set(from, [to])
})
for (const val of map.values()) {
// 按照字典序降序,tos中的最后一个字典序最小
val.sort((a,b) => a < b ? 1 : -1)
}
// console.log(map)
let start: string = "JFK"
const res: string[] = []
const dfs = (node: string) => {
while (map.has(node) && map.get(node).length) dfs(map.get(node).pop())
res.push(node)
}
dfs(start)
return (res.reverse())
}
比回溯的时间快了将近30ms,内存消耗也大大提高,只用一个map建图就好了
其余思考
这一题对于起点已经定死了是JFK
,如果存在一个其他的点需要去寻找呢?
或者说如何在一个欧拉图中确定一个起点,可以让从这个起点开始顺利完成一笔画?
熟悉离散数学的同学一定会记得,可以通过入度
和出度
这两个概念来确定起点,出度 = 入度 + 1
的点一定可以当作一个起点(在欧拉图中)
如果给了某个提,需要确定起点同时确定一个欧拉通路,就可以使用度
的知识点来进行解答
没错,我说的这一题就是753. 破解保险箱
如果使用欧拉通路来解决这一题的同学,在753这道题也可以思考一下,如何解?当然,这题使用回溯DSF也是可以完成的,只不过一旦你领悟到了欧拉图的魅力,肯定是更倾向于使用数学知识而非暴力破解!
后话
由于大二离散数学学的本来就不行,所以从回溯的思想跳转到欧拉通路的思想上还是有很多需要改变的,如果思维好一点,融汇贯通,那么其实欧拉的数学方法还是更胜一筹的(在我看来