企业官网建设流程全解析

用html5做的音乐网站,注册咨询公司,6黄页网站建设,泰安网站建设有哪些在刷LeetCode的过程中#xff0c;跳跃游戏 II#xff08;Jump Game II#xff09; 是一道经典的贪心算法题目#xff0c;要求我们以最少的跳跃次数到达数组的最后一个位置。这篇文章将详细讲解如何用贪心思想高效解决这个问题#xff0c;全程使用Java代码实现#xff0c;…在刷LeetCode的过程中跳跃游戏 IIJump Game II 是一道经典的贪心算法题目要求我们以最少的跳跃次数到达数组的最后一个位置。这篇文章将详细讲解如何用贪心思想高效解决这个问题全程使用Java代码实现思路清晰且时间复杂度最优。题目回顾给定一个长度为 n的非负整数数组 nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个下标。说明假设你总是可以到达数组的最后一个位置。解题思路贪心算法核心思想是每一步都选择能跳得最远的位置从而最小化跳跃次数。我们通过三个关键变量来实现这个思路mx记录当前位置能够到达的最远位置last记录上一次跳跃后到达的边界位置即上一次跳跃的终点ans记录跳跃的总次数。具体执行步骤遍历数组的前n-2个位置因为到达倒数第二个位置时最后一次跳跃必然能到终点对每个位置i计算i nums[i]当前位置能跳到的最远位置并更新mx为全局最大值当遍历到last上一次跳跃的边界时说明需要进行一次新的跳跃将last更新为当前能到达的最远位置mx跳跃次数ans加 1遍历结束后ans即为最少跳跃次数。Java代码实现class Solution { public int jump(int[] nums) { // 边界处理数组长度为1时无需跳跃 if (nums null || nums.length 1) { return 0; } int n nums.length; int mx 0; // 当前能到达的最远位置 int last 0; // 上一次跳跃的边界位置 int ans 0; // 跳跃次数 // 遍历到n-2即可因为到n-1已经是终点无需再跳 for (int i 0; i n - 1; i) { // 更新当前能到达的最远位置 mx Math.max(mx, i nums[i]); // 到达上一次跳跃的边界需要跳一次 if (i last) { last mx; // 新的边界是当前能到达的最远位置 ans; // 跳跃次数1 // 提前终止如果当前最远位置已经能到终点无需继续遍历 if (mx n - 1) { break; } } } return ans; } }代码解析边界处理如果数组长度小于等于 1直接返回 0起点就是终点无需跳跃变量初始化mx初始为 0初始能到达的最远位置last初始为 0初始跳跃边界是起点ans初始为 0初始跳跃次数核心遍历遍历范围是[0, n-2]因为当i n-1时已经到达终点无需处理每次计算i nums[i]并更新mx确保mx始终是当前能到达的最远位置当i到达上一次跳跃的边界last时说明必须跳一次更新last为新的最远边界mx并增加跳跃次数提前终止优化如果mx已经能覆盖到数组最后一个位置直接跳出循环减少不必要的遍历。复杂度分析时间复杂度O(n)仅需遍历数组一次每个元素最多被访问一次空间复杂度O(1)仅使用了常数个变量没有额外的空间开销。示例验证以nums [2,3,1,1,4]为例初始mx0, last0, ans0i0mx max(0, 02)2ilast更新last2ans1i1mx max(2, 13)4i≠lasti2mx max(4, 21)4ilast更新last4ans2此时mx4 4数组最后一个位置提前终止最终返回ans2符合预期。总结本题的核心是贪心策略每一步都选择能跳得最远的位置从而最小化跳跃次数通过mx记录最远可达位置、last记录跳跃边界能在一次遍历中完成计算时间复杂度最优Java 代码实现中加入了边界处理和提前终止优化进一步提升了代码的健壮性和效率。