1.跳跃游戏
原题：力扣55.
逐步判断下一步的覆盖范围，根据范围去推断是否能到达终点，不用计较每一步走到哪里。
public boolean canJump(int[] nums) {
// 题目规定 nums 长度大于等于1
if (nums.length == 1) {
return true;
}
int cover = 0;
// for 循环的终止条件是不断变化的，模拟覆盖范围的变化
for (int i = 0; i <= cover; i++) {
cover = Math.max(cover, i + nums[i]);
if (cover >= nums.length - 1) {
return true;
}
}
return false;
}
2.最短跳跃游戏
原题：力扣45.
在上一题的基础上要求最少的步数。
题目给定测试用例一定能到达终点，所以只需返回步数。
把处于同一步数（steps）的不同位置能前往的位置画一个范围，用 left 和 right 包围起来。
public int jump(int[] nums) {
// 记录覆盖范围右端
int right = 0;
// 能跳的最远的地方，用于更新双指针包围的范围，给 right 赋值
int maxPosition = 0;
// 记录步数
int steps = 0;
// 记录覆盖范围左端，不断遍历右移
for (int left = 0; left < nums.length - 1; left++) {
// 数组中每一个位置能走的最远距离和 maxPosition 比较
maxPosition = Math.max(maxPosition, nums[left] + left);
if (left == right) {
right = maxPosition;
steps++;
}
if (right >= nums.length - 1) {
return steps;
}
}
return steps;
}
如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤
个人主页：星不易 ❤
算法通关村专栏：不易|算法通关村 ❤
