55. 跳跃游戏
一句话套路贪心维护最远可达 reach,不可达即失败
题目描述
给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。
示例 1:
输入:nums = [2,3,1,1,4] 输出:true 解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4] 输出:false 解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
提示:
1 <= nums.length <= 1040 <= nums[i] <= 105
思路
时间
O(n)空间
O(1)思路
贪心维护「最远能到达的下标」reach。遍历到 i 时,如果 i > reach 说明这一步都迈不出去(中间有跳不过去的坑)-> 失败;否则用 i+nums[i] 更新 reach。
注意不需要真的模拟每一步跳多远,这就是它比 DP 快在哪。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0055 {
class Solution {
public:
bool canJump(vector<int>& nums) {
int reach = 0;
for (int i = 0; i < (int)nums.size(); ++i) {
if (i > reach) return false; // 当前位置不可达
reach = max(reach, i + nums[i]);
if (reach >= (int)nums.size() - 1) return true; // 提前收工
}
return true;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0055::Solution s;
vector<int> a{2, 3, 1, 1, 4};
CHECK_TRUE(s.canJump(a));
vector<int> b{3, 2, 1, 0, 4}; // 0 是死坑
CHECK_FALSE(s.canJump(b));
vector<int> c{0}; // 长度 1,站在终点
CHECK_TRUE(s.canJump(c));
vector<int> d{1, 0};
CHECK_TRUE(s.canJump(d));
vector<int> e{2, 0, 0}; // 恰好跨过 0
CHECK_TRUE(s.canJump(e));
vector<int> f{1, 2, 0, 1};
CHECK_TRUE(s.canJump(f));