Leetcode 55.跳跃游戏

Leetcode 55.跳跃游戏,第1张

文章目录
  • 跳跃游戏
    • 一、题目描述
    • 二、思路
    • 三、代码实现

跳跃游戏 一、题目描述

https://leetclass="superseo">code-cn.com/problems/jump-game/

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

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

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

二、思路

假设 从 i 最远能够跳到 j。 那么i 跳到 i……j-1,j 的任何一个位置。那么我们应该跳到到哪呢?
贪心策略。我们应该跳到 i……j-1,j 这些位置中可以跳的更远的位置 的那个位置。
例:
这个例子中 在i到j中 j-1跳的更远,所以我们从i跳到j-1!
j-1最大能跳到 n 所以 我们在j-1 和 n 之间选择 能跳到更远位置的位置。依此类推

三、代码实现

我们先将每个位置能跳到的最大位置记录。
遍历整个数组,每次如果跳的位置更远,那么就更新最大位置。
注意:j<=max_index
说明当前所在的位置比能够跳到的最大位置小,
如果 j>max_index
说明当前所在的位置比能够跳到的最大位置还要大,说明跳不到j这个位置,那么一定跳不到最后。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==0) return 0;
        //求每个位置能跳到的最大下标
        int jump[100005]={0};
        for(int i=0;i<nums.size();i++) jump[i]=i+nums[i];
        int j=0;
        //当前能跳跃到的最大下标
        int max_index=nums[j];
        //从第一个位置 往后扫描 看最大能跳到哪个位置。注意 j>max_index 说明已经跳到了能达到的最大位置!
        while(j<nums.size()&&j<=max_index){
            if(jump[j]>max_index)
                //能跳的更远
                max_index=jump[j];
            j++;
        }
        if(j==nums.size())
            return true;
        else return false;
    }
};

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/791412.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-05
下一篇 2022-05-05

发表评论

登录后才能评论

评论列表(0条)

保存