辽阳专业网站开发公司设计师一般放作品的网站

辽阳专业网站开发公司,设计师一般放作品的网站,海城建设网站,铜仁公司做网站哈喽各位#xff0c;我是前端小L。 欢迎来到贪心算法专题第五篇#xff01; 想象一下#xff0c;你站在一个长长的走廊里#xff0c;地面上标着数字。每个数字代表你在当前位置最多能向前跳几步#xff08;你可以跳满#xff0c;也可以只跳一步#xff09;。 你的目标很…哈喽各位我是前端小L。欢迎来到贪心算法专题第五篇 想象一下你站在一个长长的走廊里地面上标着数字。每个数字代表你在当前位置最多能向前跳几步你可以跳满也可以只跳一步。 你的目标很简单判断你能否从起点一直跳到终点这道题容易陷入的一个误区是纠结于“我是跳 1 步好还是跳 2 步好”。 如果我们去模拟每一种跳法那这就变成回溯问题了复杂度会很高。贪心算法告诉我们别纠结具体跳几步只看你最远能覆盖到哪力扣 55. 跳跃游戏https://leetcode.cn/problems/jump-game/题目分析输入非负整数数组nums。规则nums[i]代表你在位置i的最大跳跃长度。目标判断是否能到达最后一个下标。例子 1[2, 3, 1, 1, 4]在下标 0数值2最远能覆盖到下标 2。我们走到下标 1数值3最远能覆盖到下标1 3 4。既然能覆盖到 4即终点那就返回true。例子 2[3, 2, 1, 0, 4]在下标 0数值3最远覆盖到 3。在下标 1数值2最远覆盖到1 2 3。在下标 2数值1最远覆盖到2 1 3。在下标 3数值0最远覆盖到3 0 3。无论如何都跨不过下标 3 这个坎到不了终点 4。返回false。核心思维维护“最大覆盖范围”我们要把问题转化为在这个覆盖范围内我能不能把覆盖范围进一步扩大Cover: 我们维护一个变量cover表示当前最远能走到的下标。初始时我们在起点cover 0。移动我们在0到cover的范围内遍历每一个位置i。注意我们只能在cover范围内移动如果你当前的位置i已经超过了cover说明你根本跳不到这儿游戏结束。更新对于遍历到的位置i我们计算这一跳能达到的最远距离i nums[i]。如果i nums[i]比当前的cover还要大我们就更新cover。判定一旦cover nums.size() - 1终点下标说明终点已经被覆盖了直接返回true。贪心策略不管我怎么跳我每一步都尽可能去更新最大的覆盖范围。只要终点在这个范围内我就赢了。算法流程cover 0。如果数组只有一个元素直接返回true。遍历i从0到nums.size() - 2其实只需要遍历到cover即可但为了代码简单我们用循环控制关键约束只有当i cover时我们才能站在i上。贪心更新cover max(cover, i nums[i])。提前结束如果cover nums.size() - 1返回true。循环结束后如果还没返回true说明到不了返回false。代码实现 (C)C#include vector #include algorithm using namespace std; class Solution { public: bool canJump(vectorint nums) { int cover 0; // 当前能覆盖到的最远下标 // 只有一个元素肯定能到 if (nums.size() 1) return true; // 注意i 只能在 cover 范围内移动 // 虽然循环写的是 i cover但 cover 是在动态增长的 for (int i 0; i cover; i) { // 更新覆盖范围 cover max(cover, i nums[i]); // 如果覆盖范围已经包含了终点 if (cover nums.size() - 1) { return true; } } // 跑完所有能跑的地方还是没覆盖到终点 return false; } };深度复杂度分析时间复杂度O(N)我们最多遍历数组一次。空间复杂度O(1)只需要一个变量cover。总结格局打开这道题展示了贪心算法的一种**“宏观视角”。 我们没有去纠结微观的“第一步跳几米第二步跳几米”而是直接审视“势能”**覆盖范围。只要我的势能足够大能罩住终点那具体怎么跳总归是有办法的。下一题预告跳跃游戏 II现在难度升级了 如果在上一题的基础上我保证一定能跳到终点但我要求你求出最少跳几步能到这时候“最大覆盖范围”这个单一指标就不够用了。我们需要两个指标“当前这一步最远能到哪”和“下一步最远能到哪”。 这道题是贪心算法中逻辑稍微复杂一点的题目准备好烧脑了吗下期见