55. 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.
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.
请登录之后再进行评论