建设工程敎育网网站,设计师学习网站,最新新闻事件今天国内大事2022,南京企业自助建站系统如果我们「贪心」地进行正向查找#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;
}
