3.＜tag-贪心算法的简单应用＞lt.55. 跳跃游戏 + lt.45. 跳跃游戏 II dbc

lt.55. 跳跃游戏 [案例需求]

[思路分析]

[代码实现]

class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        int cover = nums[0];
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(cover, i + nums[i]);
            if (cover >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

另一种写法

class Solution {
    public boolean canJump(int[] nums) {
        //
        int len = nums.length;
        int longestDist = 0;
        //在覆盖范围内更新最远能够达到的距离(i <= longestDist)
        for(int i = 0; i <= longestDist; i++){   
            //最远到达的距离 = 当前位置 + 当前位置nums[i], 也就是覆盖距离
            longestDist = Math.max(longestDist, i + nums[i]);

            if(longestDist >= len - 1)return true;
        }
        return false;
    }
}

lt.45. 跳跃游戏 II [案例需求]

[思路分析] [代码实现]

class Solution {
    public int jump(int[] nums) {
        if(nums == null || nums.length <= 1){
            return 0;
        }
        //当前的跳跃次数
        int steps = 0;
        //当前跳跃次数情况下, 最远能够覆盖的距离
        int curStepsMaxReach = 0; 
        //当前跳跃次数+1情况下, 最远能够覆盖的距离
        int oneMoreStepMaxReach = nums[0];

        for(int i = 1; i < nums.length; i++){
            //如果目前的位置超过了curStepsMaxReach, 则意味着我必须要跳一步了, 即Step++;
            //同时由于step++了, curStepsMaxReach 就变成了 oneMoreStepMaxReach
            if(i > curStepsMaxReach){ // ?
                steps++;
                curStepsMaxReach = oneMoreStepMaxReach;
            }

            oneMoreStepMaxReach = Math.max(oneMoreStepMaxReach, i + nums[i]);
        }

        return steps;
    }
}