leetcode刷题日记——跳跃游戏 II

[ 题目描述 ]：

[ 思路 ]：

• 题目要求在一个一定能达到数组末尾的跳跃数组中(见55题 跳跃游戏)，找出能够跳到末尾的最小次数
• 要求次数最少，那肯定是选取能选步数中最大的数。也就是在当前能够达到的距离中，选择能够达到的最远的步数，即跳跃一次；然后在新的最远的距离，再次探寻最大的距离；当能够达到的最远距离超过数组长度的时候，即跳跃完毕
• 运行如下

int jump(int* nums, int numsSize) {int jumps=0, len=0,maxlen=0;for (int i=0; i<numsSize-1;i++) {maxlen = fmax(maxlen, i+nums[i]); if (i == len) {jumps++; len = maxlen;}if(len>numsSize-1) break;}return jumps;
}

[ 优化 ]：

• 时间复杂度O(n)，空间复杂度O(1)

[ 官方题解 ]：

• 一、反向查找出发位置,贪心de 选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置。因此，我们可以从左到右遍历数组，选择第一个满足要求的位置。

int jump(int* nums, int numsSize) {int position = numsSize - 1;int steps = 0;while (position > 0) {for (int i = 0; i < position; i++) {if (i + nums[i] >= position) {position = i;steps++;break;}}}return steps;
}

• 二、正向查找可到达的最大位置，即上述方法