45. 跳跃游戏 II

此题55. 跳跃游戏的进阶版

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

按照前面题的思路，依然是从后往前搜索。每次搜索能跳到当前位置的最远位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int jump(vector<int>& nums) {
        // 选择当前能跳到当前点的最远的距离。
        int max_index = nums.size()-1;
        int current_max_index = max_index;
        int step = 0;
        //当没有到达开头位置，进行循环。
        while(max_index > 0){
            //记录能跳到当前数组的最前面的点。
            for(int i = max_index-1; i >= 0; i--){
                if(i + nums[i] >= max_index){
                    current_max_index = i;
                }
            }
             //更新能跳的最远的点。
            max_index = current_max_index;
            //步数更新
            step++;
        }
        return step;
    }
    
};

用了两层循环，发现能ac，但是又排在了末名。

看了大神的代码，写出了下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() < 2){
            return 0;
        }
        //当前可到达的最远距离。
        int current_max_index = nums[0];
        //遍历各个位置中，可到达的最远距离。
        int pre_max_max_index = nums[0];
        int jump = 1;
        
        for(int i = 1; i < nums.size(); i++){
            //更新当前可达到的最远距离。
            if(i > current_max_index){
                jump++;
                current_max_index = pre_max_max_index;
            }
            if(pre_max_max_index < nums[i] + i){
                //更新
                pre_max_max_index = nums[i] + i;
            }
        }
        return jump;
    }
    
};

跳到当前所能跳到的最远的位置所在的位置中。

记录当前位置所能到达的最远的位置。

如果做到了该最远位置，更新一下。继续走。