leetcode 45 跳跃游戏II

电玩女神 2022-08-28 09:00 122阅读 0赞

## 前言 ##

题目：[45.跳跃游戏II][45._II]

参考题解：[跳跃游戏II-力扣官方题解][II-]

--------------------

## 提交代码 ##

如果之前做过[leetcode 55 跳跃游戏][leetcode 55],那么“跳跃游戏II”应该不难。

核心思想：在当前范围\[s1,e1\]内，选择下一个跳转范围\[s2,e2\]。其中s2=e1+1，e2等于\[s1,e1\]中元素可以跳转最远的点。

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ELVrcxf3-1633511570677)(45\_跳跃游戏II.assets/image-20211006171135102.png)\]

class Solution {
    public:
        int jump(vector<int>& nums) {
            if(nums.size() == 1) // 只有一个元素，不用前进，到达重点
                return 0;
            
            int start = 0;
            int end = start + nums[start];
            int farthest_loc = end;
            int count = 1;
            if(farthest_loc >= nums.size()-1) // 终点在一级火箭的打击范围内
                return count;
            
            while(1){ // 题目限定：总是可以到达数组的最后一个位置
                count++; // 每进入一次循环，代表着使用新的打击范围
                for(int i=start+1; i<=end; i++){ // 下一级火箭，所能打击的最大范围
                    farthest_loc = max(farthest_loc,nums[i]+i);
                    if(farthest_loc >= nums.size()-1)
                        return count;
                }
                start = end;
                end = farthest_loc;
            }
        }
    };

[45._II]: https://leetcode-cn.com/problems/jump-game-ii/
[II-]: https://leetcode-cn.com/problems/jump-game-ii/solution/tiao-yue-you-xi-ii-by-leetcode-solution/
[leetcode 55]: https://blog.csdn.net/sinat_38816924/article/details/120626239

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-45. 跳跃游戏 II

题目来源贪心动态规划动态规划+贪心题目来源 [45. 跳跃游戏 II][45. _ II] 贪心如果移动下

谁借莪１个温暖的怀抱￠/ 2024年03月24日 16:02/ 0 赞/ 27 阅读

相关 leetcode55、45.跳跃游戏 I&II

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

我不是女神ヾ/ 2023年01月23日 13:48/ 0 赞/ 120 阅读

相关【贪心】 LeetCode45. 跳跃游戏 II

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

小咪咪/ 2022年12月03日 13:22/ 0 赞/ 139 阅读

相关 45. 跳跃游戏 II

> 给定一个非负整数数组，你最初位于数组的第一个位置。 > > 数组中的每个元素代表你在该位置可以跳跃的最大长度。 > > 你的目标是使用最少的跳跃次数到达数组的最后一个位

太过爱你忘了你带给我的痛/ 2022年10月08日 15:24/ 0 赞/ 124 阅读

相关 45. 跳跃游戏 II

[力扣![icon-default.png?t=L892][icon-default.png_t_L892]/images/20220828/372516f793d841769

朴灿烈づ我的快乐病毒、/ 2022年09月15日 00:08/ 0 赞/ 160 阅读

相关 leetcode 45 跳跃游戏II

前言题目：[45.跳跃游戏II][45._II] 参考题解：[跳跃游戏II-力扣官方题解][II-] -------------------- 提交代码如

电玩女神/ 2022年08月28日 09:00/ 0 赞/ 123 阅读

相关 LeetCode 45.Jump Game II (跳跃游戏II)

题目描述: 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

约定不等于承诺〃/ 2022年05月11日 04:16/ 0 赞/ 154 阅读

相关 leetcode:45.跳跃游戏 II

题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置

亦凉/ 2022年04月24日 13:44/ 0 赞/ 154 阅读

相关 leetcode:45. 跳跃游戏 II

题目: 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

曾经终败给现在/ 2022年04月12日 14:17/ 0 赞/ 166 阅读

相关 leetcode(45)跳跃游戏

跳跃游戏解题思路：贪心算法+自底向上 class Solution { public int jump(int[] nums) {

川长思鸟来/ 2021年10月18日 08:46/ 0 赞/ 289 阅读