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

LeetCode 55. 跳跃游戏 | C 贪心算法最优解题解 题目描述题目级别中等给你一个非负整数数组nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标如果可以返回true否则返回false。示例 1:输入nums [2,3,1,1,4]输出true解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2:输入nums [3,2,1,0,4]输出false解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。 解题思路贪心算法 (范围覆盖视角)遇到跳跃类的问题很多人一开始会陷入误区纠结于“我现在到底该跳 1 步、2 步还是 3 步” 如果去穷举所有的跳法时间复杂度会爆炸。贪心算法的破局点在于不要纠结具体的跳跃步数而是看“覆盖范围”。我们可以把问题转化为只要我每次都尽力把“最远可达范围”向右扩展最后看这个范围能不能覆盖到终点就行了。核心运作机制我们维护一个变量r代表当前能够到达的最远下标。初始时我们在下标 0所以r 0。我们从左到右遍历数组中的每一个位置i前提条件当前位置i必须在我们的可达范围之内即i r。如果连位置i都走不到那更别提从i往下跳了。贪心扩展既然我能走到位置i那么我从位置i最远能跳到哪里呢当然是i nums[i]。我们尝试用这个新距离去刷新我们的最远可达范围rr max(r, i nums[i])。遍历结束后或者在遍历过程中只要r nums.size() - 1就说明终点在我们的覆盖范围之内返回true。如果遍历完了发现r还是没能达到终点说明半路卡死了返回false。 C 代码实现classSolution{public:boolcanJump(vectorintnums){intr0;// 记录当前能够到达的最远下标intnnums.size();// 遍历数组中的每一个位置for(inti0;in;i){// 只有当当前位置 i 能够被走到时才有可能从这里继续起跳if(ir){// 贪心策略用当前位置能跳到的最远距离去刷新全局的最远距离 rrmax(r,inums[i]);}else{// 优化剪枝如果当前位置 i 已经超出了最远可达范围 r// 说明遇到了无法跨越的 0后面永远走不到了直接跳出break;}}// 最后判断最远可达范围是否覆盖了最后一个下标returnrn-1;}};