做电商网站的上海公司,培训网站建设学校,网站接电话,欧派整装大家居装修公司加盟难度#xff1a;中等
题目#xff1a;
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处:
0 j nums[…难度中等
题目
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
0 j nums[i] i j n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums [2,3,0,1,4] 输出: 2
提示:
1 nums.length 104 0 nums[i] 1000 题目保证可以到达 nums[n-1]
解题思路
这道题目的解决方案可以通过贪心算法来实现核心思想是尽可能地让每次跳跃都能让我们到达更远的位置。 理解问题 给定一个非负整数数组nums数组中的每个元素表示你从当前位置可以跳跃的最大长度目标是到达数组的最后一个位置。要求找到到达最后一个位置所需的最小跳跃次数。 初始设置 ● 初始化jumps为0表示跳跃次数。 ● 初始化maxReach为0用来记录当前能到达的最远位置。 ● 初始化lastJumpPos为0记录上一次跳跃后能到达的最远位置。 遍历数组 遍历数组nums直到倒数第二个位置因为到达最后一个位置时自然完成任务无需额外跳跃。
在每次迭代中执行以下步骤 4. 更新最大可达位置计算当前位置i加上其对应的跳跃能力nums[i]取当前最大可达距离与这个值的最大者更新maxReach。这样可以确保maxReach始终记录着以当前位置为起点能跳到的最远位置。 5. 判断是否需要跳跃如果当前遍历到了上一次跳跃所能达到的最远位置即i lastJumpPos说明需要进行下一次跳跃。此时jumps加1并将lastJumpPos更新为当前的maxReach。这表示从当前位置开始至少需要一次跳跃来覆盖剩余的距离。
结果返回 遍历结束后jumps即为到达数组最后一个位置所需的最小跳跃次数。
为什么这种方法有效 这种方法充分利用了贪心策略每一步都试图做出最优选择即尽可能通过较少的跳跃覆盖更远的距离。通过维护一个不断向前推进的“最远可达边界”我们确保了在每次跳跃时都选择了最经济的方案从而减少了总的跳跃次数。 通过这种方式我们避免了暴力搜索或复杂的动态规划状态转移仅通过一次遍历就高效解决了问题。
JavaScript代码实现
function jump(nums) {let n nums.length;if (n 1) return 0; // 如果数组只有一个元素不需要跳跃// jumps表示跳跃次数maxReach表示当前能到达的最远位置lastJumpPos表示记录上一次跳跃后能到达的最远位置let jumps 0, maxReach 0, lastJumpPos 0;for (let i 0; i n - 1; i) {// 找到当前能跳到的最远位置maxReach Math.max(maxReach, i nums[i]);// 当前位置已经是上次跳跃能达到的最远位置需要再进行一次跳跃if (i lastJumpPos) {jumps;lastJumpPos maxReach; // 更新下次跳跃需要开始的位置}}return jumps;
}这段代码实现了题目要求的功能注意其中对特殊情况的处理以及如何通过贪心策略逐步推进跳跃的边界最终计算出最小的跳跃次数。
