[toc]
leetcode 45. 跳跃游戏 II.
题目描述
- 跳跃游戏 II
给定一个长度为 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]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]
解题思路
法1
方法1:模拟跳跃\
要使跳跃的次数最少那么前后两次跳跃之间必须默契配合才行
就是说第一次跳跃的位置必须考虑到第二次跳跃,两次跳跃的可以总距离必须
最远才可以,也就是相邻两次具有相关性
我们可以使用动态规划的思想来解决这个问题
- 确定本次可以跳跃的区间
- 跳跃 的位置加上该位置可以跳跃的距离就是两次跳跃的最远距离,最远距离最长的就是本次跳跃的位置,
- 每次循环,找出每次可以跳跃的区间,然后模拟跳到给位置上,在找下一个跳跃区间,直到跳完,既然跳跃的次数
- 时间复杂度(O())
- 空间复杂度(O())
执行结果
法1
// 选择跳跃的位置 返回最远两次跳跃的长度
func chise(nums []int) (r int) {
for i := 0; i < len(nums); i++ {
if r < i+nums[i] {
r = i + nums[i]
}
}
return
}
func jump(nums []int) (r int) {
t := 0
for i, j := 1, nums[0]+1; j < len(nums); r++ {
t = j
j = i + chise(nums[i:j]) + 1//从截止位置的后一个开始记录区间(左闭右开的结构特点)
i = t
}
r++
return
}
执行结果：
通过
显示详情
查看示例代码
添加备注
执行用时：
8 ms
, 在所有 Go 提交中击败了
97.23%
的用户
内存消耗：
5.8 MB
, 在所有 Go 提交中击败了
44.27%
的用户
通过测试用例：
109 / 109
炫耀一下:
法2
法3
本文由mdnice多平台发布
