leetcode第55题

简介: 当自己按照 45 题的思路写完的时候,看 Solution 的时候都懵逼了,这道题竟然这么复杂?不过 Solution 把问题抽象成动态规划的思想,以及优化的过程还是非常值得学习的。

image.png

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 把问题抽象成动态规划的思想,以及优化的过程还是非常值得学习的。


目录
打赏
0
0
0
0
10
分享
相关文章
|
9月前
|
leetcode-283:移动零
leetcode-283:移动零
32 0
|
4月前
【LeetCode 02】暴力法总结
【LeetCode 02】暴力法总结
34 1
|
9月前
|
leetcode-474:一和零
leetcode-474:一和零
49 0
顺手牵羊(LeetCode844.)
好多同学说这是双指针法,但是我认为叫它顺手牵羊法更合适
91 0
LeetCode——944. 删列造序
LeetCode——944. 删列造序
127 0
leetcode第45题
时间复杂度:O(n)。 空间复杂度:O(1)。 这里要注意一个细节,就是 for 循环中,i < nums.length - 1,少了末尾。因为开始的时候边界是第 0 个位置,steps 已经加 1 了。如下图,如果最后一步刚好跳到了末尾,此时 steps 其实不用加 1 了。如果是 i < nums.length,i 遍历到最后的时候,会进入 if 语句中,steps 会多加 1 。
134 0
leetcode第45题
leetcode第54题
在 leetcode 的 solution 和 discuss 看了下,基本就是这个思路了,只是实现上有些不同,怎么用来标记是否走过,当前方向,怎么遍历,实现有些不同,但本质上是一样的。就是充分理解题意,然后模仿遍历的过程。
115 0
leetcode第54题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等