2021-09-12-jump-game.md

title	date	permalink	tags
跳跃游戏	2021-09-12	/posts/2021/09/jump-game/	greedy Array dynamic programming

题目描述

给定一个non-negative array nums, 你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

 示例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 {
    public boolean canJump(int[] nums) {
        // 关键：可跳的范围
        // 问题转化为：跳跃范围能不能覆盖到终点

        //base case
        if (nums.length == 1){
            return true;
        }

        // 覆盖范围: 看看能不能覆盖到终点
        int coverRange = nums[0]; //最开始至多能走几步
        for(int i=0;i<=coverRange;i++){
            //i+nums[i]: 能跳的范围
            coverRange = Math.max(coverRange, i + nums[i]);
            // 如果中途到了
            if(coverRange >= nums.length-1){
                return true;
            }
        }
        return false;
    }
}