• 注册
• 今日签到
• 连续签到
• 管理员
今天01:25
• Lee
今天02:03
• 查看作者
• # LeetCode: 55. Jump Game

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.

纽约州·纽约
• 0
• 0
• 0
• 1.1k
• 请登录之后再进行评论

• 做任务
• 提醒设置 全部清空
• 返回顶部