大浪淘沙

以平常心对股市沉浮, 不悔不怕
正文

leetcode 55 --jump game

(2019-12-05 10:25:04) 下一个

题意及分析:根据题目要求,数组里的每个元素表示从该位置可以跳出的最远距离,要求问从第一个元素(index=0)开始,能否达到数组的最后一个元素,这里认为最后一个元素为终点。这里是到达,说明超过也行,看下图能更好的理解题意。

 

所以这里可以使用贪心算法,计算出某个点时 能够跳出的最大距离(当前的最大值和(当前点+能跳出的最大距离)的较大的值),如果能跳出的最大距离大于最后一个点的位置,那么返回true,能到达;如果到达当前点后,不能在往后跳,那么不能达到最后点,返回false。

[ 打印 ]
阅读 ()评论 (0)
评论
目前还没有任何评论
登录后才可评论.