Leetcode 45. Jump Game II

Topic link

Solution: Greed

For each index position, calculate the minimum number of hops needed to reach that position, and increase the number of hops when necessary.

func jump(nums []int) int {
    l := len(nums)
    if l == 0 {
        panic("nums is empty")}if l == 1 {
        return 0
    }
    // l > 1
    dp := make([]int, l)
    // dp[0] = 0
    for i, j := 0.1; i < l && j < l; i++ {
        n := nums[i]
        end := min(l, i+n+1)
        for j < end {
            dp[j] = dp[i]+1
            j++
        }
    }
    return dp[l- 1]}func min(a, b int) int {
    if a <= b {
        return a
    }
    return b
}
Copy the code

Time complexity O(n)O(n)O(n) O(n) space complexity O(n)O(n)O(n) O(n).

Solution 2 inMethod aOn the basis of optimizing spatial complexity

The solution method is the same, but the space complexity is optimized

func jump(nums []int) int {
    l := len(nums)
    if l == 0 {
        panic("nums is empty")}if l == 1 {
        return 0
    }
    if l == 2 {
        return 1
    }
    var (
        curr int // The current farthest reached index
        step int // The current minimum number of hops
        next int // The next hop reaches the farthest index
        end = l- 1 // Simplify the logic in the for loop below
    )
    for i := 0; i < end; i++ {
        x := i+nums[i]
        if x > next {
            next = x
        }
        if i == curr {
            step++
            curr = next
        }
    }
    return step
}
Copy the code

Time complexity O(n)O(n)O(n) space complexity O(1)O(1)O(1) O(1).