算法设计与分析-Week3

发表于 | 更新于

Jump Game II

题目描述

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.

Example 1:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note: You can assume that you can always reach the last index.

解题思路

题目所求的是从起点到终点的最少跳跃次数，数组的每一个整数表示的是当前位置所能跳跃的最大距离。这里我首先将起点所能到达的最远距离设为furthest，并用变量r保存这个最远点，由于在起点与r之间的每一个点我都可以跳，因此我对这中间的点进行遍历，根据这些点的最远跳跃距离找到第二次跳跃所能到达的最远点furthest，当遍历到达第一次跳跃的最远点r时，跳跃次数加一，此时肯定发生了一次跳跃，将r更新为最远点furthest，第二次跳跃的落点肯定在furthest之前；重复上面的操作，找到第三次及第n次跳跃所能到达的最远点furthest，当最远点比终点远时，再多跳一步即可到达终点。整个算法只需要遍历一次数组，因此时间复杂度为\(O(n)\)。

源代码

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