【Leetcode 每日一题 - 扩展】45. 跳跃游戏 II

devtools/2024/12/23 0:35:00/

问题背景

给定一个长度为 $n$ 的 $0$ 索引整数数组 $n u m s$ 。初始位置为 $n u m s [0]$ 。
每个元素 $n u m s [i]$ 表示从索引 $i$ 向前跳转的最大长度。换句话说，如果你在 $n u m s [i]$ 处，你可以跳转到任意 $n u m s [i + j]$ 处：

$\le j \le nums[i]$
$\lt n$

返回到达 $n u m s [n - 1]$ 的最小跳跃次数。生成的测试用例可以到达 $n u m s [n - 1]$ 。

数据约束

$\le nums.length \le 10 ^ 4$
$\le nums[i] \le 1000$
题目保证可以到达 $n u m s [n - 1]$

解题过程

经典跳跃问题，可以用造桥场景来理解。
题目描述不是很好懂，其实是在每个位置 $i$ 上，可以在 $[1, n u m s [i]]$ 中选择一个距离 $j$ 并从当前位置移动到 $i + j$ 这个位置上。
解决方案是一个比较明显的贪心算法，每次选择能够到达的最远位置来造桥，能尽可能地减少操作次数。
注意要到达的位置是 $n - 1$ ，所以循环应该在 $i < n - 1$ 处结束。通过样例的输出可能会想到在结果上进行修正，但这样是不对的，因为最后造额外的桥是有条件的。
由于题目保证了一定能够实现目标，不需要再做额外的处理，不保证一定能够全覆盖的情形，参见灌溉花园的最少水龙头数目。

具体实现

class Solution {public int jump(int[] nums) {int res = 0;int curEnd = 0;int nextEnd = 0;// 由于到达的位置是 n - 1，那么在 n - 2 的位置上有可能进行最后一次操作for(int i = 0; i < nums.length - 1; i++) {// 在每个位置上更新能够到达的最远边界nextEnd = Math.max(nextEnd, i + nums[i]);// 如果当前已经不能继续往前走，那么在这个位置上造桥if(i == curEnd) {curEnd = nextEnd;res++;}}return res;}
}