力扣每日一练(24-1-20)
Python:
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
maxReach, step, end = nums[0], 1, nums[0]
for i in range(1, n):
if i > end:
step += 1
end = maxReach
maxReach = max(maxReach, nums[i] + i)
return step
maxReach
、step
和 end
有以下的作用:
-
maxReach
:这个变量用来记录从当前位置开始,我们能够跳到的最远的位置。在每一步中,我们都会更新maxReach
为当前的maxReach
和nums[i] + i
中的较大值,其中i
是当前的位置,`nums[i] 是当前位置的值,也就是我们能够跳跃的最大长度。 -
step
:这个变量用来记录我们需要跳跃的次数。每当我们到达当前跳跃的结束位置时,我们就知道我们必须进行另一次跳跃,所以step
会增加 1。 -
end
:这个变量用来记录当前跳跃的结束位置。每当我们到达end
,我们就知道我们必须进行另一次跳跃,并更新end
为maxReach
,也就是我们能够到达的最远位置。
这三个变量共同帮助我们确定在每一步中应该跳到哪个位置,以便我们能够以最少的跳跃次数到达数组的最后一个位置。
C#
public int Jump(int[] nums) {
int n = nums.Length;
if (n < 2) {
return 0;
}
int maxReach = nums[0], step = 1, end = nums[0];
for (int i = 1; i < n; i++) {
if (i > end) {
step++;
end = maxReach;
}
maxReach = Math.Max(maxReach, nums[i] + i);
}
return step;
}
我们首先检查 nums
的长度是否小于 2,如果是,那么就返回 0,因为我们已经在目标位置。然后,我们初始化 maxReach
、step
和 end
为 nums[0]
,并从 nums
的第二个元素开始遍历。如果我们到达了当前跳跃的结束位置,那么就增加 step
,并更新 end
为 maxReach
。然后,我们更新 maxReach
为当前的 maxReach
和 nums[i] + i
中的较大值。最后,我们返回 step
作为结果。
原文地址:https://blog.csdn.net/weixin_47420447/article/details/135709906
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!