【LeetCode】55. 跳跃游戏

ゝ一纸荒年。 2022-05-10 15:10 204阅读 0赞

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

#### 题目描述 ####

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

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

判断你是否能够到达最后一个位置。

#### 示例 ####

输入: \[2,3,1,1,4\]  
输出: true  
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

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

#### 解决方法 ####

贪心算法。贪心策略：假设当前位置为i,在位置i能跳到的位置里选取使得下一步跳跃能达到最远的那个位置

class Solution { 
    public:
        bool canJump(vector<int>& nums) { 
            //贪心算法。贪心策略：假设当前位置为i,在位置i能跳到的位置里选取使得下一步跳跃能达到最远的那个位置
            if (nums.size()<=1) return true;
            int pos=0;
            while(pos<nums.size()){ 
                if (nums[pos]==0 && pos!=nums.size()-1) return false;
                if (pos==nums.size()-1) return true;
                int max=INT_MIN, k=pos; //选取下一个跳跃点
                for (int i=k+1;i<=k+nums[k] && i<nums.size();i++){ 
                    if (nums[i]+i>max){ 
                        pos=i;
                        max=nums[i]+i;
                    }
                }        
            }
            return false;
        }
    };

[https_leetcode-cn.com_problems_jump-game_description]: https://leetcode-cn.com/problems/jump-game/description/

发表评论取消回复

表情：

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

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

相关阅读

相关 Leetcode 55. 跳跃游戏

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

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

相关 Leetcode 55. 跳跃游戏

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

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

相关 leetcode55跳跃游戏

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

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

相关 leetcode 55 跳跃游戏

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

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

相关【LeetCode】55. 跳跃游戏

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

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

相关 leetcode:55. 跳跃游戏

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

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

相关 leetcode 55. 跳跃游戏

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

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

相关 leetcode:55.跳跃游戏

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

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

相关 leetcode(55)跳跃游戏

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

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

相关 LeetCode55. 跳跃游戏

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

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