尧图网页设计 
文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接55. 跳跃游戏2、题目描述二、个人思路整理1、思路分析核心思路维护最远可达位置核心观察如果你能到达某个下标i ii那么从起点到i ii之间的所有位置你都能到达。在下标i ii时你能到达的最远位置为i nums [ i ] i \text{nums}[i]inums[i]。因此我们只需要遍历数组动态更新全局最远可达下标max_reach。状态转移与边界初始状态max_reach 0。遍历每个下标i ii不可达判断如果当前下标i max_reach i \text{max\_reach}imax_reach说明前面的跳跃无论如何都够不到当前位置后续也绝不可能到达直接返回false。更新覆盖范围更新max_reach max(max_reach, i nums[i])。提前终止剪枝如果此时max_reach n - 1说明已经可以到达或超过最后一个下标直接返回true。如果能顺利遍历结束说明可以到达终点返回true。2、解题代码classSolution{public:boolcanJump(vectorintnums){intnnums.size();intmax_reach0;// 记录当前跳跃到达的最远下标for(inti0;in;i){// 如果当前位置已经超过了之前能到达的最远距离说明中间断档无法到达此处if(imax_reach){returnfalse;}// 贪心更新当前能够覆盖的最远下标当前下标 该处最大跳跃步数max_reachmax(max_reach,inums[i]);// 剪枝优化 如果最远可达位置已经覆盖或超过了终点下标直接返回成功if(max_reachn-1){returntrue;}}returntrue;}};复杂度分析时间复杂度O ( n ) O(n)O(n)只需线性遍历一次数组。空间复杂度O ( 1 ) O(1)O(1)仅需常数级别的变量维护状态。三、知识风暴贪心算法Greedy Algorithm是本题的核心算法思想。它通过每一步都做出当前看起来最优的选择来逐步逼近全局最优解。对于跳跃游戏而言我们不需要回溯所有可能的跳跃路径只需在遍历过程中动态维护「当前能到达的最远位置」即可判断能否抵达终点。理解贪心策略的正确性与边界处理对掌握本题至关重要。算法核心思想局部最优推导全局最优在每个下标i ii我们只关心「从当前位置能跳到的最远位置」i nums [ i ] i \text{nums}[i]inums[i]并不断更新全局最远可达下标max_reach。只要max_reach能覆盖到终点就一定存在一条可行路径。不可达的判定如果遍历到某个下标i ii时发现i max_reach i \text{max\_reach}imax_reach说明前面的所有跳跃都无法触及当前位置中间出现了「断档」后续也绝不可能到达直接返回false。与动态规划的区别动态规划需要记录每个位置是否可达并可能回溯多条路径而贪心只维护一个最远可达边界无需额外数组空间复杂度更低。常见对比贪心 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)。需要记录每个下标是否可达并逐一判断从前面的哪些位置能跳到当前位置适合需要统计路径数量或具体路径的场景。共同点两者都能判断能否到达终点。区别在于贪心只关心「最远能到哪」而动态规划关心「每个位置是否可达」。“贪心”设计思想核心思想利用「可达区间是连续的」这一性质——如果你能到达下标i ii那么起点到i ii之间的所有位置都能到达。因此只需维护一个不断右移的右边界max_reach无需关心区间内部的具体跳法。与本题的联系跳跃游戏只要求判断「能否到达终点」不要求给出具体跳跃路径。因此我们无需记录每一步怎么跳只需保证max_reach始终覆盖当前遍历到的下标即可。注意事项max_reach的更新必须取「当前最远」与「从i ii出发能到的最远位置」的较大值即max_reach max(max_reach, i nums[i])不能直接覆盖为i nums[i]否则可能丢失之前位置带来的更远覆盖。使用要点循环遍历用for (int i 0; i n; i)顺序遍历每个下标在循环内先判断是否可达再更新最远覆盖。不可达判断if (i max_reach) return false;必须放在更新之前因为当前位置不可达时后续位置更不可能到达。剪枝优化每次更新后判断if (max_reach n - 1) return true;一旦覆盖终点即可提前结束无需遍历完整个数组。结果返回若循环正常结束未提前返回说明所有下标都在可达范围内返回true。算法变体与扩展跳跃游戏LeetCode 55本题贪心维护最远可达位置的标准应用。跳跃游戏 IILeetCode 45在保证能到达终点的前提下求最少跳跃次数。需要额外维护「当前步的覆盖边界」与「下一步的最远覆盖」是贪心的进阶应用。跳跃游戏 IIILeetCode 1306从起点出发每次只能跳到i nums[i]或i - nums[i]且不能越界。由于跳跃方向不唯一贪心失效需改用 BFS 或 DFS 搜索。跳跃游戏 IVLeetCode 1345数组中相同值的下标可以互相跳跃求最少步数。需要结合哈希表分组 BFS 求解是图论建模的进阶应用。相关 LeetCode 例题55. 跳跃游戏贪心 维护最远可达位置45. 跳跃游戏 II贪心 最少跳跃次数1306. 跳跃游戏 IIIBFS/DFS 可达性搜索1345. 跳跃游戏 IV哈希表 BFS 最短路 【贪心算法】LC 55.跳跃游戏
文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接55. 跳跃游戏2、题目描述二、个人思路整理1、思路分析核心思路维护最远可达位置核心观察如果你能到达某个下标i ii那么从起点到i ii之间的所有位置你都能到达。在下标i ii时你能到达的最远位置为i nums [ i ] i \text{nums}[i]inums[i]。因此我们只需要遍历数组动态更新全局最远可达下标max_reach。状态转移与边界初始状态max_reach 0。遍历每个下标i ii不可达判断如果当前下标i max_reach i \text{max\_reach}imax_reach说明前面的跳跃无论如何都够不到当前位置后续也绝不可能到达直接返回false。更新覆盖范围更新max_reach max(max_reach, i nums[i])。提前终止剪枝如果此时max_reach n - 1说明已经可以到达或超过最后一个下标直接返回true。如果能顺利遍历结束说明可以到达终点返回true。2、解题代码classSolution{public:boolcanJump(vectorintnums){intnnums.size();intmax_reach0;// 记录当前跳跃到达的最远下标for(inti0;in;i){// 如果当前位置已经超过了之前能到达的最远距离说明中间断档无法到达此处if(imax_reach){returnfalse;}// 贪心更新当前能够覆盖的最远下标当前下标 该处最大跳跃步数max_reachmax(max_reach,inums[i]);// 剪枝优化 如果最远可达位置已经覆盖或超过了终点下标直接返回成功if(max_reachn-1){returntrue;}}returntrue;}};复杂度分析时间复杂度O ( n ) O(n)O(n)只需线性遍历一次数组。空间复杂度O ( 1 ) O(1)O(1)仅需常数级别的变量维护状态。三、知识风暴贪心算法Greedy Algorithm是本题的核心算法思想。它通过每一步都做出当前看起来最优的选择来逐步逼近全局最优解。对于跳跃游戏而言我们不需要回溯所有可能的跳跃路径只需在遍历过程中动态维护「当前能到达的最远位置」即可判断能否抵达终点。理解贪心策略的正确性与边界处理对掌握本题至关重要。算法核心思想局部最优推导全局最优在每个下标i ii我们只关心「从当前位置能跳到的最远位置」i nums [ i ] i \text{nums}[i]inums[i]并不断更新全局最远可达下标max_reach。只要max_reach能覆盖到终点就一定存在一条可行路径。不可达的判定如果遍历到某个下标i ii时发现i max_reach i \text{max\_reach}imax_reach说明前面的所有跳跃都无法触及当前位置中间出现了「断档」后续也绝不可能到达直接返回false。与动态规划的区别动态规划需要记录每个位置是否可达并可能回溯多条路径而贪心只维护一个最远可达边界无需额外数组空间复杂度更低。常见对比贪心 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)。需要记录每个下标是否可达并逐一判断从前面的哪些位置能跳到当前位置适合需要统计路径数量或具体路径的场景。共同点两者都能判断能否到达终点。区别在于贪心只关心「最远能到哪」而动态规划关心「每个位置是否可达」。“贪心”设计思想核心思想利用「可达区间是连续的」这一性质——如果你能到达下标i ii那么起点到i ii之间的所有位置都能到达。因此只需维护一个不断右移的右边界max_reach无需关心区间内部的具体跳法。与本题的联系跳跃游戏只要求判断「能否到达终点」不要求给出具体跳跃路径。因此我们无需记录每一步怎么跳只需保证max_reach始终覆盖当前遍历到的下标即可。注意事项max_reach的更新必须取「当前最远」与「从i ii出发能到的最远位置」的较大值即max_reach max(max_reach, i nums[i])不能直接覆盖为i nums[i]否则可能丢失之前位置带来的更远覆盖。使用要点循环遍历用for (int i 0; i n; i)顺序遍历每个下标在循环内先判断是否可达再更新最远覆盖。不可达判断if (i max_reach) return false;必须放在更新之前因为当前位置不可达时后续位置更不可能到达。剪枝优化每次更新后判断if (max_reach n - 1) return true;一旦覆盖终点即可提前结束无需遍历完整个数组。结果返回若循环正常结束未提前返回说明所有下标都在可达范围内返回true。算法变体与扩展跳跃游戏LeetCode 55本题贪心维护最远可达位置的标准应用。跳跃游戏 IILeetCode 45在保证能到达终点的前提下求最少跳跃次数。需要额外维护「当前步的覆盖边界」与「下一步的最远覆盖」是贪心的进阶应用。跳跃游戏 IIILeetCode 1306从起点出发每次只能跳到i nums[i]或i - nums[i]且不能越界。由于跳跃方向不唯一贪心失效需改用 BFS 或 DFS 搜索。跳跃游戏 IVLeetCode 1345数组中相同值的下标可以互相跳跃求最少步数。需要结合哈希表分组 BFS 求解是图论建模的进阶应用。相关 LeetCode 例题55. 跳跃游戏贪心 维护最远可达位置45. 跳跃游戏 II贪心 最少跳跃次数1306. 跳跃游戏 IIIBFS/DFS 可达性搜索1345. 跳跃游戏 IV哈希表 BFS 最短路