45. Jump Game 2 跳跃游戏2

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.

给出一个非负整数数组,数组中的元素大小表示可以从该index向右跳跃的距离.问跳到最后一个元素的最少跳跃次数.

这道题属于贪心算法类.

写法1:

int jump(vector<int>& nums) {
    int res = 0;       // 记录跳d了几次
    int size = nums.size();
    if (size<2) return 0;
    for (int i = 0; i < size; ) {
        int steps = nums[i]; // 第i个元素可以走的步数
        int max = 0;
        int step = 0;        // 第i个元素实际走的步数
        while (steps > 0) {
        	// 如果这一步跳出超过边界,直接返回
            if (i + steps >= (size-1)) {
                res ++;
                return res;
            }else{
            	// 保存最远到达
                int tmp = nums[i+steps]+(i+steps);
                if (tmp > max){
                    max = tmp;
                    step = steps;
                }
                steps--;
            }
        }
        if (step > 0) {
            res ++;
            i += step;
            if (i>=(size-1))
                return res;
        }else{
            return 0;
        }
    }
    return 0;
}

写法2: 这个是别人的解法,更加的简洁

int jump2(vector<int>& nums) {
    // last为上一次到达的最远值
    int res = 0, n = nums.size(), last = 0, cur = 0;
    for (int i = 0; i < n - 1; ++i) {
        // 记录当前能到达的最远值
        cur = max(cur, i + nums[i]);
        // 当i到达last的时候,说明结束了上一个最大范围,需要加1
        if (i == last) {
            last = cur;
            ++res;
            if (cur >= n - 1) break;
        }
    }
    return res;
}
 
comments powered by Disqus