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. 连接词
48 0
|
6月前
|
C++ Python
leetcode-283:移动零
leetcode-283:移动零
29 0
|
6月前
LeetCode
LeetCode
38 0
|
6月前
|
算法
leetcode:389. 找不同
leetcode:389. 找不同
27 0
leetcode 827 最大人工岛
leetcode 827 最大人工岛
58 0
leetcode 827 最大人工岛
LeetCode 389. 找不同
给定两个字符串 s 和 t,它们只包含小写字母。
71 0
LeetCode 283. 移动零
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
85 0
|
C++ Python
LeetCode 771. Jewels and Stones
LeetCode 771. Jewels and Stones
79 0
|
算法
leetcode第47题
基本上都是在上道题的基础上改出来了,一些技巧也是经常遇到,比如先排序,然后判断和前一个是否重复。利用 Hash 去重的功能。利用原来的存储空间隐藏掉数据,然后再想办法还原。
leetcode第47题
|
算法
leetcode第40题
会发现出现了很多重复的结果,就是因为没有跳过重复的 1。在求 opt [ 1 ] 的时候就变成了 [ [ 1 ],[ 1 ] ] 这样子,由于后边求的时候都是直接在原来每一个列表里加数字,所有后边都是加了两次了。
leetcode第40题