Leetcode No.55 Jump Game
2022/11/10The general solution to the leetcode no.55 jump game. Medium level.
algorithm
dfs
others


1. Question

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

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

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

2. Solution

首先考虑特殊情况,当列表仅包含一个元素时,因为开始元素就是末尾元素,所以只返回 True

a. DFS

遇到这道题时,我的第一思路是使用 dfs 对所有可能的情况进行深度遍历。 画完树形图之后,发现存在相同情况的节点,可以通过一个列表存储历史节点,进行剪枝,空间换时间。

dfs-solution

b. Other solution

再次仔细观察题目,发现如果每一位都大于0的话,就算一步一步的跳跃也能达到末尾。

那么影响结果的关键就在于 能否跳过值为0的元素 。 于是解决问题的方法可以分类讨论,遍历整个列表:

  1. 遇到大于0的数,继续;
  2. 遇到0,判断能否跨越;

当遇到 0 时,我就去判断 0之前列表中的数字 能否成功跳过 0 这个元素,那么如何判断呢?

  1. 截取 0 之前的列表
  2. 从后向前遍历,看元素的值能否让它跳过末尾 (或跳到末尾)

根据 0 出现的位置会分成两种情况:

  1. 0 出现在中间位置:需要跳过
  2. 0 出现在最后一位:需要达到或跳过

于是代码如下所示:

python
from typing import List


def canJump(nums: List[int]) -> bool:
    if len(nums) == 1:
        return True

    def can_skip_zero(sub_nums: List[int]) -> bool:
        """whether it can jump over zero"""
        for i in range(1, len(sub_nums)+1):
            if sub_nums[-i] > i:
                return True
        return False

    def can_reach_zero(sub_nums: List[int]) -> bool:
        """whether it can reach or jump over zero"""
        for i in range(1, len(sub_nums)+1):
            if sub_nums[-i] >= i:
                return True
        return False

    for i in range(len(nums)):
        if nums[i] == 0:
            if i == len(nums)-1:
                return can_reach_zero(nums[:i])
            if not can_skip_zero(nums[:i]):
                return False
    return True


print(canJump([1, 2, 0, 0, 1]))
Designed & Coded by Tianyu @2022~2024