55.md

题目地址

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

解答1

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """
            跳跃游戏(非最优解)

            给定一个非负整数数组，你最初位于数组的第一个位置。
            数组中的每个元素代表你在该位置可以跳跃的最大长度。
            判断你是否能够到达最后一个位置。

            输入: [2,3,1,1,4]
            输出: true
            解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
        """
        n = len(nums)
        for i in range(n - 2, -1, -1):
            if nums[i] > 0:
                continue
            elif nums[i] == 0:
                if i > 0:
                    temp = 0
                    for j in range(i - 1, -1, -1):
                        if nums[j] > i - j:
                            temp = 1
                            break
                    if temp:
                        continue
                    else:
                        return False
                else:
                    return False
        return True

解答2

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """
            跳跃游戏

            给定一个非负整数数组，你最初位于数组的第一个位置。
            数组中的每个元素代表你在该位置可以跳跃的最大长度。
            判断你是否能够到达最后一个位置。

            输入: [2,3,1,1,4]
            输出: true
            解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
        """
        n = len(nums)
        start = n - 2
        end = n - 1
        while start >= 0:
            if start + nums[start] >= end: end = start
            start -= 1
        return end <= 0

解答3

class Solution:
    def jump(self, nums) -> bool:
        """
            跳跃游戏

            给定一个非负整数数组，你最初位于数组的第一个位置。
            数组中的每个元素代表你在该位置可以跳跃的最大长度。
            你的目标是使用最少的跳跃次数到达数组的最后一个位置。

            输入: [2,3,1,1,4]
            输出: 2
            解释: 跳到最后一个位置的最小跳跃数是 2。
            从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
        """
        mx, sta, end, i, cnt = 0, 0, 0, 0, 0
        while i < len(nums) - 1:
            reach = i + nums[i]
            if reach >= mx:
                mx, sta = reach, i
            if i == end:
                i, end, cnt = sta, mx, cnt + 1
            i += 1
        return cnt