leetcode 55. 跳跃游戏(C++)

小灰灰 2023-05-28 05:28 104阅读 0赞

# 题目 #

给定一个非负整数数组，你最初位于数组的第一个位置。  
数组中的每个元素代表你在该位置可以跳跃的**最大长度**。  
判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
    输出: true
    解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
    输出: false
    解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

来源：[55. 跳跃游戏 - 力扣（LeetCode）][55. _ - _LeetCode]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 贪心算法 #

*  遍历每一个点，用maxlength记录（此点及之前的点）所能到达的最远点，  
    若到某个点，发现之前的最大距离已经不能到达，返回false；  
    否则，肯定能跳跃到最后一个位置。

代码如下：

class Solution { 
    public:
        bool canJump(vector<int>& nums) { 
            int maxlength = 0;      //记录所能到达的最远点
        	for (int i = 0; maxlength < nums.size()-1; i++){ 
        		if (i > maxlength)      return false;   //若此点已不能到达，返回false 
        		maxlength = max(maxlength, i + nums[i]);
        	}
        	return true;
        }
    };

结果：  
![在这里插入图片描述][20200328123636493.png]

# 倒推法 #

*  从后往前寻找能到最后一个位置的点（本质也是贪心算法）

代码如下：

class Solution { 
    public:
        bool canJump(vector<int>& nums) { 
            if (nums.empty())   return false;
            int pos = nums.size() - 1;      //pos表需要到达的位置
            for (int i = nums.size() - 2; i >= 0; i--) 
                if (nums[i] + i >= pos)     pos = i;
            return pos == 0;
        }
    };

结果：  
![在这里插入图片描述][2020032812364632.png]

[55. _ - _LeetCode]: https://leetcode-cn.com/problems/jump-game
[20200328123636493.png]: /images/20230528/e17627d536e347cbbe0080cf82199452.png
[2020032812364632.png]: /images/20230528/f1c1006853664a2ba9ba35c6d4219027.png