乐趣区

关于java:Leetcode-55-跳跃游戏

Leetcode 55 – 跳跃游戏 – 题解以及解析
<!–more–>

题目形容

给定一个非负整数数组,你最后位于数组的第一个地位。

数组中的每个元素代表你在该地位能够跳跃的最大长度。

判断你是否可能达到最初一个地位。

  • 示例 1:

    输出: [2,3,1,1,4]

    输入: true

    解释: 咱们能够先跳 1 步,从地位 0 达到 地位 1, 而后再从地位 1 跳 3 步达到最初一个地位。

  • 示例 2:

    输出: [3,2,1,0,4]

    输入: false

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

提交答案

class Solution {public boolean canJump(int[] nums) {
        int length = nums.length;
        int farPosition = 1;

        for (int i = 0; i < length && i < farPosition; i++) {if (nums[i] + i >= farPosition) {farPosition = nums[i] + i + 1;
            }
            if (farPosition >= length) {return true;}
        }
        return false;
    }
}

执行用时: 1 ms , 在所有 Java 提交中击败了 99.93% 的用户

内存耗费: 41.6 MB, 在所有 Java 提交中击败了 12.50% 的用户

题解反思

这题采纳 贪婪法 作为整体的解题思路。即:

  1. 保护一个最远可能达到的地位(farPosition)。
  2. 顺次遍历数组中的每一项,如果此时的索引小于最远可达到的地位,那么也就是说该项是能够达到的,但是否可能达到数据中的最初一项,还须要持续判断。
  3. 判断以后项的 索引和数值之和 是否大于最远可达到的地位,如果大于,则更新最远可达到区域为以后项的索引值和数值.
  4. 若以后可达到的地位大于数组的长度了,也就意味着能够间接达到数组中的最初一个地位,间接返回 true 就好,否则就返回 false

复杂度剖析

  • 工夫复杂度:O(n),最差的状况就是会顺次循环数组的所有元素。
  • 空间复杂度:O(1),通过 farPosition 记录最远可达到的地位,不须要额定的空间开销。

这道题整体上还是比较简单的,就先总结这么多,持续保持算法练习!

出处:Teamind https://teamind.co/ 欢送转载,也请保留这段申明。谢谢!

退出移动版