0005 跳跃游戏Ⅱ

跳跃游戏Ⅱ

编号：0005

试题来源：leetcode

题目描述

给定一个非负整数数组，最初位于数组的第一个位置，数组中的每个元素代表你在该位置可以跳跃的最大长度。目标是使用最少的跳跃次数到达数组的最后一个位置。输出最少的跳跃次数。

假设你总是可以到达数组的最后一个位置

示例

输入：[2,3,1,1,4]

输出：2

解释：从下标为0跳到下标为1，再从下标为1跳至最后一个位置，共两步

解答算法

官方解答传送门

反向查找出发位置

算法思路

想要到达最后一个位置，那么可以找到所有可以一步跳至最后一个位置的位置，需要满足nums[i]+i >= nums.size()-1，所有满足这样条件的位置，我们选择i最小的，这样方便其他的位置到达i,这时候i就作为新的target，进行进一步的判断，一直到最后的target == 0，循环终止。

代码实现

我自己写的代码(c++)

class Solution {
public:
    int jump(vector<int>& nums) {
        int times = 0, target = nums.size() - 1, tempTarget = target;   //times是跳跃步数，target是当前要达到的目标位置下标，tempTarget是一个临时的target，最后进行比较决定取不取
        while (target != 0)    //当target为0的时候，循环终止，逆向搜索达到终点
        {
            int i;
            times++;          //每一次进入循环，都是新的一次跳跃，步数+1
            for (i = 0; i < target / 2 + 1; i++)   //从0开始遍历到满足条件
            {
                if (i + nums[i] >= target)        //若从头开始满足条件，那么直接赋给新的target，然后退出循环
                {
                    target = i;
                    break;
                }
                if (target - i - 1 + nums[target - i - 1] >= target)//这个相当于从后向前遍历，类似于双指针向中间进发
                    tempTarget = target - i - 1;
            }
            target = min(target, tempTarget);    //新的target取较小值
        }
        return times;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

该思路用c++写会超出时间限制，未通过测试。(不是太明白)

官方解答用java写的

class Solution {
    public int jump(int[] nums) {
        int position = nums.length - 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析

时间复杂度：整个过程中，有两层嵌套遍历，在最坏的情况下，也就是[1,1,1,1,1,1…]这样的情况下，遍历的总次数为${\sum }_{i=1}^n(n-i)$，因此$O(n^2)$

空间复杂度，只申请了常数个变量，没有用栈，因此$O(1)$

正向查找可到达的最大位置

思路分析

从左向右遍历数组，找到其能够到达的最大边界，例如最开始查找a[0]，将边界值end更新为a[0]所能到达的最远点，也就是a[0]+0，然后在遍历a[1..a[0]+0]的过程中，不断更新其下一步能够到达的最远点maxPos，，然后当到达边界end的时候，说明要进行下一步跳跃，step++，同时更新end为maxPos

代码实现

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxPos = 0, n = nums.size(), end = 0, step = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (maxPos >= i) {
                maxPos = max(maxPos, i + nums[i]);
                if (i == end) {
                    end = maxPos;
                    ++step;
                }
            }
        }
        return step;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析

时间复杂度：整个过程中，只遍历了一次数组，因此时间复杂度$O(n)$

空间复杂度：申请了常数个变量$O(1)$