WHCSRL 技术网

【LeetCode 动态规划专项】跳跃游戏(55)

1. 题目

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

1.1 示例

  • 示例 1 1 1

    • 输入: nums = [2, 3, 1, 1, 4]
    • 输出: true
    • 解释: 可以先跳 1 1 1 步,从下标 0 0 0 到达下标 1 1 1 ,然后再从下标 1 1 1 3 3 3 步到达最后一个下标。
  • 示例 2 2 2

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

1.2 说明

1.3 提示

  • 1 ≤ nums.length ≤ 3 ∗ 1 0 4 1 le ext{nums.length} le 3 * 10^4 1nums.length3104
  • 0 ≤ nums [ i ] ≤ 1 0 5 0 le ext{nums}[i] le 10^5 0nums[i]105

1.4 进阶

在数组最后一个下标可达时,你可以进一步输出具体的跳跃情况么?

2. 解法一(动态规划)

2.1 分析

2.1.1 定义状态

这里使用 dp[i] 表示下标 i 的位置是否可达。

2.1.2 状态转移

在已经下标 i 之前位置的可达情况 dp[0]dp[1] 一直到 dp[i - 1] 的前提下,想要确定 dp[i] 的取值时,只要判断 dp[0]dp[1] 一直到 dp[i - 1] 中是否有某位置 j 可达从该位置可继续到达下标为 i 的位置,即是否有 dp[j] is True and dp[j] + j >= i

2.2 解答

根据上述分析,可以得到下列解答:

from typing import List


class Solution:
    def can_jump(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        dp = [False for _ in range(len(nums))]
        dp[0] = True
        if nums[0] >= 1:
            dp[1] = True
        for i in range(2, len(nums)):
            for j in range(i):
                if dp[j] is True and nums[j] >= i - j:
                    dp[i] = True
                    break
        return dp[-1]


def main():
    # nums = [2, 3, 1, 1, 4]
    nums = [3, 2, 1, 0, 4]
    sln = Solution()
    print(sln.can_jump(nums))


if __name__ == '__main__':
    main()

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

2.3 复杂度

  • 时间复杂度: O ( n 2 ) O(n^2) O(n2),其中 n n n 是数组 nums 的长度;
  • 空间复杂度: O ( n ) O(n) O(n)

3. 解法二(贪心)

实际上,上述解法虽理论上可行,但由于时间复杂度为 O ( n 2 ) O(n^2) O(n2) ,因而直接提交会超时。

3.1 分析

设想一下,对于数组中的任意一个位置 i,我们如何判断它是否可以到达?根据题目的描述,只要存在一个位置 j,它本身可以到达,并且它跳跃的最大长度为 j + nums[j] ,这个值大于等于 i,即 j + nums[j] >= i,那么位置 i 也可以到达。

换句话说,对于每一个可以到达的位置 j,它使得 j + 1j + 2 一直到 j + nums[j] 这些连续的位置都可以到达。

这样一来,我们依次遍历数组中的每一个位置,并实时维护最远可以到达的位置。对于当前遍历到的位置 j如果它在最远可以到达的位置的范围内,那么我们就可以从起点通过若干次跳跃到达该位置,同时可能需要用 j + nums[j] 更新最远可以到达的位置。

在遍历的过程中,如果最远可以到达的位置大于等于数组中的最后一个位置,那就说明最后一个位置可达,此时就可以直接返回 True 作为答案。反之,如果在遍历结束后,最后一个位置仍然不可达,就需要返回 False 作为答案。

3.2 解答

from typing import List


class Solution:
    def greedy_can_jump(self, nums: List[int]) -> bool:
        right_most = nums[0]
        for i in range(len(nums)):
            if i <= right_most:  # Position i is reachable
                right_most = max(i + nums[i], right_most)  # right_most may need update under this condition
            if right_most >= len(nums) - 1:  # Last position is at least reachable from position i
                return True
        return False


def main():
    # nums = [2, 3, 1, 1, 4]
    nums = [3, 2, 1, 0, 4]
    sln = Solution()
    print(sln.greedy_can_jump(nums))


if __name__ == '__main__':
    main()

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

实际上,根据上述思路,上述核心代码还可以写成如下两种形式:

def also_greedy_can_jump(self, nums: List[int]) -> bool:
    right_most = nums[0]
    for i in range(len(nums)):
        if i > right_most:
            return False
        right_most = max(i + nums[i], right_most)
    return True

def optimized_can_jump(self, nums: List[int]) -> bool:
    right_most = nums[0]
    i = 0
    while i <= right_most and right_most < len(nums) - 1:
        right_most = max(i + nums[i], right_most)
        i += 1
    return right_most >= len(nums) - 1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

3.3 复杂度

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 为数组的大小。只需要访问 nums 数组一遍,共 n n n 个位置。
  • 空间复杂度: O ( 1 ) O(1) O(1),不需要额外的空间开销。

实际上,这题还可以通过逆向的思维来解答,即从最后一个位置开始遍历,一次判断从其前面的位置是否可以跳至该位置,在遍历结束后判断当前位置是否为第一个位置:

from typing import List


class Solution:
    def backwards_can_jump(self, nums: List[int]) -> bool:
        pos = len(nums) - 1
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= pos:
                pos = i
        return pos == 0


def main():
    # nums = [2, 3, 1, 1, 4]
    nums = [3, 2, 1, 0, 4]
    sln = Solution()
    print(sln.backwards_can_jump(nums))


if __name__ == '__main__':
    main()

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
推荐阅读