LeetCode百题【跳跃游戏I,II】

题目描述

解法

贪心
- 每次都找能跳的最远的距离，最后跟数组长度比较
- 注意当前位置是否可达，才能更新最大长度
  - i++相当于一步一步走
  - maxLen相当于是跳着走
  - 如果i>=maxLen，说明该位置不可达

class Solution {
    public boolean canJump(int[] nums) {
        int maxLength=0;
        for (int i = 0; i < nums.length; i++) {
            //遍历数组
            if(i<=maxLength){
                //当前位置可以到达，才能动态更新最大长度
                maxLength=Math.max(maxLength,i+nums[i]);
            }//对当前最大长度前的数组的每一个元素求跳跃最大值
            if(maxLength>=nums.length-1){
                //如果长度已经超过了最大长度，直接跳出返回
                return true;
            }
        }
        return false;
    }
}

时间复杂度：O(n)

链接：55. 跳跃游戏 - 力扣（LeetCode） (leetcode-cn.com)
来源：力扣（LeetCode）

题目描述

解法

动态规划
跟上题类似，这次是要输出最小跳跃次数
遍历数组，时刻更新跳跃最大位置，同时对每次跳跃进行检查，查看是否达到上次跳跃的最大距离位置，是则计数器加一；
题目说我们总能达到最后的位置，因此数组遍历不需要遍历到最后一个元素，否则就无法达到最后一个位置，而且在边界刚好为最后位置时还会增加一次不必要的跳跃次数

class Solution {
    public int jump(int[] nums) {
        int maxPos=0;//记录当前的最大距离
        int step=0;//记录跳跃次数
        int border=0;//记录上次跳跃的最大距离
        for (int i = 0; i < nums.length-1; i++) {
            maxPos=Math.max(maxPos,i+nums[i]);//时刻更新最大距离
            if(i==border){//判断是否到达上次的跳跃最大距离
                step++;
                border=maxPos;
            }
        }
        return  step;
    }
}