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


相关文章
|
6月前
leetcode-472. 连接词
leetcode-472. 连接词
49 0
|
1月前
【LeetCode 02】暴力法总结
【LeetCode 02】暴力法总结
15 1
|
6月前
leetcode-827:最大人工岛
leetcode-827:最大人工岛
61 0
|
6月前
leetcode-475:供暖器
leetcode-475:供暖器
48 0
|
6月前
leetcode-1219:黄金矿工
leetcode-1219:黄金矿工
79 0
|
6月前
|
消息中间件 Kubernetes NoSQL
LeetCode 1359、1360
LeetCode 1359、1360
|
Python
LeetCode 1904. 你完成的完整对局数
一款新的在线电子游戏在近期发布,在该电子游戏中,以 刻钟 为周期规划若干时长为 15 分钟 的游戏对局。这意味着,在 HH:00、HH:15、HH:30 和 HH:45 ,将会开始一个新的对局,其中 HH 用一个从 00 到 23 的整数表示。游戏中使用 24 小时制的时钟 ,所以一天中最早的时间是 00:00 ,最晚的时间是 23:59 。
104 0
|
索引
|
算法 Python
LeetCode 386. Lexicographical Numbers
给定一个整数 n, 返回从 1 到 n 的字典顺序。
84 0
LeetCode 386. Lexicographical Numbers
|
算法 Java
一和零(LeetCode 474)
一和零(LeetCode 474)
96 0