【力扣100题】96.跳跃游戏 II

题目描述

给定一个长度为n的数组nums，初始位置在下标 0。每个元素nums[i]表示从索引i向后跳转的最大长度。返回到达n - 1的最小跳跃次数。测试用例保证可以到达n - 1。

示例 1：

输入：nums = [2,3,1,1,4] 输出：2 解释：从下标 0 跳到下标 1（跳 1 步），再从下标 1 跳到下标 4（跳 3 步）

示例 2：

输入：nums = [2,3,0,1,4] 输出：2

解题思路总览

算法一：动态规划

思路

dp[i]表示到达位置 i 所需的最小跳跃次数。转移方程：

• dp[i] = min(dp[j] + 1)，其中 j < i 且 j + nums[j] >= i

代码

classSolution{public:intjump(vector<int>&nums){intn=nums.size();vector<int>dp(n,INT_MAX);dp[0]=0;for(inti=1;i<n;i++){for(intj=0;j<i;j++){if(j+nums[j]>=i){dp[i]=min(dp[i],dp[j]+1);}}}returndp[n-1];}};

算法流程

输入: nums = [2,3,1,1,4], n=5 dp[0] = 0 i=1: j=0, 0+nums[0]=0+2=2 >= 1, dp[1]=dp[0]+1=1 dp[1]=1 i=2: j=0, 0+2=2 >= 2, dp[2]=dp[0]+1=1 j=1, 1+3=4 >= 2, dp[2]=min(1, dp[1]+1=2)=1 dp[2]=1 i=3: j=0, 0+2=2 < 3, 不满足 j=1, 1+3=4 >= 3, dp[3]=dp[1]+1=2 j=2, 2+1=3 >= 3, dp[3]=min(2, dp[2]+1=2)=2 dp[3]=2 i=4: j=0, 0+2=2 < 4, 不满足 j=1, 1+3=4 >= 4, dp[4]=dp[1]+1=2 j=2, 2+1=3 < 4, 不满足 j=3, 3+1=4 >= 4, dp[4]=min(2, dp[3]+1=3)=2 dp[4]=2 输出: 2

复杂度分析

算法二：BFS

思路

从起点开始 BFS，每一层代表一次跳跃，遍历当前层所有能到达的位置，更新下一层的可达范围。

代码

classSolution{public:intjump(vector<int>&nums){intn=nums.size();intans=0;intcurEnd=0;// 当前跳跃的边界intnextEnd=0;// 下一层跳跃的边界for(inti=0;i<n-1;i++){nextEnd=max(nextEnd,i+nums[i]);if(i==curEnd){ans++;curEnd=nextEnd;}}returnans;}};

算法流程

输入: nums = [2,3,1,1,4], n=5 初始: ans=0, curEnd=0, nextEnd=0 i=0: nextEnd = max(0, 0+2) = 2 i == curEnd(0), ans++, ans=1, curEnd = nextEnd(2) 当前层结束，跳跃次数=1 i=1: nextEnd = max(2, 1+3) = 4 i != curEnd(2), 不做处理 i=2: nextEnd = max(4, 2+1) = 4 i != curEnd(2), 不做处理 i=3: nextEnd = max(4, 3+1) = 4 i == curEnd(2), ans++, ans=2, curEnd = nextEnd(4) 当前层结束，跳跃次数=2 循环结束（i 只到 n-2=3，因为最后一步不需要再跳） curEnd(4) >= n-1(4)，说明已经能到达终点 输出: ans = 2

复杂度分析

算法三：贪心（反向查找）

思路

从后往前找，每一步找「能跳到当前位置」的最左边的位置，直到起点。

代码

classSolution{public:intjump(vector<int>&nums){intans=0;intpos=nums.size()-1;while(pos>0){for(inti=0;i<pos;i++){if(i+nums[i]>=pos){pos=i;ans++;break;}}}returnans;}};

算法流程

输入: nums = [2,3,1,1,4], n=5, pos=4, ans=0 第一步: pos=4, 从 i=0 开始找能跳到 4 的位置 i=0: 0+2=2 < 4, 不满足 i=1: 1+3=4 >= 4, pos=1, ans=1 找到，跳到 pos=1 第二步: pos=1, 从 i=0 开始找能跳到 1 的位置 i=0: 0+2=2 >= 1, pos=0, ans=2 找到，跳到 pos=0 pos=0, 循环结束 输出: ans = 2

复杂度分析

算法四：贪心（正向，最优解）

思路

维护curEnd（当前跳跃可达的边界）和nextEnd（下一次跳跃可达的最远位置）。当遍历到curEnd时，说明需要再跳一次，ans++并更新curEnd = nextEnd。

代码

classSolution{public:intjump(vector<int>&nums){intans=0;intcurEnd=0;// 当前跳跃的右边界intnextEnd=0;// 下一步能到的最远位置for(inti=0;i<nums.size()-1;i++){nextEnd=max(nextEnd,nums[i]+i);if(i==curEnd){ans++;curEnd=nextEnd;}}returnans;}};

算法流程

输入: nums = [2,3,1,1,4] 初始: ans=0, curEnd=0, nextEnd=0, n=5 i=0: nextEnd = max(0, 0+2) = 2 i(0) == curEnd(0), ans++ (ans=1), curEnd = nextEnd(2) 第一次跳跃完成 i=1: nextEnd = max(2, 1+3) = 4 i(1) != curEnd(2), 不做处理 i=2: nextEnd = max(4, 2+1) = 4 i(2) != curEnd(2), 不做处理 i=3: nextEnd = max(4, 3+1) = 4 i(3) == curEnd(2), ans++ (ans=2), curEnd = nextEnd(4) 第二次跳跃完成 循环结束（i 只到 n-2=3，因为最后一步不需要再跳） 输出: ans = 2

复杂度分析

复杂度对比总结

贪心正向核心思想

nums = [2,3,1,1,4] 遍历过程： +-------------------------------------------------------------+ | 下标 | 能跳到的最远 | curEnd | nextEnd | 跳跃次数 | | | 0 | 2 | 0 | 2 | 1 | 第一次跳 | | 1 | 4 | 2 | 4 | | 更新next | | 2 | 3 | 2 | 4 | | | | 3 | 4 | 2 | 4 | 2 | 第二次跳 | | 4 | - | - | - | | | +-------------------------------------------------------------+ 核心思想： - curEnd：当前这一次跳跃能达到的最远边界 - nextEnd：下一次跳跃能达到的最远边界 - 当 i 到达 curEnd 时，必须再跳一次 - 每次跳跃 ans++

面试追问 FAQ

相关题目

总结