LeetCode 刷题记录: 55. Jump Game [Python]

原题

https://leetcode.com/problems/jump-game/

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

思路

设定一个变量reachable记录当前能够达到的最远值。然后遍历nums:

  1. 当reachable<i时,即已经不能到达该处。返回False。

  2. 否则更新reachable,大小为当前能走的最远值以及此处可以走的最远值之间的最大值。

  3. 接着判断reachable是否大于nums,若是即可提前返回True跳出。

代码

1
2
3
4
5
6
7
class Solution:
def canJump(self, nums: List[int]) -> bool:
reachable=0
for i in range(len(nums)):
if reachable<i:return False
reachable=max(reachable,i+nums[i])
if reachable>=len(nums)-1: return True

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×