跳跃游戏

题目

https://leetcode-cn.com/problems/jump-game/

解

package main

// [2,3,1,1,4]
func canJump(nums []int) bool {
    if len(nums) == 0 {
        return false
    }
    // 错误处理
    if len(nums) == 1 {
        if nums[0] >= 0 {
            return true
        } else {
            return false
        }
    }
    var ret = make([]bool, len(nums))
    for i := len(nums) - 2; i >= 0; i-- {
        if nums[i] >= len(nums)-1-i {
            ret[i] = true
            continue
        }
        if len(ret) >= nums[i]+i {
            // 遍历能到达的节点
            for j := i; j <= nums[i]+i; j++ {
                if ret[j] {
                    ret[i] = true
                    break
                }
            }
        }
    }
    return ret[0]
}

思路

从后往前遍历数据，每次遍历判断是否能到达最后，若是能，说明改点能jump，赋值true；若是不能赋值false；每个点判断自己能到达的点，若是能达到的点能jump，说明改点也能jump。