题解 | #几步可以从头跳到尾#

题目描述
给你一个长度为n的数组A。
A[i]表示从i这个位置开始最多能往后跳多少格。
求从1开始最少需要跳几次就能到达第n个格子。

方法一：暴力求解

求解思路
对于本题目要求从1开始最少需要跳几次就能到达第n个格子。我们设置三个变量分别记录当前位置、最远跳跃位置和跳跃次数。每当当前位置和索引i相等时，将最远跳跃位置赋值给当前位置，跳跃次数加1，如果索引中没找到当前位置，则说明已经跳出数组A了。然后我们从第一个到最后n-1依次进行遍历，每经过之处都要求出最大可达到的位置。

图片说明

解题代码

import java.util.*;
public class Solution {
   public int Jump (int n, int[] A) {
    int mycount=0; // 跳的步数
    int index=0; // 当前位置
    int maxStep=0; // 最远可跳跃位置
    for(int i=0;i<n-1;i++)
    {
        maxStep=Math.max(maxStep,i+A[i]); // maxStep记录的每次可以达到的最大位置
        if(index>=n)
        {
            break; // 当前位置大于长度
        }
        if(index==i)
        {   //当前位置等于i时候
            index=maxStep; // 根据每处的maxStep,将当前位置换成局部最优
            mycount++; // 结果加1
        }
    }
    return mycount; // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：引入常数级变量，因此空间复杂度为 $O(1)$

方法二：贪心优化求解

求解思路
对于方法一，我们进行优化改进，我们用贪心的思想，从数组的后面开始往前面遍历，找到第一个能到达终点的位置，以此类推，最终找到起点即可。

图片说明

解题代码

import java.util.*;
public class Solution {
public int Jump (int n, int[] A) {
    int hystep = 0; // 步数
    // 数组为空，或者长度为1，返回0
    if (A == null || A.length == 0 || A.length == 1)
    {
        return 0;
    }
    int right = 0; // 声明相关变量
    int index = 0;
    int i = 0;
    int len = n-1;
    while(index < n && i < len)
    {   //找出最远能够到达的位置
        right = Math.max(right,i + A[i]); // 求出最远位置
        if (index == i)
        {
            index = right;
            ++hystep; // 步数+1
        }
        ++i;
    }
    return hystep; // 返回结果
}
}

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O(N )$
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$