• En
  • Signup
  • 捐助


    • 今日签到
    • 连续签到



    • 查看作者
    • 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
    • 958
    • 请登录之后再进行评论

    • Tasks
    • Current Activities
    • Back to Top