14.跳跃游戏Ⅱ

题目简介

题目解答

解法一：贪心算法+动态规划

思路：想象你在玩大富翁，回合制游戏，随身带的钱决定你每回合最多可以走多少格，需要以最短的回合数到达终点。 格子里面的数字代表“钱”，每回合你需要停留在格子里休息得到补充的“钱”才能继续行走。 每次走到一个格子的时候，你需要估计预算在下一个回合能走多少格，哪个格子的钱最多，下一回合就去那个格子 。但是前面的格子里有多少钱有战争迷雾看不到，要到了才知道。 border 指本回合能走的最远位置，即钱用完了就不能继续往前了 maxPosition 就是钱

代码：

class Solution {
    public int jump(int[] nums) {
        // 记录当前能跳跃到的位置的边界下标
        int border = 0;
        // 记录在边界范围内，能跳跃的最远位置的下标
        int maxPosition = 0;
        // 记录所用步数
        int steps = 0;
        for(int i=0;i<nums.length-1;i++){
            // 继续往下遍历，统计边界范围内，哪一格能跳得更远，每走一步就更新一次能跳跃的最远位置下标
            // 其实就是在统计下一步的最优情况
            maxPosition = Math.max(maxPosition,nums[i]+i);
            // 如果到达了边界，那么一定要跳了，下一跳的边界下标就是之前统计的最优情况maxPosition，并且步数加1
            if(i==border){
                border = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}

代码注释很好的解释了每一行代码是干嘛的，看不懂的可以参考注释。

复杂度分析：

• 时间复杂度：O(n)，其中 n 是数组长度。
• 空间复杂度：O(1)。

题目链接

45. 跳跃游戏 II
感谢各位读者的阅读，本文章有任何错误都可以在评论区发表你们的意见，我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞，你的每一次鼓励都是作者创作的动力哦！😘