【Hot 100 刷题计划】 LeetCode 45. 跳跃游戏 II | C++ 贪心算法最优解题解

LeetCode 45. 跳跃游戏 II | C 动态规划与贪心 O(N) 双解法题解 题目描述题目级别中等给定一个长度为n的0 索引整数数组nums。初始位置在下标 0。每个元素nums[i]表示从索引i向后跳转的最大长度。返回到达n - 1的最小跳跃次数。测试用例保证可以到达n - 1。示例 1:输入:nums [2,3,1,1,4]输出:2解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。 解题思路与代码实现这道题求的是“最少步数”很自然会让人想到动态规划求极值。但如果想要追求极致的性能我们需要利用跳跃游戏的特殊性质使用贪心算法进行降维打击。 解法一动态规划 (思路直观易于理解)核心思想我们开辟一个dp数组dp[i]表示到达索引i需要的最少跳跃次数。初始状态dp[0] 0其余全部初始化为无穷大。遍历数组站在位置i时我们把它能跳到的所有未来位置j都更新一遍dp[j] min(dp[j], dp[i] 1)。 C 代码实现classSolution{public:intjump(vectorintnums){intnnums.size();vectorintdp(n,0x3f3f3f3f);// 初始化为无穷大dp[0]0;// 起点不需要跳跃for(inti0;in;i){// 遍历从当前位置 i 能够跳到的所有位置 jfor(intji1;jinums[i]jn;j){dp[j]min(dp[j],dp[i]1);}}returndp[n-1];}}; 解法二贪心算法 (时间 O(N)大厂面试终极解)既然是跳跃我们其实不需要挨个更新后面的格子。我们可以把跳跃看作是一次次扩大势力范围的过程。核心机制我们维护两个变量farthestfarthestfarthest(当前接触过的所有点中能跳到的最远距离) 和currentendcurrent_{end}currentend​(当前这一步所能覆盖的右边界)。遍历数组每经过一个格子iii我们就尝试用它去刷新farthestfarthestfarthest。灵魂转折点当我们遍历到currentendcurrent_{end}currentend​时说明“当前这一步的潜力已经全部榨干了”。为了继续往前走我们被迫必须进行下一次跳跃。于是跳跃次数jumpsjumpsjumps并把下一步的边界currentendcurrent_{end}currentend​更新为刚才探索到的最远距离farthestfarthestfarthest。 进阶 C 代码实现classSolution{public:intjump(vectorintnums){intjumps0;// 记录跳跃次数intcurrent_end0;// 记录当前这一跳的最远边界intfarthest0;// 记录在当前边界内能探索到的全局最远距离// 注意这里 i nums.size() - 1因为到了终点就不需要再跳了for(inti0;inums.size()-1;i){// 贪心在前进的过程中不断刷新能到达的最远距离farthestmax(farthest,inums[i]);// 如果走到了当前这一跳的边界if(icurrent_end){jumps;// 必须进行下一次跳跃current_endfarthest;// 更新下一跳的边界}}returnjumps;}};