1.6 面试经典150题 - 跳跃游戏

跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

class Solution(object):def canJump(self, nums):""":type nums: List[int]:rtype: bool"""if not nums or len(nums) == 1: return True# 定义左右指针left = 0right = left + 1while right < len(nums):tmp_right = left# 计算本轮最有可以到达的位置for i in range(left, right):pos = i + nums[i]# 可以到达最后一个元素，提前返回if pos >= len(nums) - 1: return Trueif pos > tmp_right: tmp_right = pos# 本轮不能再向右了，返回falseif tmp_right < right: return False# 更新两个指针值left = rightright = tmp_right + 1return True

本题解题思路：

记录两个值：当前位置left，和目前可以到达的最右位置right

每次对区间内的位置进行遍历，找到新的 可以到达的最右位置

如果不能继续向右，则无法到达最后一个节点

如果可以，则更新left 和 right位置，继续遍历

 跳跃游戏II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i] 
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

class Solution(object):def jump(self, nums):""":type nums: List[int]:rtype: int"""if not nums or len(nums) == 1: return 0count = 0left = 0right = left + 1while right < len(nums):count += 1tmp_right = leftfor i in range(left, right):pos = i + nums[i]if pos >= len(nums) - 1: return countif pos > tmp_right: tmp_right = posif tmp_right < right: return -1left = rightright = tmp_right + 1return count

本题对上题略加修改，每次遍历都将计数加1，在上一题返回return的位置，变为返回计数即可。