HHot 100C++ 图解

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 <= 104
  • 0 <= nums[i] <= 105

思路

时间O(n)
空间O(1)

思路

贪心维护「最远能到达的下标」reach。遍历到 i 时,如果 i > reach 说明这一步都迈不出去(中间有跳不过去的坑)-> 失败;否则用 i+nums[i] 更新 reach。

注意不需要真的模拟每一步跳多远,这就是它比 DP 快在哪。

图解

2 0 3 1 1 2 1 3 4 4
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/14_greedy.cpp14 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q55_jump_game13 行
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));

↑↓ 选择↵ 打开/ 随时唤起