算法通关村第十七关 | 黄金挑战 | 跳跃游戏

发布时间:2023年12月17日

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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。