跳跃游戏

给出一个非负整数数组,你最初定位在数组的第一个位置。

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

判断你是否能到达数组的最后一个位置。


样例

A =[2,3,1,1,4],返回 true.

A =[3,2,1,0,4],返回 false.


需要注意的是,例如你现在的位置是A[0],元素是2,你可以选择跳一位,也可以选择跳两位。两位便是你可以跳跃的最大长度。

此题可以使用动态规划来进行求解。

设置一个常量max_j,表示最远能到达的位置,遍历数组中每一个数字,如果当前坐标大于max_t或者max_t已经抵达最后一个位置则跳出循环,否则就更新max_t的值为其和i + A[i]中的较大值,其中i + A[i]表示当前位置能到达的最大位置

代码:

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 给出一个非负整数数组,你最初定位在数组的第一个位置。 数组中的每个元素代表你在那个位置可以跳跃的最大长度。 判断你...
    Arnold134777阅读 1,088评论 0 0
  • 题目 给出一个非负整数数组,你最初定位在数组的第一个位置。 数组中的每个元素代表你在那个位置可以跳跃的最大长度。 ...
    六尺帐篷阅读 270评论 0 1
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,776评论 0 33
  • 计算机二级C语言上机题库(南开版) 1.m个人的成绩存放在score数组中,请编写函数fun,它的功能是:将低于平...
    MrSunbeam阅读 6,478评论 1 42
  • 今天我不想谈多么深奥,多么正经的东西,我只是想谈谈自己的生活,谈谈懵懂年华的疑惑。 我是一个普通到不能再...
    七晨阅读 254评论 1 0