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, 然后再从下标 1 跳 3 步到达最后一个下标。
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

2. Solution

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

a. DFS

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

dfs-solution

b. Other solution

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

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

遇到大于0的数，继续；
遇到0，判断能否跨越；

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

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

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

0 出现在中间位置：需要跳过
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]))

Leetcode No.56 Merge Intervals

Leetcode No.39 Combination Sum