Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4]Output: trueExplanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]Output: falseExplanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
I am thinking that go through each element of the array, whenever the integers are greater than the present "left" step, update the left. Each process, we can update the pos -= 1 to get close to end. If we can reach from any position with integers steps to the end return True, and return False when the "left" steps is -1.
class Solution: def canJump(self, nums: List[int]) -> bool: length = len(nums) #print(str(length) + "," +str(nums[pos])) pos = 0 left = nums[0] while nums[pos] >= 0 or left >=0: print("pos =" + str(pos)) print("left =" + str(left)) if left == -1: return False if nums[pos]+pos >= length-1: return True if nums[pos]> left: left = nums[pos] if nums[pos] >= 0 or left >=0: pos += 1 left -= 1
Space complexity if O(1) and time complexity is O(n) because we do not use any extra space other than 1, and only go through the given number array once.
请登录之后再进行评论