45题的时候已经见过这道题了,只不过之前是返回从第 0 个位置能跳到最后一个位置的最小步数,这道题是返回是否能跳过去。
leetCode Solution 中给出的是动态规划的解法,进行了一步一步的优化,但都也比较慢。不过,思路还是值得参考的,上边说的比较详细,这里就不啰嗦了。这里,由于受到 45 题的影响,自己对 45 题的解法改写了一下,从而解决了这个问题。
下边的解法都是基于45题 的想法,大家可以先过去看一下,懂了之后再回到下边来看。
解法一 顺藤摸瓜
45 题的代码。
publicintjump(int[] nums) { intend=0; intmaxPosition=0; intsteps=0; for(inti=0; i<nums.length-1; i++){ //找能跳的最远的maxPosition=Math.max(maxPosition, nums[i] +i); if( i==end){ //遇到边界,就更新边界,并且步数加一end=maxPosition; steps++; } } returnsteps; }
这里的话,我们完全可以把 step 去掉,并且考虑下当前更新的 i 是不是已经超过了边界。
publicbooleancanJump(int[] nums) { intend=0; intmaxPosition=0; for(inti=0; i<nums.length-1; i++){ //当前更新超过了边界,那么意味着出现了 0 ,直接返回 falseif(end<i){ returnfalse; } //找能跳的最远的 maxPosition=Math.max(maxPosition, nums[i] +i); if( i==end){ //遇到边界,就更新边界,并且步数加一end=maxPosition; } } //最远的距离是否到答末尾returnmaxPosition>=nums.length-1; }
时间复杂度:O(n)。
空间复杂度:O(1)。
总
当自己按照 45 题的思路写完的时候,看 Solution 的时候都懵逼了,这道题竟然这么复杂?不过 Solution 把问题抽象成动态规划的思想,以及优化的过程还是非常值得学习的。