原题目：

跳跃游戏 II

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

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

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]

输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2。

从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

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

解法：

这道题希望用最少的次数完成跳跃，符合贪心的思维：局部最优，不可取消

我们选择当前能选择的走的最远的路径

具体实现

遍历数组，在遍历过程中，

使用一个变量表示当前能一步走到的最远点

使用一个变量记录当前步骤中，下一步能最远到达的点

使用一个变量表示当前走的步数

首先规定程序如何“选择”出了最远的步

我们在遍历数组的过程中，记录了当前步骤能一步到达的最远的点，

无论我们在这个步骤中选择下一步走哪个，我们在循环到当前能一步走到的最远点时，我们一定能得到：走完了一步、下一步能一步到达的最远点。

如此遍历完数组，就得到了答案

class Solution {

    public int jump(int[] nums) {

    int end = 0;

    int maxPosition = 0;

    int steps = 0;

    for(int i = 0; i < nums.length - 1; i++){

        //找能跳的最远的

        maxPosition = Math.max(maxPosition, nums[i] + i);

        if( i == end){ //遇到边界，就更新边界，并且步数加一

            end = maxPosition;

            steps++;

        }

    }

    return steps;

}

}

巴特西

Leetcode力扣45题跳跃游戏 II

原题目：

解法：

具体实现

首先规定程序如何“选择”出了最远的步

最新文章

热门文章

巴特西

Leetcode力扣45题 跳跃游戏 II

原题目：

解法：

具体实现

首先规定程序如何“选择”出了最远的步

最新文章

热门文章

Leetcode力扣45题跳跃游戏 II