LeeCode-02-跳跃游戏2

int jump(int nums, int numsSize) {
/
思路：
1.都是从0开始，所以maxlength = 0，每跳跃一次，遍历从index = 0到index = nums[i]，即这一次所能跳跃最大距离的所有的元素，判断跳跃这一 次所到达的最远距离，更新maxlength,以此类推，直至maxlength >= numsSize - 1
*/
int maxlength = nums[0];
int amount = 0;

if(numsSize == 1){
    return amount;
}
if (maxlength  >= numsSize - 1){
        return amount + 1;
    }

/*for(int i = 0; i < numsSize; i++){
    for(int j = i + 1; j <= i + nums[i]; j++){
        if(j == numsSize - 1){
            return amount + 1;
        }
        maxlength = maxlength > nums[j] + j ? maxlength : nums[j] + j;
    }
    amount = amount + 2;

    if (maxlength  >= numsSize - 1){
        return amount;
    }

    i = maxlength - 1;

}
return amount;*/

int i = 0;
while(maxlength  < numsSize - 1){
     for(int j = i + 1; j <= i + nums[i]; j++){
        if(j == numsSize - 1){
            return amount + 1;
        }
        maxlength = maxlength > nums[j] + j ? maxlength : nums[j] + j;
    }
    amount = amount + 2;
    i = maxlength;

}
return amount;

}

int jump(int* nums, int numsSize) {
int maxlength = nums[0];
long amount = 0; // 将 amount 的类型改为 long

if(numsSize == 1) {
    return amount;
}

int i = 0;
while (maxlength <= numsSize - 1) {
    for (int j = i + 1; j <= i + nums[i]; j++) {
        if (j == numsSize - 1) {
            return amount + 1;
        }
        maxlength = maxlength > nums[j] + j ? maxlength : nums[j] + j;
        if (maxlength >= numsSize - 1) {
            return amount + 2;
        }
    }
    amount = amount + 2;
    i = maxlength;
}

return amount;

}

从当前元素开始，遍历该元素值范围内能遍历的所有元素，判断选择哪个元素实现下一步走的最远
每遍历一个，计算一次选择该元素能到达的最远距离（下标加元素值）
eg:{2 3 1 1 4 6 2 1}
从2的下一个元素3开始遍历，选择3时，最远到达1 + 3 = 4，选择1时，最远能到达2 + 1 = 3，最远到达1，遍历结束，以4作为下一次遍历的开始
从4的下一个元素6开始遍历，选择6时，最远能到达5 + 6 = 11，选择2时…… !!!不足点 已经达到结束条件，还要继续循环

int max(int a, int b) {
return a > b ? a : b;
}
int jump(int* nums, int numsSize) {
int maxReach = 0; // 当前位置能到达的最远距离
int steps = 0; // 跳跃次数
int end = 0; // 当前跳跃范围的边界 上一次跳跃的的终点 第一次跳跃上一次的终点即为0

for (int i = 0; i < numsSize - 1; i++) {
    maxReach = max(maxReach, i + nums[i]);// 更新当前位置能到达的最远距离
    if (i == end) { // 如果到达当前跳跃范围的边界
        end = maxReach; // 更新下一次跳跃的边界为当前位置能到达的最远距离
        steps++; // 增加跳跃次数
    }
}
return steps;

}
eg:{2 3 1 1 4 6 2 1}