LeetCode题解：跳跃游戏

前言今天是周五，我们来和大家玩一个跳跃游戏题目给定一个非负整数数组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、假设每个位置都可以跳转到，那么我们只需要遍历数组，看有没有位置可以跳转到直接通过这个位置的Numbers跳转到最后。比如[2,3,2,1,4]，我们遍历数字看哪个位置可以跳到最后，可以发现第三个位置的数字是2，所以我们可以通过跳转到最后一个下标第三位，阵法成立。2.上述假设成立的另一个条件是每个位置是否可以跳转到。比如[2,0,2,1,4]，按照上面的逻辑，第三个位置可以跳到最后一个下标。但是，能达到第三的位置吗？如果第三个位置达不到，那么最后一个位置呢？本例中第一个位置是2，可以跳到第三个位置。如果改成[1,0,2,1,4]，第三个位置就达不到了。结合上面的分析，我们可以得到如下解决方案：publicbooleancanJump(int[]nums){//最大可以到达的位置kintk=0;//遍历数组for(inti=0;i=l-1){returntrue;}}returnfalse;}这种在某个位置做出当前最优选择的算法一般称为贪心算法。贪心算法的思想是将问题分解成若干个子问题，然后对每个子问题进行局部求解，最终得到整个问题的解。贪心算法有两个主要特点：总是在当前视图中做出最好的选择。从局部最优选择到整体最优解。所以“贪”大概就是短视的意思，只看到眼前最好的，没有站在全局的角度去思考。虽然不能保证最后的解是最优的，但是这种方法确实可以解决问题，把大问题化为小问题，把小问题解决好。那么什么时候会有更好的解决方案呢？这导致了动态规划。动态规划的思想也是为了解决子问题，但是每一步的选择都会依赖于相关子问题的解决，所以有时候动态规划对于复杂的问题可以有更好的解决方案，因为它更相关子问题之间的相关性。强大的。下次再说吧，再见。时间复杂度O(n)空间复杂度O(1)参考https://blog.csdn.net/qq_42363032/article/details/103597453https://leetcode-cn.com/problems/jump-game/submissions/本文转载来自微信公众号《积木上的代码》，作者积木zz。转载本文请联系代码上的积木公众号。