目录

• Leetcode 55 跳跃游戏1
• 题目
• 代码
• Leetcode 45 跳跃游戏2
• 题目
• 代码

这两道题的思想都是采用贪心思想，通过局部最优，来达到最后的全局最优。

Leetcode 55 跳跃游戏1

题目

代码

问题判断是否能达到最后，关键是声明一个reach变量，来记录我们最远到达的距离，那么当reach到达最后一个索引就返回true。我们每次遍历都要更新reach，使得reach每次都是目前能到达的最远距离。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()<=0)
            return true;
        int reach = 0;
        for(int i=0;i<=reach;i++)
        {
            reach = max(reach,nums[i]+i);
            if(reach>=nums.size()-1)
                return true;
        }
        return false;

    }
};

Leetcode 45 跳跃游戏2

题目

代码

这道题比上道题，多了一个最短距离。那么我们利用贪心思想，每次都找到局部最优解，从而达到全局最优。比如题目中的示例，具体过程是下面这样。

我们在代码中使用last来标记在每一轮中的最远距离。具体代码如下

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.empty())
            return -1;
        int reach = 0;
        int count = 0;
        int last = 0;
        for(int i=0;i<nums.size();i++)
        {
            if(i>reach)			//超过了能到达的最远距离，返回-1
                return -1;
            if(i>last)			// 每当我们遍历超过上一轮的区间，我们就更新last，
            					// 然后步数+1，之后在我们新得到的区间中继续遍历。				
            {
                count++;
                last = reach;
            }
            reach = max(reach,nums[i]+i);  //我们每次都记录能够到达的最远距离
        }
        return count;        
    }
};