🍥

Hang Zhang

genius.

Data Structure and Algorithm

Jump Game

55. 跳跃游戏

算法

维护最远可达位置：
- 使用变量 i 表示当前最远可达的位置
- 初始位置为 0
逐步检查跳跃能力：
- 遍历数组，当前下标为 j，检查是否可以到达：
  - 如果 i < j，说明无法继续前进，返回 false
- 更新最远可达位置：
  - i = max(i, j + nums[j]
终止条件：
- 遍历结束后，若能始终更新 i 使其覆盖整个数组，返回 true

复杂度分析

遍历数组一次，时间复杂度为 O(n)
空间复杂度为 O(1)

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution
{
public:
    bool canJump(vector<int>& nums)
    {
        int i = 0; // 当前最远可达位置
        for (int j = 0; j < nums.size(); ++j)
        {
            if (i < j)  // 如果无法覆盖当前位置
                return false;
            i = std::max(i, j + nums[j]); // 更新最远可达位置
        }
        return true; // 如果能够遍历完成，返回 true
    }
};

Python 代码

1
2
3
4
5
6
7
8


class Solution:
    def canJump(self, nums: List[int]) -> bool:
      i = 0
      for j in range(len(nums)):
        if i < j:
          return False
        i = max(i, j + nums[j])
      return True

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func canJump(nums []int) bool {
  i := 0
  for j := 0; j < len(nums); j ++ {
    if i < j {
      return false
    }
    i = max(i, j + nums[j])
  }
  return true
}