​歌词快乐的一只小青蛙是什么歌(快乐的一只小青蛙儿歌歌词)

歌词快乐的一只小青蛙是什么歌(快乐的一只小青蛙儿歌歌词)

第45题：跳跃游戏 II

题目描述

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

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

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

快乐的一只小青蛙 leap leap leap leap leap frog~~~

我写这篇文章的时候一直被小跳蛙洗脑~[灵光一闪]

还是一样，本文答案参考自LeetCode官方题解。

这道题是经典的贪心算法题

贪心算法：每一次都要拿到局部最优解，最后就能够得到全局最优解

【方法1】贪心算法：反向查找

从终点向起点寻找，每次都要找到距离当前位置最远的且能跳到该位置的前一个位置，一直向前寻找，直到到达起点。

这句话有点长啊~，上图：

画得有点粗糙，大家见谅

其中，绿色的箭头是最终选择的跳跃路线（指从终点到起点），而红色的箭头是可以选择但不是最贪心的

【方法2】贪心算法：正向查找

这个就是正常方向的了。

思路跟方法1差不多，不过要注意的是 当前能跳跃的最远距离大于离终点的距离时，直接将跳跃次数加1就可以了（这不是废话吗[捂脸]）

乐的池塘里面有只小青蛙

它跳起舞来就像被王子附体了

酷酷的眼神 没有哪只青蛙能比美

总有一天它会被公主唤醒了

[来看我][来看我][来看我]