LeetCode题解之跳跃游戏

前言

创新互联公司一直在为企业提供服务，多年的磨炼，使我们在创意设计，全网营销推广到技术研发拥有了开发经验。我们擅长倾听企业需求，挖掘用户对产品需求服务价值，为企业制作有用的创意设计体验。核心团队拥有超过十多年以上行业经验，涵盖创意，策化，开发等专业领域，公司涉及领域有基础互联网服务成都移动机房、app软件定制开发、手机移动建站、网页设计、网络整合营销。

周五了，和大家玩个跳跃游戏

题目

给定一个非负整数数组 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  
  
  
  
            //如果达不到i位置，就直接返回false 
  
  
  
  
            if(k  
  
  
  
            k=Math.max(k,i+nums[i]); 
  
  
  
  
        } 
  
  
  
  
        return true; 
  
  
  
  
    } 
 
 
 

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

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

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

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

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

• 总是作出在当前看来最好的选择。
• 从局部的最优选择到整体最优解。

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

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

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

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

就等下次聊了，拜拜。

时间复杂度

O(n)

空间复杂度

O(1)

参考

https://blog.csdn.net/qq_42363032/article/details/103597453

https://leetcode-cn.com/problems/jump-game/submissions/

本文转载自微信公众号「码上积木」，作者积木zz 。转载本文请联系码上积木公众号。

当前文章：LeetCode题解之跳跃游戏
文章URL：http://www.mswzjz.cn/qtweb/news0/264750.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 贝锐智能