跳至主要內容

0055. 跳跃游戏

ITCharge大约 3 分钟

0055. 跳跃游戏open in new window

  • 标签:贪心、数组、动态规划
  • 难度:中等

题目链接

题目大意

描述:给定一个非负整数数组 nums,数组中每个元素代表在该位置可以跳跃的最大长度。开始位置位于数组的第一个下标处。

要求:判断是否能够到达最后一个下标。

说明

  • 1nums.length3×1041 \le nums.length \le 3 \times 10^4
  • 0nums[i]1050 \le nums[i] \le 10^5

示例

  • 示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 13 步到达最后一个下标。
  • 示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

解题思路

思路 1:贪心算法

如果我们能通过前面的某个位置 jj,到达后面的某个位置 ii,则我们一定能到达区间 [j,i][j, i] 中所有的点(jij \le i)。

而前面的位置 jj 肯定也是通过 jj 前面的点到达的。所以我们可以通过贪心算法来计算出所能到达的最远位置。具体步骤如下:

  1. 初始化能到达的最远位置 maximax_i00
  2. 遍历数组 nums
  3. 如果能到达当前位置,即 maxiimax_i \le i,并且当前位置 + 当前位置最大跳跃长度 > 能到达的最远位置,即 i+nums[i]>maxii + nums[i] > max_i,则更新能到达的最远位置 maximax_i
  4. 遍历完数组,最后比较能到达的最远位置 maximax_i 和数组最远距离 size - 1 的关系。如果 maxi>=len(nums)max_i >= len(nums),则返回 True,否则返回 False

思路 1:代码

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        size = len(nums)
        max_i = 0
        for i in range(size):
            if max_i >= i and i + nums[i] > max_i:
                max_i = i + nums[i]
            
        return max_i >= size - 1

思路 1:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 是数组 nums 的长度。
  • 空间复杂度

思路 2:动态规划

1. 划分阶段

按照位置进行阶段划分。

2. 定义状态

定义状态 dp[i] 表示为:从位置 00 出发,经过 jij \le i,可以跳出的最远距离。

3. 状态转移方程
  • 如果能通过 0i10 \sim i - 1 个位置到达 ii,即 dp[i1]idp[i-1] \le i,则 dp[i]=max(dp[i1],i+nums[i])dp[i] = max(dp[i-1], i + nums[i])
  • 如果不能通过 0i10 \sim i - 1 个位置到达 ii,即 dp[i1]<idp[i - 1] < i,则 dp[i]=dp[i1]dp[i] = dp[i - 1]
4. 初始条件

初始状态下,从 00 出发,经过 00,可以跳出的最远距离为 nums[0],即 dp[0] = nums[0]

5. 最终结果

根据我们之前定义的状态,dp[i] 表示为:从位置 00 出发,经过 jij \le i,可以跳出的最远距离。则我们需要判断 dp[size - 1] 与数组最远距离 size - 1 的关系。

思路 2:代码

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        size = len(nums)
        dp = [0 for _ in range(size)]
        dp[0] = nums[0]
        for i in range(1, size):
            if i <= dp[i - 1]:
                dp[i] = max(dp[i - 1], i + nums[i])
            else:
                dp[i] = dp[i - 1]
        return dp[size - 1] >= size - 1

思路 2:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 是数组 nums 的长度。
  • 空间复杂度O(n)O(n)