力扣45：跳跃游戏2题解

2024/10/25 16:22:56 来源：https://blog.csdn.net/zhilanguifang/article/details/141094881 浏览: 次关键词：力扣45：跳跃游戏2题解

题目链接：
https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-100-liked
参考的代码随想录里面的题解：

题目

在这里插入图片描述

难度

中等，标的是中等难度，而且我之前做过这道题，但是我没写出来，555~

思路：

这个题跟跳跃游戏1思路类似，但是难度要大很多。
整体也是贪心思想，但是在对每个位置贪心的时候还要记录下该位置能够覆盖到的所有下标下一跳能够到达的最远下标(也就是下一跳最远可以去到哪里)。而跳跃游戏1每次遍历到一个位置的时候只需要判断当前位置能够覆盖的最远下标。

代码：

class Solution {public int jump(int[] nums) {if(nums.length==1) return 0;int cur=0;int next=0;int step=0;for(int i=0;i<nums.length;i++){step++;cur=Math.max(next,nums[i]);if(cur>=nums.length-1) break;for(int j=i+1;j<=cur;j++){next=Math.max(next,j+nums[j]);if(next>=nums.length-1){step++;return step;}}}return step;}
}