人力资源网站,像素时代网站建设手机站设计,wordpress 章节 插件,如何搭建门户网站本题与55. 跳跃游戏十分类似#xff0c;区别在于本题是要求出最小的跳跃次数。 在55. 跳跃游戏的框架上#xff0c;我们需要增加一些东西#xff1a;
既然要计算最小跳跃次数#xff0c;就需要用一个变量计数跳跃的次数#xff1b;需要一次前瞻#xff0c;来计算之后那次… 本题与55. 跳跃游戏十分类似区别在于本题是要求出最小的跳跃次数。 在55. 跳跃游戏的框架上我们需要增加一些东西
既然要计算最小跳跃次数就需要用一个变量计数跳跃的次数需要一次前瞻来计算之后那次跳跃可能的覆盖范围即需要两个变量curDistance和nextDistance分别记录当前覆盖距离的最远下标和下一步跳跃覆盖的最远距离下标在当前覆盖距离范围内的时候不断更新nextDistance直到到达最远的curDistance此时需要步数1把curDistanced的值更新为nextDistance并判断是否到达最后一个下标如果到达则break。
实现代码如下
class Solution {public int jump(int[] nums) {if(nums.length1) return 0;int curDistance0; //记录当前覆盖最远距离的下标int ans0;//记录步数int nextDistance0; //记录下一步覆盖最远距离的下标for(int i0;inums.length;i) {//更新下一步覆盖最远距离的下标nextDistanceMath.max(nextDistance, inums[i]);//若达到了当前覆盖最远距离的下标if(icurDistance) {ans;curDistancenextDistance;if(nextDistancenums.length-1) break;}}return ans;}
}
