55. Jump Game

Problem

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

https://leetcode.com/problems/jump-game/

Example 1:

Input: nums = [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:

Input: nums = [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.

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

Test Cases

1
2

class Solution:
    def canJump(self, nums: List[int]) -> bool:

1
2
3
4
5
6
7
8
9
10
11
12
13

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([2,3,1,1,4], True),
    ([3,2,1,0,4], False),
])
class Test:
    def test_solution(self, nums, expected):
        sol = Solution()
        assert sol.canJump(nums) == expected

Thoughts

从最右侧 r = n - 1 开始看。令 l = r - 1，如果 nums[l] >= r - l 说明从 l 可以跳到 r，那就令 r = l 继续。否则令 l = l - 1 继续。

最终如果 r 没有到达 0，说明最远也跳不到 r，更到不了终点，返回 false。

Code

1
2
3
4
5
6
7
8

class Solution:
    def canJump(self, nums: list[int]) -> bool:
        r = len(nums) - 1
        for l in range(r - 1, -1, -1):
            if nums[l] >= r - l:
                r = l

        return r == 0

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章