55. 跳跃游戏

55. 跳跃游戏 - 力扣（LeetCode）

代码一

func canJump(nums []int) bool {

	jumpMap := make(map[int]struct{}, 0)

    jumpMap[0] = struct{}{}

	for i := 0; i < len(nums); i++ {
        if _, ok := jumpMap[i]; !ok {
            continue
        }

		if nums[i]+i+1 >= len(nums) {
			return true
		}

		for j := 1; j <= nums[i]; j++ {
			jumpMap[i+j] = struct{}{}
		}
	}

    return false
}

执行时间很长，但是能通过

代码二 - 贪心

func canJump(nums []int) bool {
    maxReachNum := 0

    for i := range nums {
	    // 如果最大值已经超过了最大索引，那么直接返回
        if maxReachNum >= len(nums)-1 {
            return true
        }
        if i > maxReachNum {
            return false
        }

        maxReachNum = max(maxReachNum, i+nums[i])
    }

    return true
}

维护一个最大可以到达的最大值，如果 i 比这个值大，那么就代表，无法继续往后走了