算法题--跳步游戏判断是否可达终点

image.png

0. 链接

题目链接

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:

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:

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.

2. 思路1：贪心算法

题目要求是判断是否可以满足要求，换句话说，就是在每个位置处，判断
max_end = i + nums[i] >= len(nums) - 1是否成立, 如果不成立, 则记录到目前位置的最大的max_end, 然后寄希望于后续位置

在两种情况下，可以提前知晓结果:

• max_end >= len(nums) - 1成立, 则返回True
• i > max_end成立, 代表中间应该出现了0, 导致无法跳到第i个位置, 跳步在此中断, 返回False

3. 代码

# coding:utf8
from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) <= 1:
            return True

        end_idx = len(nums) - 1
        max_end = 0
        for i in range(end_idx + 1):
            if i > max_end:
                return False
            end = i + nums[i]
            if end > max_end:
                max_end = end
                if max_end >= end_idx:
                    return True

        return False


solution = Solution()
print(solution.canJump([2, 3, 1, 1, 4]))
print(solution.canJump([3,2,1,0,4]))
print(solution.canJump([0]))

输出结果

True
False
True

4. 结果

image.png