LeetCode 55. Jump Game

Posted on | In |
Words count in article: 235 | Reading time ≈ 1

题目

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:

1
2
3
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

1
2
3
Input: [3,2,1,0,4]
Output: false
Explanation: 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.

思路

Greedy.
max_num记录当前能到达的最大的位置，可能是之前能跳到的最大的位置，也可能是当前最大的能跳到的位置，即max_num = max(max_num, i+nums[i]).
如果当前能到达的最大的位置小于当前位置的索引，则表示到达不了，返回False. 如果能跳到最后，返回True.

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        max_num = 0
        for i in range(len(nums)):
            if max_num < i:
                return False
            max_num = max(max_num, i+nums[i])
        return True