2021-05-28：跳跃游戏 II。给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的

福大大架构师每日一题

发布于 2021-08-05 15:53:15

2.5K0

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2021-05-28：跳跃游戏 II。给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

福大大答案2021-05-28：

准备三个变量，step，cur，next。step是步数，cur是当前可达，next是下次可达。遍历数组，当cur小于i，步数加1，下次可达变成当前可达，下次可达取自己和i+arr[i]的最大值。最后返回step。时间复杂度是O(N)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {

    arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
    ret := jump(arr)
    fmt.Println(ret)

}

func jump(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    step := 0
    cur := 0
    next := 0
    for i := 0; i < len(arr); i++ {
        if cur < i {
            step++
            cur = next
        }
        next = getMax(next, i+arr[i])
    }
    return step
}

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

执行结果如下：