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.
In first solution, i try to search every possible path to the end. return true until found one path. but the solution is too slow.
class Solution(object): def canJump(self, nums): """ :type nums: List[int] :rtype: bool """ if(len(nums) < 2): return True return self.innerCanJump(nums) def innerCanJump(self, nums): if(len(nums) == 0): return False if(len(nums) == 1): return True for i in range(nums): if self.innerCanJump(nums[i+1:]): return True return False
The most important point in this case is how far we can reach, not in which path, so just mark the longest station we can reach and check weather the end point in this range.
class Solution(object): def canJump(self, nums): """ :type nums: List[int] :rtype: bool """ reach = 1 for i in range(len(nums)): if (reach < i + 1): break; reach = max(reach, i + 1 + nums[i]) return reach >= len(nums)