45. 跳跃游戏 II
【摘要】 link给定一个长度为 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]。 Exa...
给定一个长度为 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]。
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.复制
func jump(nums []int) int {
// 动态规划四步走：
// 1、状态：f[i] 表示从起点到当前位置跳的最小次数
// 2、推导：f[i] = min(f[j]+1),a[j]) j >=i 表示从j位置用一步跳到当前位置，这个j位置可能有多个，取最小的一个就行
// 3、初始化：f[0] = 0
// 4、结果：f[n-1]
f := make([]int, len(nums))
f[0] = 0
for i := 1; i < len(nums); i++ {
// f[i] 先取一个默认最大值i
f[i] = i
// 遍历之前结果取一个最小值+1
for j := 0; j < i; j++ {
if nums[j]+j >= i {
f[i] = min(f[j]+1,f[i])
}
}
}
return f[len(nums)-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}复制
贪心
设每次所选的起跳位置为start，
能到的最大距离end为i+nums[start]，
我们为了能用最小的次数跳到终点，每次都想跳到最大的位置为max。
跳的次数为count
为了保证count最小，所以每次跳都要这一跳能跳的最远位置，解题思路应为贪心算法。从前向后遍历，
每完成一次跳跃后更新count与end的值，下一次的i即从上一跳的最远处end_{i-1}(=start_i)endi−1(=starti)开始计算，
遍历位置start_istarti到end_iendi得到能跳的最远处max，然后当遍历到end_iendi时，更新下一跳的起点start_{i+1}starti+1为max
func jump(nums []int) int {
if nums == nil || len(nums) == 0{
return -1
}
n := len(nums)
count,max,end := 0,0,0
for i:=0;i<n-1;i++{
// 记录每一个位置i所能跳到的最大位置max
if i+nums[i]>max{
max = i+nums[i]
}
// end是上一个所选的起跳位置能跳的最远处，当到达end时，更新下一跳的最大位置
if i == end{
end = max
count++
}
}
return count
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）