Leetcode 55. 跳跃游戏

港控/mmm° 2022-10-14 01:14 171阅读 0赞

#### 题目重述 ####

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

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

#### 示例 1： ####

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

#### 示例 2： ####

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

#### 提示： ####

1 <= nums.length <= 3 \* 104  
0 <= nums\[i\] <= 105

#### 思路解析 ####

维护一个计数器，标志从0位置能到的最大距离，在遍历数组的时候，不断地更新这个计数器，如果计数器大于数组长度，那么就代表能到。

#### C++实现 ####

class Solution {
        
    public:
        bool canJump(vector<int>& nums) {
        
            // 标记从0位置能到的最远距离
            int right_most = 0;
            for(int i=0;i<nums.size();i++)
            {
        
                // 如果当前位置是0能到的
                if(i<=right_most)
                {
        
                    // 更新能到的最远距离
                    right_most = max(right_most,i+nums[i]);
                    if(right_most>=nums.size()-1)
                    {
        
                        return true;
                    }
                }
            }
            return false; 
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode 55. 跳跃游戏

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

港控/mmm°/ 2022年10月14日 01:14/ 0 赞/ 171 阅读

相关 Leetcode 55. 跳跃游戏

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

小灰灰/ 2022年09月14日 14:20/ 0 赞/ 173 阅读

相关 leetcode55跳跃游戏

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

你的名字/ 2022年09月04日 06:41/ 0 赞/ 213 阅读

相关 leetcode 55 跳跃游戏

前言题目：[55. 跳跃游戏][55.] 参考题解：[跳跃游戏-代码随想录][-] -------------------- 提交代码方法一：回溯

偏执的太偏执、/ 2022年08月28日 09:00/ 0 赞/ 163 阅读

相关【LeetCode】55. 跳跃游戏

题目链接：[https://leetcode-cn.com/problems/jump-game/description/][https_leetcode-cn.com_pro

ゝ一纸荒年。/ 2022年05月10日 15:10/ 0 赞/ 201 阅读

相关 leetcode:55. 跳跃游戏

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

不念不忘少年蓝@/ 2022年04月08日 09:58/ 0 赞/ 257 阅读

相关 leetcode 55. 跳跃游戏

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

旧城等待，/ 2022年01月18日 23:35/ 0 赞/ 263 阅读

相关 leetcode:55.跳跃游戏

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

深碍√TFBOYSˉ_/ 2021年12月18日 06:19/ 0 赞/ 261 阅读

相关 leetcode(55)跳跃游戏

跳跃游戏 1、解题思路：自底向上，动态规划 class Solution { public boolean canJump(int[] nums)

红太狼/ 2021年11月01日 08:30/ 0 赞/ 327 阅读

相关 LeetCode55. 跳跃游戏

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

拼搏现实的明天。/ 2021年09月26日 20:14/ 0 赞/ 308 阅读