45 55跳跃游戏解题记录

先是55跳跃游戏，暴力解法会怎样？会超出时间限制，而且有很多细节要注意：

func canJump(nums []int) bool {// 处理空数组情况，当nums只剩一个元素时，nums[i:]导致越界。if len(nums) == 0 {return false}// 如果只有一个元素，已经到达终点if len(nums) == 1 {return true}i := nums[0]if i == 0 { // 如果第一步就不能跳，且不是终点，则失败return false}// 尝试所有可能的跳跃步数for ; i>0; i-- {// 确保不会越界if i < len(nums) {if canJump(nums[i:]) { // 将剩余没判断的切片递归return true}}}return false
}

时间复杂度是O(n^n)。对于这个问题，更高效的解法是贪心算法。但是为什么是贪心呢，需要想我们只管跳得更远，比它近的地方一定是可以到达的。于是我需要遍历数组每个值，去维护一个能到达的最大长度。

func canJump(nums []int) bool {sum := 0for i, v := range nums {if sum < i { // sum已经是最远距离了，还不可达当前indexreturn false}if sum >= len(nums)-1 { // 已经到达或者超出最后一个index了return true }if sum < i+v {sum = i+v // 更新最长长度}}return false
}

45跳跃游戏二说的是一定可以到达，但是求最少跳几次。那不也是贪心贪的每一跳尽量远吗？那我记录一下上次贪心的次数。

func jump(nums []int) int {count := 0sum := 0for i, v := range nums {if sum >= len(nums)-1 { // 已经到达或者超出最后一个index了return count}if sum < i+v {sum = i+v // 更新最长长度count++}}return count
}

**然后错了。**我才反应过来，我不是要贪总的距离，这次我要贪每一跳尽量远。也就是每一跳都选择那一跳覆盖范围内的跳最远的，就能实现最少次数。

func jump(nums []int) int {count := 0i := 0for i < len(nums)-1 {// 避免越界, 如果当前位置本身就能从起点跳到终点if i+nums[i] >= len(nums)-1 {count += 1return count}// 还要找一个有潜力的落脚点，找到能去的落脚点中最远的那个maxi := i+1for j:=2; j<=nums[i]; j++ {if maxi+nums[maxi] < i+j+nums[i+j]{maxi = i+j}}i = maxi count += 1}return count
}