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的位置，变为返回计数即可。