企业官网建设流程全解析

引言

这两道题属于贪心经典题型，核心都是基于数组元素代表最大跳跃长度，两道题题干相近，但目标不同：一题判断是否可达终点，一题求到达终点的最小跳跃次数。

基础篇：跳跃游戏 I

约束：起始在下标 0；nums [i] 代表当前位置向后最大跳跃距离；判断是否能够到达最后一个下标。

思路 1：正向贪心

方法：维护max_reach，记录当前能跳到的最远下标。遍历数组，不断更新最远可达位置；若遍历到某个位置i > max_reach，说明无法到达该位置，直接返回 false；若max_reach >= n-1可提前返回 true。

复杂度：时间 (O(n))，空间 (O(1))

class Solution { public: bool canJump(vector<int>& nums) { int max_reach = 0; int n = nums.size(); for(int i = 0; i < n; i++){ if(i > max_reach) return false; // 当前位置不可达 max_reach = max(max_reach, i + nums[i]); if(max_reach >= n-1) return true; } return true; } };

思路 2：动态规划

方法：dp[i]表示下标i是否可达。初始化dp[0]=true；遍历每个位置，如果当前位置可达，则标记它后续能跳到的位置全部可达。

复杂度：时间 (O(n^2))，空间 (O(n))，大数据会超时，仅理解用。

bool canJump(vector<int>& nums) { int n = nums.size(); vector<bool> dp(n, false); dp[0] = true; for(int i=0;i<n;i++){ if(!dp[i]) continue; for(int j=1;j<=nums[i];j++){ if(i+j >= n-1) return true; dp[i+j] = true; } } return dp[n-1]; }

进阶篇：跳跃游戏 II

约束：起始在下标 0；nums [i] 代表当前位置向后最大跳跃距离；保证一定可以到达终点，求到达最后下标的最小跳跃次数。

思路 1：区间贪心

方法：维护 3 个变量：当前区间边界end、全局最远可达位置max_reach、跳跃次数step。遍历到区间边界end时，代表必须起跳一次，更新边界为全局最远位置。

复杂度：时间 (O(n))，空间 (O(1))

class Solution { public: int jump(vector<int>& nums) { int n = nums.size(); if(n == 1) return 0; int step = 0; int end = 0; int max_reach = 0; for(int i = 0; i < n-1; i++){ max_reach = max(max_reach, i + nums[i]); if(i == end){ // 走到区间边界，必须起跳 step++; end = max_reach; } } return step; } };

思路 2：反向贪心

方法：从终点向前搜索，找到最靠左的、能够跳到当前终点的位置；更新终点为此位置，跳跃次数 + 1；直到终点回到下标 0。

复杂度：时间 (O(n^2))，空间 (O(1))

int jump(vector<int>& nums) { int pos = nums.size()-1; int step = 0; while(pos > 0){ // 从左往右找第一个能跳到pos的下标 for(int i=0; i<pos; i++){ if(i + nums[i] >= pos){ pos = i; step++; break; } } } return step; }

总结

I：只关心能不能到达 → 贪心维护最远可达下标

II：求最少跳跃次数 → 区间贪心，到达区间边界才计数