55. 跳跃游戏

Problem: 55. 跳跃游戏

思路

思路1：暴力解法

对于某个元素而言，如果可以跳到第start+i步，而且start+i的位置也可以跳到最后，也就符合要求。但是这种思路运行超时了

思路2：贪心算法 用一个变量记录可以到达的最右边的值，对于每个元素而言，可以达到的最右边是i + nums[i]，然后不断检查是否可以达到末尾的位置

Code

代码1：

func canJumpV1(nums []int) bool {
	return helper(nums, 0)
}

func helper(nums []int, start int) bool {
	if start == len(nums)-1 {
		return true
	}

	if nums[start] == 0 {
		return false
	}

	for i := 1; i <= nums[start]; i++ {
		if helper(nums, start+i) {
			return true
		}
	}

	return false
}

代码2：

func canJump(nums []int) bool {
	rightMost := 0
	for i := 0; i < len(nums); i++ {
		if i <= rightMost {
			// 注意：必须包含=的情况，特殊case是输入为：[0]
			if i+nums[i] >= rightMost {
				rightMost = i + nums[i]
				if rightMost >= len(nums)-1 {
					return true
				}
			}
		}
	}

	return false
}