2021-11-04 leetcode 动态规划 45.跳跃游戏2 c++

2021-11-04 leetcode 动态规划 45.跳跃游戏2 c++

题目

思路
贪心

首先 实现nums[0]的第一次跳跃，跳跃范围为range，在range范围内遍历nums[i]，找到最远可跳跃距离index。
遍历到I == range时，即范围内的元素都遍历时，进行下一次最远距离跳跃，即跳index个单位。当range超出nums.size()-1时，即能够跳到最后一个位置甚至更远，此时返回最小次数。
注意：若nums.size() == 1，则step == 0，即不需要跳。因此，这个判断

if(range >= nums.size()-1) //当前范围超出数组，即可跳到最远距离甚至更远
	return step;

需要放到最前面。

AC代码

class Solution {
public:
    int jump(vector& nums) {
        int index = 0;//在当前范围内，能挑到的最远距离
        int range = 0;//目前覆盖坐标范围
        int step = 0;//步数
        for(int i = 0; i < nums.size(); i++) {
        	if(range >= nums.size()-1) //当前范围超出数组，即可跳到最远距离甚至更远
            	return step;
            index = max(index, i+nums[i]);//在当前范围内更新最大距离
            if(i == range) {
                range = index;
                step++;
            }
        }
        return step;//这个是在nums[nums.size()-2]跳到最后一个位置以及更远的情况
    }
};