算法通关村第十七关 | 黄金挑战 | 跳跃游戏
2023-12-16 07:16:44
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;
}
如果对您有帮助,请点赞关注支持我,谢谢!?
如有错误或者不足之处,敬请指正!?
个人主页:星不易 ?
算法通关村专栏:不易|算法通关村 ?
文章来源:https://blog.csdn.net/m0_57130776/article/details/134923754
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!