leetcode 45.跳跃游戏 II │ 汪福翔

题目描述

给定一个非负整数数组 nums，你最初位于数组的第一个位置。nums[i] 表示从 i 位置可以跳跃的最大长度。你的目标是跳到最后一个位置，并且尽量减少跳跃的次数。

示例 1:

输入: [2,3,1,1,4]
输出: 2
解释: 从位置 0 跳到位置 1, 然后跳到位置 3（跳了 2 次）

示例 2:

输入: [2,3,0,1,4]
输出: 2

题解

这个问题可以通过贪心算法解决。我们从数组的开始位置开始，每次跳到当前能跳到的最远位置，然后更新这个最远位置。我们使用一个指针 end 来表示当前能跳到的最远位置，一个指针 pos 来表示当前的位置，以及一个变量 step 来记录跳跃的次数。

下面是使用 Go 语言实现的代码：

package main

import "fmt"

func jump(nums []int) int {
    n := len(nums)
    if n <= 1 {
        return 0
    }
    pos, end, step := 0, 0, 0
    for pos < n-1 { // 遍历到倒数第二个位置
        maxReach := 0
        for i := end; i > pos && i < n; i++ {
            // 更新当前能跳到的最远位置
            maxReach = max(maxReach, i+nums[i])
        }
        end = maxReach
        step++ // 更新跳跃次数
        pos = end // 更新当前位置
    }
    return step
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    fmt.Println(jump([]int{2,3,1,1,4})) // 输出: 2
    fmt.Println(jump([]int{2,3,0,1,4})) // 输出: 2
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们需要遍历整个数组一次。
空间复杂度：O(1)，我们只使用了常数级别的额外空间。

#leetcode