【leetcode】55. 跳跃游戏
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。
分析
关键是# 直到jump跳至数组尾部orjump超越了当前可以跳的最远位置。
1.
2.
3.
4.算法思路
5.算法思路-模拟
总结:
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
# 最远可达到的位置(index),不是落脚点,落脚点是这段中最远的位置
far = [] # 最远可以跳至的位置
for i, val in enumerate(nums):
temp = i+val
far.append(temp)
# print(far)
max_far = far[0]
jump = 0
# jump(当前位置)要<=最远能到的位置,这样才有路可以走
# 如果我现在处于的位置<最远能调到的位置,那么就一定true
while jump<len(nums) and jump<=max_far:
# 直到jump跳至数组尾部 or jump超越了当前可以跳的最远位置
if far[jump]>max_far:
# 如果当前可以跳的更远,则更新max_far
max_far = far[jump]
jump += 1
if jump == len(nums):
return True
return False