题目描述:
给定一个长度为 n
的 0 索引整数数组 nums
。初始位置为 nums[0]
。
每个元素 nums[i]
表示从索引 i
向后跳转的最大长度。换句话说,如果你在 nums[i]
处,你可以跳转到任意 nums[i + j]
处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1]
的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]
。
代码思路:
- 初始化变量:
num_c
:记录跳跃次数,初始化为0。position
:记录当前需要到达的目标位置,初始化为数组的最后一个索引(len(nums) - 1
),因为目标是到达数组的最后一个位置。
- 循环直到到达起始位置:
- 使用一个
while
循环,条件是position > 0
,意味着只要还没到达数组的第一个位置(索引0),就继续循环。
- 使用一个
- 寻找能够到达当前目标位置的最远起始点:
- 在每次循环中,使用一个
for
循环遍历从0到position
(包括position
)的所有位置。 - 对于每个位置
i
,检查从i
出发能否跳跃到或超过当前的目标位置position
(即i + nums[i] >= position
)。 - 如果可以,增加跳跃次数
num_c
,并将position
更新为当前的起始点i
,然后跳出内层循环。
- 在每次循环中,使用一个
- 返回结果:
- 循环结束后,返回跳跃次数
num_c
。
- 循环结束后,返回跳跃次数
代码实现:
class Solution:def jump(self, nums: List[int]) -> int:num_c = 0position = len(nums) - 1while position > 0:for i in range(position + 1):if i + nums[i] >= position:num_c += 1position = ibreakreturn num_c