45. Jump Game II

妖狐艹你老母 2022-03-21 11:10 133阅读 0赞

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:**

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.

题意：一个数组存储了**非负整型数据**，数组中的第i个元素nums\[i\]，代表了可以从数组第i个位置**最多**向前跳跃nums\[i\]步。已知数组**各元素**的情况下，确认可以从第0个位置跳跃到数组最后一个位置，求**最少**需要**跳跃**几次？

分析：在**到达某点前**若一直不跳跃，发现从该点不能调到**更远**的地方了，在这之前肯定有次**必要的**跳跃。所以，在无法到达更远前，应该跳到一个可以到达更远位置的位置。

算法：（1）设置cur\_max\_index为**当前可达到的最远位置**；（2）设置pre\_max\_max\_index为在遍历过程中，各个位置可达到的最远位置；（3）设置min\_jump为最少跳跃次数；（4）利用pos遍历数组，若pos超过cur\_max\_index，min\_jump加1，更新cur\_max\_index；（5）遍历过程中，如果index\[pos\]更大，则更新pre\_max\_max\_index。

class Solution {
    public:
      int jump(vector<int>& nums) {
    	if (nums.size() <= 1)
    		return 0;
    
    	vector<int> index;
    	for (int i = 0; i < nums.size(); i++)
    	{
    		index.push_back(nums[i] + i);
    	}
    
    	int pos = 1;
    	int min_jump = 1;
    	int cur_max_index = index[0];
    	int pre_max_max_index = index[0];
    	while (pos < index.size())
    	{
    		if (pos > cur_max_index)
    		{
    			min_jump++;
    			cur_max_index = pre_max_max_index;
    		}
    
    		if (index[pos] > pre_max_max_index)
    			pre_max_max_index = index[pos];
    
    		pos++;
    	}
    	return min_jump;
    }
    };