Leetcode-45Jump Game II

45. 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.

For example:
Given array A = [2,3,1,1,4]

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.

题解：

输入一个数组，数组中的元素 nums[i] 表示可以从第 i 个位置最多向前跳跃 nums[i] 步，若该数组能够从第0个位置跳跃到数组的最后一个位置，求若想从第0个位置跳跃到数组的最后一个位置最少需要跳几次。
和Leetcode55：https://www.jianshu.com/p/cf34a714ef44 类似；还是以A = [2,3,1,1,4] 为例：
A[0] = 2：表示从位置0最远可以跳到位置2；也就是说，遍历A的时候，如果当前位置 i = 2 时，说明到该位置后必须进行一次跳跃；
用max_jump表示截止到当前位置 i 所能跳到的最远距离；
用current_max_jump存储在跳跃之前所能达到的最远距离；
例如：
对于位置 0 ：A[0] = 2 ；说明位置 0 在跳跃之前所能达到的最远距离current_max_jump = 2 ；所以当 i = 2 时，我们将跳跃次数result + 1；同时，将截止到位置 2 所能跳到的最远距离max_jump 赋给 current_max_jump，让下一次的跳跃也可以跳到所能达到的最远位置；
如果下一次的跳跃也可以跳到所能达到的最远位置大于等于数组A的总长度，说明再一次跳跃可以直接到达终点，break 遍历 A 数组的循环。
特殊情况分析：
当输入的数组只有一个位置时，说明已经在终点了，直接返回0；

My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() <= 1) {
            return 0;
        }
        int current_max_jump = nums[0];
        int max_jump = 0;
        int result = 0;
        for (int i = 0; i < nums.size(); i++) {
            max_jump = max(max_jump, i + nums[i]);
            if (current_max_jump >= nums.size()) {
                result += 1;
                break;
            }
            if (current_max_jump == i) {
                result += 1;
                current_max_jump = max_jump;
            }
        }
        return result;
    }
};

int main() {
    vector<int> nums;
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(1);
    nums.push_back(1);
    nums.push_back(4);
    Solution s;
    cout << s.jump(nums);
    return 0;
}

结果：

2

My Solution（Python）：

class Solution:
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_jump = nums[0]
        cur_jump = nums[0]
        jump_count = 0
        for i in range(1, len(nums)):
            if cur_jump >= len(nums) - 1:
                jump_count += 1
                break
            max_jump = max(max_jump, i + nums[i])
            if i == cur_jump:
                cur_jump = max_jump
                jump_count += 1
        return jump_count