LeetCode如何实现跳跃游戏

这篇文章给大家介绍LeetCode如何实现跳跃游戏,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。

十多年的杜尔伯特网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。成都营销网站建设的优势是能够根据用户设备显示端的尺寸不同,自动调整杜尔伯特建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。成都创新互联从事“杜尔伯特网站设计”,“杜尔伯特网站推广”以来,每个客户项目都认真落实执行。

题目

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1:输入:nums = [2,3,1,1,4] 输出:true

解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:输入:nums = [3,2,1,0,4] 输出:false

解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

分析

简单分析一下,由题目得出,要想到达最后一个下标,得满足两个条件:

  • 1、假设每个位置都能跳到,那么我们只需要遍历数组,看看有没有位置能直接通过这个位置上的数字跳到结尾。

比如[2,3,2,1,4],我们遍历数字,看看哪个位置可以跳到最后,可以发现第三个位置的数字是2,所以可以通过第三个位置跳到最后的下标,数组成立。

  • 2、上述假设成立的还有个条件就是 每个位置是否都能跳到。

比如[2,0,2,1,4],按照上面的逻辑,第三个位置是可以跳到最后下标。但是,第三个位置是否能到达呢?如果第三个位置都到不了,那又何谈最后的位置呢?在这个例子中,第一个位置为2,是可以跳到第三个位置的。

如果改成[1,0,2,1,4],第三个位置就到不了了。

结合上述分析,我们可以得出以下解法:

public boolean canJump(int[] nums) {         //能到达的最大位置k         int k =0;         //遍历数组         for(int i=0;i

也可以在每次获取k之后再判断一次,如果满足条件就直接返回,减少循环次数:

public boolean canJump(int[] nums) {         //能到达的最大位置k         int k =0;         //获取数组长度         int l = nums.length;         //遍历数组         for(int i=0;i= l-1) {              return true;             }         }         return false;     }

这种在到了某个位置,作出当前最好的选择 的算法一般称为贪心算法。

贪心算法的思路就是把问题分为若干个子问题,然后针对每个子问题进行局部求解,最终得到整个问题的解。

贪心算法主要有两个特点:

  • 总是作出在当前看来最好的选择。

  • 从局部的最优选择到整体最优解。

所以“贪心”的意思大概就是目光短浅,只看到到眼前的最好,而不会从整体的角度思考。

虽然不能保证最后的解法是最优的,但是这种办法确实是能够解决问题的,将大问题化解成小问题,小问题好好解决。

那有什么时候会有更好的解呢?这就引出 动态规划了。

动态规划的思想同样是解决子问题,但是每一步的选择都会依赖于相关的子问题解,所以有时候的复杂问题选择动态规划能有更好的解法,因为他对于子问题间的相关性更强。

关于LeetCode如何实现跳跃游戏就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。


本文题目:LeetCode如何实现跳跃游戏
转载来于:http://scyanting.com/article/gjeogd.html