45.Jump Game II---贪心---2018大疆笔试题

时间:2022-08-22 23:44:17

题目链接

题目大意:与55题类似,只是这里要求出跳数。

法一(借鉴):贪心。cur表示当前能到达的最远距离,pre表示上一次能到达的最远距离,每到一个位置更新一次最远距离cur,如果当前位置超过了上一次能到达的最远距离,则更新跳数和上一次能到达的最远距离。代码如下(耗时6ms):

     public int jump(int[] nums) {
int cur = 0, res = 0, pre = 0;
for(int i = 0; i < nums.length; i++) {
//如果当前位置超过了上一次可以达到的最远距离,更新跳数和上一次可达到的最远距离
if(i > pre) {
pre = cur;
res++;
}
//更新当前最远距离
cur = Math.max(cur, i + nums[i]);
}
return res;
}