跳跃游戏II

发表于 更新于 分类于 本文字数： 104 阅读时长 ≈ 1 分钟

ori维护上一起点的覆盖范围，cover维护最远覆盖。

j<=ori时，即此时j为上一起点应跳到的点。

而numsSize为1时，则在return时做特殊处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int jump(int* nums, int numsSize){
int cover=nums[0],step=1,j=1,ori=0;
while(cover<numsSize-1){
    if(j==numsSize){
        return 0;
    }
    if(nums[j]+j>=cover){
        if(j<=ori){
            cover=nums[j]+j;
        }
        else{
            ori=cover;
            cover=j+nums[j];
            step+=1;
        }
    }
    j+=1;
}
return (numsSize==1)?0:step;
}