https://leetcode-cn.com/problems/zui-xiao-tiao-yue-ci-shu/
我最开始的想法是BFS,但是很快枪毙了,是因为如果考虑向前跳的话,那么可能会出现O(n^2)的算法。但实际情况是,如果按照深度顺序去更新的话,并不是每次都需要考虑所有的前面节点,只需要考虑到上次更新之后的节点。下面代码参考的是 这个解答
class Solution:
def minJump(self, jump: List[int]) -> int:
n = len(jump)
depth = [0] * n
from collections import deque
dq = deque()
dq.append(0)
max_left = 0
ans = 0
while dq:
x = dq.popleft()
y = x + jump[x]
if y >= n:
ans = depth[x] + 1
break
if not depth[y]:
depth[y] = depth[x] + 1
dq.append(y)
for y in range(max_left + 1, x):
if not depth[y]:
depth[y] = depth[x] + 1
dq.append(y)
max_left = max(max_left, x)
return ans
实际上这里还有更牛的 回答:一种经典的套路,我忍不住摘抄过来
直接建图跑最短路复杂度是O(n^2)的,因为对每个u>v,都有一条从u到v的边。一种经典的套路就是对每个u新增对应虚拟点u',然后新增三种边: 1.每个u向u'连一条边,长度为1。 2.每个u'向(u-1)'连一条边,长度为0。 3.每个u'向u连一条边,长度为0。 那么就等效于对每个u>v,都有一条长度为1的路径。