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 对所有可能的情况进行深度遍历。
画完树形图之后，发现存在相同情况的节点，可以通过一个列表存储历史节点，进行剪枝，空间换时间。
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]))