拓冰网站定制 
文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接45.跳跃游戏 II2、题目描述二、个人思路整理1、思路分析核心思路题目要求用最少跳跃次数到达数组末尾且保证一定可达。不需要枚举具体跳到哪一个格子上而是维护当前跳跃步数所能覆盖的边界维护两个指针/边界cur_end当前这一步最远能到达的边界。farthest在当前步数能覆盖的所有位置中起跳下一步最多能触达的最远位置max(farthest, i nums[i])。什么时候增加跳跃次数遍历数组索引i ii。当i ii遍历到了cur_end即当前这一步能覆盖的极限说明必须进行下一次跳跃了step更新当前边界cur_end farthest遍历终止条件遍历到nums.length - 2即可即i n − 1 i n - 1in−1不需要遍历最后一个元素。因为如果遍历到n − 1 n - 1n−1且恰好i c u r _ e n d i cur\_endicur_end会导致无故多加一次跳跃步数而在n − 2 n-2n−2之前触发更新后farthest必然已经≥ n − 1 \ge n - 1≥n−1。2、解题代码classSolution{public:intjump(vectorintnums){intnnums.size();// 数组长度为 1 时初始就在终点无需跳跃if(n1){return0;}intsteps0;// 记录最少跳跃次数intcur_end0;// 当前这一步跳跃所能覆盖的最远右边界intfarthest0;// 从当前步内任意位置起跳下一步能触达的最远位置// 注意遍历到 n - 2 即可不需要遍历最后一个位置// 因为当到达 n - 2 时cur_end 已经被更新为覆盖或超过终点 (n - 1) 的位置for(inti0;in-1;i){// 实时维护在当前覆盖范围内起跳能达到的最远距离farthestmax(farthest,inums[i]);// 遍历到了当前步的边界说明必须迈出下一次跳跃if(icur_end){steps;// 步数增加cur_endfarthest;// 将边界更新为之前计算出的最远可达位置}}returnsteps;}};复杂度分析时间复杂度O ( n ) O(n)O(n)只需单次遍历数组。空间复杂度O ( 1 ) O(1)O(1)仅需常数级别的变量维护边界。三、知识风暴贪心算法Greedy Algorithm是本题的核心算法思想。它通过在每一步做出当前看起来最优的选择期望最终得到全局最优解。对于「跳跃游戏 II」这类具有最优子结构性质的问题贪心策略往往能以O ( n ) O(n)O(n)的复杂度高效求解。算法核心思想局部最优推导全局最优每一步都选择「能跳到最远位置」的起跳点从而用最少的步数覆盖整个数组。本题中维护当前步数能覆盖的边界cur_end当遍历到边界时再迈出下一步即可保证步数最少。无需回溯贪心算法不回溯、不枚举所有可能路径只关注当前可达范围内的最远位置因此时间复杂度仅为O ( n ) O(n)O(n)。与动态规划的区别动态规划需要记录每个位置的最少步数并逐一比较而贪心只维护「当前步的边界」和「下一步的最远位置」两个变量空间复杂度降为O ( 1 ) O(1)O(1)。常见对比贪心 vs 动态规划贪心算法时间复杂度O ( n ) O(n)O(n)空间复杂度O ( 1 ) O(1)O(1)。适合每一步的局部最优能直接推导全局最优的场景代码简洁高效。动态规划时间复杂度O ( n 2 ) O(n^2)O(n2)空间复杂度O ( n ) O(n)O(n)。适合需要枚举所有子问题、且局部最优不能直接决定全局最优的场景通用性更强但开销更大。共同点两者都依赖「最优子结构」性质。区别在于贪心只保留一个当前最优状态而动态规划需要维护一张状态表。贪心算法的设计思想核心思想在遍历过程中始终维护「当前这一步能到达的最远边界」和「从当前边界内任意位置起跳能到达的更远位置」。当遍历到当前边界时步数加一并将边界更新为更远位置。与本题的联系跳跃游戏 II 保证一定可达因此贪心策略不会出现「跳不到终点」的失败情况。我们只需在到达终点前不断扩展边界即可得到最少步数。注意事项贪心算法并不总是正确需要先证明「局部最优能推出全局最优」。本题中每一步都跳到最远位置不会比跳到较近位置更差因此贪心成立。使用要点边界变量cur_end记录当前步数能覆盖的最远下标farthest记录从当前覆盖范围内起跳能到达的更远下标。更新时机遍历到cur_end时步数加一并将cur_end更新为farthest表示进入下一跳。遍历范围只需遍历到n - 2避免在终点处多算一步。结果返回遍历结束后steps即为最少跳跃次数。算法变体与扩展跳跃游戏 ILeetCode 55只判断能否到达终点是本题的简化版同样可用贪心维护最远可达位置。跳跃游戏 IIILeetCode 1306从起点出发每次可向左或向右跳nums[i]步判断能否到达值为 0 的位置需用 BFS/DFS 而非贪心。加油站LeetCode 134环形路径上的贪心问题判断能否绕行一圈并找到起点。分发糖果LeetCode 135两次遍历的贪心策略分别处理左、右相邻关系。相关 LeetCode 例题55. 跳跃游戏贪心 最远可达位置134. 加油站贪心 环形路径135. 分发糖果贪心 两次遍历45. 跳跃游戏 II本题贪心 最少步数 【贪心算法】LC 45.跳跃游戏 II
文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接45.跳跃游戏 II2、题目描述二、个人思路整理1、思路分析核心思路题目要求用最少跳跃次数到达数组末尾且保证一定可达。不需要枚举具体跳到哪一个格子上而是维护当前跳跃步数所能覆盖的边界维护两个指针/边界cur_end当前这一步最远能到达的边界。farthest在当前步数能覆盖的所有位置中起跳下一步最多能触达的最远位置max(farthest, i nums[i])。什么时候增加跳跃次数遍历数组索引i ii。当i ii遍历到了cur_end即当前这一步能覆盖的极限说明必须进行下一次跳跃了step更新当前边界cur_end farthest遍历终止条件遍历到nums.length - 2即可即i n − 1 i n - 1in−1不需要遍历最后一个元素。因为如果遍历到n − 1 n - 1n−1且恰好i c u r _ e n d i cur\_endicur_end会导致无故多加一次跳跃步数而在n − 2 n-2n−2之前触发更新后farthest必然已经≥ n − 1 \ge n - 1≥n−1。2、解题代码classSolution{public:intjump(vectorintnums){intnnums.size();// 数组长度为 1 时初始就在终点无需跳跃if(n1){return0;}intsteps0;// 记录最少跳跃次数intcur_end0;// 当前这一步跳跃所能覆盖的最远右边界intfarthest0;// 从当前步内任意位置起跳下一步能触达的最远位置// 注意遍历到 n - 2 即可不需要遍历最后一个位置// 因为当到达 n - 2 时cur_end 已经被更新为覆盖或超过终点 (n - 1) 的位置for(inti0;in-1;i){// 实时维护在当前覆盖范围内起跳能达到的最远距离farthestmax(farthest,inums[i]);// 遍历到了当前步的边界说明必须迈出下一次跳跃if(icur_end){steps;// 步数增加cur_endfarthest;// 将边界更新为之前计算出的最远可达位置}}returnsteps;}};复杂度分析时间复杂度O ( n ) O(n)O(n)只需单次遍历数组。空间复杂度O ( 1 ) O(1)O(1)仅需常数级别的变量维护边界。三、知识风暴贪心算法Greedy Algorithm是本题的核心算法思想。它通过在每一步做出当前看起来最优的选择期望最终得到全局最优解。对于「跳跃游戏 II」这类具有最优子结构性质的问题贪心策略往往能以O ( n ) O(n)O(n)的复杂度高效求解。算法核心思想局部最优推导全局最优每一步都选择「能跳到最远位置」的起跳点从而用最少的步数覆盖整个数组。本题中维护当前步数能覆盖的边界cur_end当遍历到边界时再迈出下一步即可保证步数最少。无需回溯贪心算法不回溯、不枚举所有可能路径只关注当前可达范围内的最远位置因此时间复杂度仅为O ( n ) O(n)O(n)。与动态规划的区别动态规划需要记录每个位置的最少步数并逐一比较而贪心只维护「当前步的边界」和「下一步的最远位置」两个变量空间复杂度降为O ( 1 ) O(1)O(1)。常见对比贪心 vs 动态规划贪心算法时间复杂度O ( n ) O(n)O(n)空间复杂度O ( 1 ) O(1)O(1)。适合每一步的局部最优能直接推导全局最优的场景代码简洁高效。动态规划时间复杂度O ( n 2 ) O(n^2)O(n2)空间复杂度O ( n ) O(n)O(n)。适合需要枚举所有子问题、且局部最优不能直接决定全局最优的场景通用性更强但开销更大。共同点两者都依赖「最优子结构」性质。区别在于贪心只保留一个当前最优状态而动态规划需要维护一张状态表。贪心算法的设计思想核心思想在遍历过程中始终维护「当前这一步能到达的最远边界」和「从当前边界内任意位置起跳能到达的更远位置」。当遍历到当前边界时步数加一并将边界更新为更远位置。与本题的联系跳跃游戏 II 保证一定可达因此贪心策略不会出现「跳不到终点」的失败情况。我们只需在到达终点前不断扩展边界即可得到最少步数。注意事项贪心算法并不总是正确需要先证明「局部最优能推出全局最优」。本题中每一步都跳到最远位置不会比跳到较近位置更差因此贪心成立。使用要点边界变量cur_end记录当前步数能覆盖的最远下标farthest记录从当前覆盖范围内起跳能到达的更远下标。更新时机遍历到cur_end时步数加一并将cur_end更新为farthest表示进入下一跳。遍历范围只需遍历到n - 2避免在终点处多算一步。结果返回遍历结束后steps即为最少跳跃次数。算法变体与扩展跳跃游戏 ILeetCode 55只判断能否到达终点是本题的简化版同样可用贪心维护最远可达位置。跳跃游戏 IIILeetCode 1306从起点出发每次可向左或向右跳nums[i]步判断能否到达值为 0 的位置需用 BFS/DFS 而非贪心。加油站LeetCode 134环形路径上的贪心问题判断能否绕行一圈并找到起点。分发糖果LeetCode 135两次遍历的贪心策略分别处理左、右相邻关系。相关 LeetCode 例题55. 跳跃游戏贪心 最远可达位置134. 加油站贪心 环形路径135. 分发糖果贪心 两次遍历45. 跳跃游戏 II本题贪心 最少步数