题解 | #跳跃游戏(二)#

题意整理

• 给定一个非负数组，数组的值记录当前位置所能跳的最大步数。
• 从起始位置开始，如果能跳到结束位置，则可以获取每个位置对应值的积分。
• 如果不能到结束位置，则不能获得积分，返回-1。

方法一（暴力循环）

1.解题思路

• 首先定义一个积分数组，用于记录对应结束点的最大积分。
• 初始化0位置积分为对应数组的值，其它位置初始化积分为-1。
• 遍历整个数组，然后再遍历当前位置所能到达的所有位置，跟新对应位置的积分值。
• 最后终点位置的积分即是所求的最大积分。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int maxJumpGrade (int[] nums) {
        //数组长度
        int n=nums.length;
        //如果长度为0，直接返回-1
        if(n==0) return -1;
        //用于记录对应结束点的最大积分
        int[] grade=new int[n];
        //初始化为-1
        Arrays.fill(grade,-1);
        //初始化0位置的最大积分
        grade[0]=nums[0];
        for(int i=0;i<n;i++){
            //如果为-1，说明不能由起始点跳到该位置
            if(grade[i]==-1) continue;
            //遍历所有可以跳到的位置，跟新积分值
            for(int j=1;j<=nums[i];j++){
                //如果超过n，直接结束当前循环
                if(i+j>=n) break;
                grade[i+j]=Math.max(grade[i+j],grade[i]+nums[i+j]);
            }
        }
        return grade[n-1];
    }
}

3.复杂度分析

• 时间复杂度：假设数组长度为n，每一个位置对应值的最大值为m，则两层循环最多执行$n\ast mn*m$次，所以时间复杂度是$O(n\ast m)O(n*m)$。
• 空间复杂度：需要额外大小为n的积分数组，所以空间复杂度为$O(n)O(n)$。

方法二（贪心）

1.解题思路

我们可以考虑从后往前遍历数组，如果当前位置$ii$可以到达终点位置，同时当前位置$jj$也可以到达终点位置（），假设我们将$ii$替换为新的终点位置，则累计过程中会加上$nums[i]+nums[j]nums[i]+nums[j]$对应的积分(因为$nums[j]+j>=nnums[j]+j>=n$，所以$nums[j]+j>=inums[j]+j>=i$一定成立，从$jj$位置也一定可以跳到$ii$位置)，如果直接将$jj$替换为新的终点位置，则累计过程中会加上$nums[j]nums[j]$对应的积分，所以将新的终点替换为$ii$位置是最佳的决策。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int maxJumpGrade (int[] nums) {
        //数组长度
        int n=nums.length;
        //数组长度为0，直接返回-1
        if(n==0) return -1;
        //当前积分
        int grade=nums[n-1];
        
        //当前跳跃的终点位置
        int curEnd=n-1;
        for(int i=n-2;i>=0;i--){
            //只要能跳到curEnd位置，直接跟新积分值以及终点位置
            if(i+nums[i]>=curEnd){
                grade+=nums[i];
                curEnd=i;
            }
        }
        //如果最后能跟新到起始位置，直接返回grade，否则返回-1
        return curEnd==0?grade:-1;
    }
}

3.复杂度分析

• 时间复杂度：只需一层循环，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：不需要额外的内存空间，所以空间复杂度为$O(1)O(1)$。