Jump game#
Practice Link#
LeetCode
Description#
- 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.
Examples#
1Input: [2,3,1,1,4]
2Output: true
3Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
1Input: [3,2,1,0,4]
2Output: false
3Explanation: You will always arrive at index 3 no matter what. Its maximum
4 jump length is 0, which makes it impossible to reach the last index.
Python Solution#
1class Solution:
2 def canJump(self, nums):
3 """
4 :type nums: List[int]
5 :rtype: bool
6 """
7 if len(nums) <= 1:
8 return True
9 jumps = 1
10 n = len(nums) - 2
11 for i in range(n, -1, -1):
12 if nums[i] >= jumps:
13 jumps = 1
14 else:
15 jumps += 1
16 return nums[0] >= jumps