添加链接描述
思路:
- 从后往前找:必到最后一个下标,最后一个下标来自于之前的下标跳跃过来
- 如果有多个点都能跳到最后一步,那么选择离最后一步最远的下标,这里理所应当的就顺应的从左到右遍历数组
- 依次倒数第二步,倒数第三步…知道position变成0为止
class Solution:
def jump(self, nums: List[int]) -> int:
# 从后向前推导,如果有多个位置能到达最后一个位置,选择一个最远的
steps=0
position=len(nums)-1
while position>0: #如果position等于0就是从开始
for i in range(position):
if i +nums[i]>=position:
position=i
steps+=1
break
return steps
思路二:
- 从前向后遍历,记录每一次能跳跃到的最大下标
- 把这个最大下标记为边界,从左到右遍历数组,到达边界时,更新边界并将跳跃次数增加 1
- 这个思路不清晰
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
maxPos, end, step = 0, 0, 0
for i in range(n - 1):
maxPos = max(maxPos, i + nums[i])
if i == end:
end = maxPos
step += 1
return step