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/ 欢送转载，也请保留这段申明。谢谢！