C++ 【贪心】跳跃游戏Ⅱ 如何用最少的次数实现跳跃至最远的位置_你的目标是使用最少的跳跃次数到达数组的最后一个位置

跳跃游戏(进阶版)

题目[leetcode45]

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

示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:
假设你总是可以到达数组的最后一个位置。

思路

因为数组是一定能够到达最后一个位置的，所以还是运用跳跃游戏Ⅰ里的核心公式计算出第 i 位置最远可跳至的位置i+nums[i]，当仍未到达所能跳跃的最远位置时，都不进行跳跃操作，因为要找出从第i个位置到最远的i+nums[i]位置之间的最远跳跃位置，这样之后再进行跳跃，控制最少的跳跃次数，跳至最远的距离，从而得到最少的次数。【贪心思想】
过程如图所示：

实现代码如下：

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() < 2){ //当距离为0时，不用跳跃
            return 0;
        }
        int current_max_index = nums[0]; //记录当前所能跳跃的最远位置
        int pre_max_index = nums[0]; //记录遍历过程中跳跃到的最远位置
        int jump_min = 1; //距离不为0，就一定要跳一步
        for(int i = 1; i < nums.size(); i++){
            if(i > current_max_index){
                current_max_index = pre_max_index; //改变当前所能跳跃的最远位置
                jump_min++; //进行跳跃
            }
            if(pre_max_index < nums[i] + i){
                pre_max_index = nums[i] + i; //i到current_max_index中的最远眺至位置
            }
        }
        return jump_min;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

致谢

本章知识点和思路由小象学院相关视频提供，由本人学习并梳理得出，希望自己加深记忆的同时，也能给大家提供更多有关于一些算法的知识点。
你的点赞、评论、收藏就是对我最大的支持与鼓励，谢谢！