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.

For example: A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

解题方法

brute force

jump game是从头开始的,那么就是一个从头遍历的过程, 新建一个array canReach, canReach[i]表示第i个是否能够跳到。

  • 对于index i
    • 如果canReach[i] == True， 那么将i能够跳到的index都设为true
    • 如果canReach[i] == False, 跳过进入下一个循环

  • 最终看canReach[n-1]是否为True

  • 时间复杂度 worst case O(n^2)

  • 空间复杂度 O(n)

优化算法

用一个变量maxReach记录当前能够reach到的最远的地方，如果i > maxReach, 说明这个reach不到，就可以跳过了； 否则就用A[i]更新maxReach。

Solution

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums:
            return False
        maxReach = 0
        for i in range(len(nums)):
            if i <= maxReach:
                maxReach = max(maxReach, i + nums[i])

        return maxReach >= len(nums) - 1

Reference