P107. 跳完数组的最少跳数

leetcode 45 lintcode 117 数组 贪心 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,给你一个非负整数数组,数组中的每个数字表示那个位置上可以向后跳的最大步数。一开始你站在下标为 0 的位置,你要计算出最少需要跳几次才能到达数组最后位置。如果无法到达数组最后位置,则返回 -1。

比如说,给你的数组 a 是:

2, 4, 0, 1, 2

一开始站在下标为 0 的位置,最多能向后跳 2 步。你先跳 1 步,来到 4,再跳 3 步就到达最后的位置。需要的最少跳数是 2。

再比如说,给你的数组是:

2, 1, 0, 4

一开始如果跳 2 步,到达 0,不能再跳。一开始如果跳 1 步,到达 1,可以向后再跳 1 步。但跳 1 步后仍然到达 0,不能再跳。因此对于这个数组,你没办法跳到最后的位置,返回 -1。

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。