老男孩linux网站,网站开发的公司名称,电脑网络优化软件,免费动态图片素材网站如果我们「贪心」地进行正向查找#xff0c;每次找到可到达的最远位置#xff0c;就可以在线性时间内得到最少的跳跃次数。
例如#xff0c;对于数组 [2,3,1,2,4,2,3]#xff0c;初始位置是下标 0#xff0c;从下标 0 出发#xff0c;最远可到达下标 2。下标 0 可到达的…
如果我们「贪心」地进行正向查找每次找到可到达的最远位置就可以在线性时间内得到最少的跳跃次数。
例如对于数组 [2,3,1,2,4,2,3]初始位置是下标 0从下标 0 出发最远可到达下标 2。下标 0 可到达的位置中下标 1 的值是 3从下标 1 出发可以达到更远的位置因此第一步到达下标 1。
从下标 1 出发最远可到达下标 4。下标 1 可到达的位置中下标 4 的值是 4 从下标 4 出发可以达到更远的位置因此第二步到达下标 4。 在具体的实现中我们维护当前能够到达的最大下标位置记为边界。我们从左到右遍历数组到达边界时更新边界并将跳跃次数增加 1。
在遍历数组时我们不访问最后一个元素这是因为在访问最后一个元素之前我们的边界一定大于等于最后一个位置否则就无法跳到最后一个位置了。如果访问最后一个元素在边界正好为最后一个位置的情况下我们会增加一次「不必要的跳跃次数」因此我们不必访问最后一个元素。
作者力扣官方题解 代码
int jump(int* nums, int numsSize)
{int max 0;int i 0,steps 0;int end0;for (i 0; i numsSize-1; i){ max max (nums[i] i) ? (nums[i] i) : max;//最远能到达的位置if (iend){end max;steps;}}return steps;
}
