力扣332题,重新安排行程...

【LeetCode】332. 重新安排行程

前言

最近在刷回溯专题的题目,前几种题型(排列、组合、子集、子序列)如果直接套用模板,加一些剪枝,随便过的那种

但是这一题如果带入普通的回溯模板,可能无从下手,主要原因是从数组类型的题目转为图论的题目,需要构建图,相对来说比较麻烦,这题我是用回溯模板进行解答调试了2小时才搞完,写完之后发现很多东西其实没必要写上去,没搞懂就开始写那还是挺憨的

这一题能用回溯做出来的前置条件就是——第一次回溯到的结果一定要是字典序最小的情况,否则如果想把所有的路程跑出来,数据量大了根本不可能。这就涉及到了一些贪心的算法了,到下面的算法部分细讲

当然这一题最好的做法当然不是回溯,而是使用欧拉图的知识来进行解答,在算法部分我会详细讲解两种做法

题目

给你一份航线列表 tickets ,其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。如果存在多种有效的行程,请你按字典排序返回最小的行程组合。

  • 例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

img

示例 1:

输入:tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] 输出:["JFK","MUC","LHR","SFO","SJC"]

img

示例 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来存放fromto,其中from指向to,这样每次取到一个点,都可以查看它的指向。

需要注意的是,这个map的类型是Map<string, string[]>,也就是一个from点,可以指向多个to的点

处理坐标

在我们回溯的过程中,要对每个fromto列表进行所有的路径进行回溯,如何让路径从上一条路走向下一条路,同时又可以回来呢?

我这里定义了一个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一样,每次回溯进过的fromto都会变成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
}

image-20220910141645238

回溯的效率感人,但是能过!(而且我这里处理图用了太多的map,导致内存消耗也很大)

欧拉通路

为什么和欧拉图扯上关系?

回想一下欧拉图的定义?

简答来说就是一笔画问题,一笔可以经过所有的边且不重复

具有欧拉回路的称为欧拉图

具有欧拉通路但没欧拉回路称为半欧拉图

回想完了再思考思考本题,为啥可以用欧拉图来解?

所有的机票看成 边, 我们需要将所有的 边 走完, 并且必须走一次且只能走一次

这不就是欧拉图的定义吗?

题目要求我们给出走过每个顶点的路径,不就是欧拉回路中走过的点的次序吗,只要找到一条字典序最短的欧拉回路就是我们想要的答案

同时由于规定了一定从JFK开始,只要从JFK开始找一条欧拉通路就可以了

如何解欧拉图中的欧拉回路?

著名的Hierholzer算法就可以用来解有向欧拉图中的欧拉回路(通路)

过程:

  1. 选择任一顶点为起点,遍历所有相邻边
  2. 深度搜索,访问相邻顶点。将经过的边都删除(重点
  3. 如果当前顶点没有相邻边,则将顶点入栈
  4. 栈中的顶点倒序输出,就是从起点出发的欧拉回路(通路)

当然如果将本题带入,起点一定是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来获取欧拉回路

现在的问题就是如何构建这个图,其实和回溯中的建图是一样的,只不过少了很多其他的内容,只需要记录fromtos就行了

建图的代码

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())
}

image-20220910153222062

比回溯的时间快了将近30ms,内存消耗也大大提高,只用一个map建图就好了

其余思考

这一题对于起点已经定死了是JFK,如果存在一个其他的点需要去寻找呢?

或者说如何在一个欧拉图中确定一个起点,可以让从这个起点开始顺利完成一笔画?

熟悉离散数学的同学一定会记得,可以通过入度出度这两个概念来确定起点,出度 = 入度 + 1的点一定可以当作一个起点(在欧拉图中)

如果给了某个提,需要确定起点同时确定一个欧拉通路,就可以使用的知识点来进行解答

没错,我说的这一题就是753. 破解保险箱

如果使用欧拉通路来解决这一题的同学,在753这道题也可以思考一下,如何解?当然,这题使用回溯DSF也是可以完成的,只不过一旦你领悟到了欧拉图的魅力,肯定是更倾向于使用数学知识而非暴力破解!

后话

由于大二离散数学学的本来就不行,所以从回溯的思想跳转到欧拉通路的思想上还是有很多需要改变的,如果思维好一点,融汇贯通,那么其实欧拉的数学方法还是更胜一筹的(在我看来