9.跳跃游戏

题目

给你一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回true；否则，返回false。

示例 1:

• 输入：nums = [2,3,1,1,4]
• 输出：true
• 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

• 输入：nums = [3,2,1,0,4]
• 输出：false
• 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

思路

方式一

题目中说：数组中的每个元素代表你在该位置可以跳跃的最大长度。 所以我们只要保证能够跳跃的最大长度超过了数组的长度就可以。

• 每走一步就记录最远可以到哪里
• 最远可达位置够不够你继续往前走

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        rightmost = 0
        for i in range(len(nums)):
            # 在可走的最大步数范围内走
            if i <= rightmost:
                # 每走一步更新一下可继续走的最大步
                rightmost = max(rightmost, i + nums[i])
                if rightmost >= len(nums) - 1:
                    return True
        return False

方式二

• 假设在一个格子上，每个格子有对应的能量值。
• 每前进一步需要消耗一个能量；
• 而到达一个格子后， 如果当前格子储存的能量值较大，则更新为较大的能量值；
• 如果当前格子能量值小于现有的能量值，则无需更新；
• 如果出现能量值正好消耗完，那就没能量继续走了，最远的步数就是这里了
• 判断最远的步数与数组的长度一样不一样

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

        for i in range(len(nums)):
            cur -= 1
            if cur < nums[i]:
                cur = nums[i]
            if cur <= 0:
                break
        return i == (len(nums) - 1)

kotlin实现方式二:

class Solution {
    fun canJump(nums: IntArray): Boolean {
        if (nums.size == 1) {
            return true
        }
        var count = nums[0]
        for (i in 1 .. nums.lastIndex - 1) {
        // 没有能量了
            if (count <= 0) {
                return false
            }
        // 跳一格，能量减1
            count --
        // 看目前的最大能量以及当前格子的能量哪个大，哪个大就用哪个
            count = max(count, nums[i])

        }
    // 最后还有能量就能到达
        return count > 0
    }
}

• 下一篇

• 邮箱 ：charon.chui@gmail.com
• Good Luck!