企业官网建设流程全解析

苏州住房建设局网站,静态网站教程,沈阳手机网站,专业做蜂蜜的网站哈喽各位#xff0c;我是前端小L。 欢迎来到贪心算法专题第六篇#xff01; 这道题是跳跃游戏的进阶版。想象一下#xff0c;你还是要从起点跳到终点#xff0c;但这次我们要比拼速度#xff08;步数#xff09;。 关键在于#xff1a;什么时候进行“下一次跳跃”…哈喽各位我是前端小L。欢迎来到贪心算法专题第六篇 这道题是跳跃游戏的进阶版。想象一下你还是要从起点跳到终点但这次我们要比拼速度步数。 关键在于什么时候进行“下一次跳跃”比如[2, 3, 1, 1, 4]。起点是2覆盖范围是下标1~2。我们是跳到下标1数值3好呢还是跳到下标2数值1好呢如果跳到1下一跳最远能到134。如果跳到2下一跳最远能到213。贪心策略显然应该选下标1作为中间跳板因为它能带我们去更远的地方力扣 45. 跳跃游戏 IIhttps://leetcode.cn/problems/jump-game-ii/题目分析输入非负整数数组nums。保证可以到达nums[n-1]。目标最小跳跃次数。核心思维维护当前步数的“边界”我们需要两个关键变量来记录覆盖范围curDistance当前这一步最远能覆盖到的位置。nextDistance如果再多跳一步最远能覆盖到的位置。逻辑推演我们遍历每一个位置i在遍历过程中不断计算并更新nextDistance max(nextDistance, i nums[i])。这代表“如果我在当前范围内找一个跳板它最远能送我去哪”。当i走到了curDistance也就是走到了当前这一步的边界说明这一步的潜力耗尽了我们必须进行下一次跳跃了。此时steps。将curDistance更新为nextDistance把边界推得更远。检查新的curDistance是否覆盖了终点如果覆盖了直接结束。[Image visualization: Current reach boundary vs Next reach boundary]贪心策略不用纠结具体跳到哪个格子我只关心**“在当前这一步的范围内我能蓄力到的最远下一跳边界在哪里”**。当走到当前边界时果断切换到下一跳的边界。算法流程如果数组长度为 1直接返回 0不用跳。初始化curDistance 0nextDistance 0steps 0遍历i从0到nums.size() - 2注意这里只需要遍历到倒数第二个元素原因如果我们在倒数第二个位置或之前更新了边界且这个边界已经覆盖了终点那步数就已经加了。遍历最后一个元素没有意义我们已经在终点了不需要再起跳。在循环中更新nextDistance max(nextDistance, i nums[i])。如果i curDistance需要走下一步了steps。更新边界curDistance nextDistance。剪枝如果curDistance nums.size() - 1直接break虽然题目保证能到但加上这个判断逻辑更严谨。代码实现 (C)C#include vector #include algorithm using namespace std; class Solution { public: int jump(vectorint nums) { if (nums.size() 1) return 0; int curDistance 0; // 当前覆盖的最远距离下标 int nextDistance 0; // 下一步覆盖的最远距离下标 int steps 0; // 记录走的最大步数 // 关键点只遍历到 nums.size() - 2 // 因为如果走到倒数第二个还没结束意味着一定需要再跳一步才能到终点 // 如果遍历到 nums.size() - 1可能会多增加一次不必要的步数 for (int i 0; i nums.size() - 1; i) { // 贪心在当前覆盖范围内寻找能跳得最远的下一次位置 nextDistance max(nextDistance, i nums[i]); // 如果走到了当前步数的边界 if (i curDistance) { steps; // 必须再跳一步 curDistance nextDistance; // 更新边界 // 如果新的边界已经覆盖了终点提前结束 if (curDistance nums.size() - 1) { break; } } } return steps; } };深度辨析为什么循环只到size - 2这是一个容易出错的边界条件。 假设nums [2, 1]。i 0curDistance初始为 0。i curDistance触发更新steps变成 1。curDistance变成022(覆盖了终点)。循环结束。返回 1。正确。假如循环写成i nums.size()i会走到 1。此时curDistance是 2。虽然逻辑上i ! curDistance不会触发steps但如果之前的curDistance刚好卡在size-1上走到最后一个元素时再次触发更新就会多算一步。核心逻辑我们在当前点i是为了起跳。如果你已经站在终点了就不需要再起跳了。深度复杂度分析时间复杂度O(N)只需要遍历一次数组。空间复杂度O(1)只需要存储距离和步数。总结边界的艺术这道题展示了贪心算法中**“动态规划式”的思维虽然没用 DP 数组。 我们把跳跃过程看作是一层一层的波纹**第 1 步能到的范围是 A。第 2 步能到的范围是 B (由 A 中的点跳出来的)。我们只需要记录波纹的边缘每碰到一次边缘步数就 1。下一题预告如果数组中有负数怎么办 题目要求K 次取反后最大化数组和。 你可以选择任意一个元素取反乘 -1这个操作必须执行 K 次。 贪心策略很有趣先把绝对值最大的负数变成正数如果负数都变完了 K 还没用完那就对着最小的非负数反复取反消耗 K。下期见