leetcode 45. 跳跃游戏 II

题目描述

45. 跳跃游戏 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:模拟跳跃\

要使跳跃的次数最少那么前后两次跳跃之间必须默契配合才行

就是说第一次跳跃的位置必须考虑到第二次跳跃,两次跳跃的可以总距离必须 最远才可以,也就是相邻两次具有相关性

我们可以使用动态规划的思想来解决这个问题

1. 确定本次可以跳跃的区间
2. 跳跃 的位置加上该位置可以跳跃的距离就是两次跳跃的最远距离,最远距离最长的就是本次跳跃的位置,
3. 每次循环,找出每次可以跳跃的区间,然后模拟跳到给位置上,在找下一个跳跃区间,直到跳完,既然跳跃的次数

• 时间复杂度(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