1345. 跳跃游戏 IV（Rating 1810）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1345. 跳跃游戏 IV

Rating 1810

思路

一眼bfs。可以连接的边是相同的数以及左右两边的数，建图后bfs即可找到最短路径。

但是潇洒写完一波后TLE了，代码如下

from collections import defaultdict
from collections import deque

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        num_dict = defaultdict(list)
        for idx, num in enumerate(arr):
            num_dict[num].append(idx)
        q = deque()
        q.append(0)
        vis = set()
        vis.add(0)
        ret = 0
        while q:
            sz = len(q)
            while sz:
                sz -= 1
                idx = q.popleft()
                num = arr[idx]
                if idx == len(arr) - 1:
                    return ret
                if idx - 1 >= 0 and idx - 1 not in vis:
                    q.append(idx - 1)
                    vis.add(idx - 1)
                if idx + 1 < len(arr) and idx + 1 not in vis:
                    q.append(idx + 1)
                    vis.add(idx + 1)
                for i in num_dict[num]:
                    if i not in vis:
                        q.append(i)
                        vis.add(i)
            ret += 1
        return -1

TLE的case类似于[7,7,7,7,7,7,…,7,7,11]

仔细分析下原因不难得出，虽然bfs复杂度是O(n)的，但每次遍历一个index时，都要重复遍历一遍相同的数判断是否需要加入队列，即罪魁祸首是下面这段代码在例如上面的特殊case下是O(n)的，所以整体的复杂度就变成了O(n^2)

for i in num_dict[num]:
    if i not in vis:
        q.append(i)
        vis.add(i)

优化点也不难想到，循环遍历完一个数后，理论上其对应的所有index都已经加入到队列中了，因此可以在dict中删除该数字，避免在后面的遍历中重复判断。

代码如下

代码

from collections import defaultdict
from collections import deque

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        num_dict = defaultdict(list)
        for i, num in enumerate(arr): # 使用dict维护相同数字对应的下标，方便建图
            num_dict[num].append(i)

        q = deque() # 初始化队列
        q.append(0)
        vis = set() # 初始化访问过的index set
        vis.add(0)
        ret = 0
        while q: # bfs 模板
            sz = len(q)
            while sz:
                sz -= 1
                idx = q.popleft()
                if idx == len(arr) - 1: # 找到终点
                    return ret
                if idx - 1 >= 0 and idx - 1 not in vis: # 添加左右两个index
                    q.append(idx - 1)
                    vis.add(idx - 1)
                if idx + 1 < len(arr) and idx + 1 not in vis: # 添加左右两个index
                    q.append(idx + 1)
                    vis.add(idx + 1)
                num = arr[idx]
                for i in num_dict[num]: # 添加相同数字对应的index
                    if i not in vis:
                        q.append(i)
                        vis.add(i)
                num_dict.pop(num) # 因为所有num对应的index已全部加入队列，所以在dict中删除该数字，后续避免重复判断
            ret += 1
        return -1