Jump Game
你站在数组 nums 的索引 0 处。从索引 i 开始，你可以向前跳任意步数，范围是 1 到 nums[i]，因此 nums[i] 是你从那里能跳的最远距离，而 0 表示你无法移动。如果存在一连串跳跃能够到达最后一个索引，则返回 true，否则返回 false。
函数
- numsinteger-array
- 从每个索引位置出发能跳的最远距离
- 返回值boolean
- 如果你能从索引 0 开始到达最后一个索引，则为 true；否则为 false
约束条件
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 105- 一次跳跃的距离可能小于
nums[i]，因此长距离跳跃不会迫使你越过最后一个索引。
示例
- 输入
- nums = [2, 0, 3, 1, 0, 2]
- 输出
- true
- 解释
- 从索引 0 可以到达索引 1 或 2。索引 1 的值是 0，是一条死路；索引 2 的值是 3，可以到达索引 5，也就是最后一个索引。
- 输入
- nums = [1, 3, 0, 0, 0, 2]
- 输出
- false
- 解释
- 索引 0 只能前进一步到索引 1，而索引 1 最多只能到达索引 4。索引 2、3 和 4 都存放着 0，所以永远无法越过索引 4 到达索引 5。
- 输入
- nums = [0]
- 输出
- true
- 解释
- 这个数组只有一个元素，所以你从最后一个索引开始，不需要跳跃。
进阶
统计到达最后一个索引的不同跳跃序列数量，结果对 10^9+7 取模，时间复杂度仍为 O(n)。
提示
逐个打开提示，每个都会多透露一点。
只有当它前面的内容都无法跳过它时，
0才会困住你。要判断这一点，你需要知道它前面的索引的哪些信息？如果你能到达索引
i，就能到达从i到i+nums[i]的每个索引，因为允许跳得更短。因此，可到达的索引始终构成一个从索引 0 开始的连续区间。从左向右遍历，并记录
farthest，也就是当前区块的最右端。如果当前索引超出farthest，就永远无法到达。否则，如果i+nums[i]更大，就将farthest更新为i+nums[i]。如果遍历完整个数组，就能到达最后一个索引。
题解
逐条尝试路线会耗费指数级的时间。换个角度看索引：你能到达的索引总是从索引 0 开始的一段连续区间。这个区间的右端点包含了你需要的所有信息，只需遍历一遍就能得出答案。
尝试每一次跳跃
结果正确，但无法在最大的测试中运行完毕
思路
从索引 0 开始，依次尝试每个落点，并从每个落点继续重复同样的操作。如果任何一条分支到达最后一个索引，答案就是 true。这种搜索是正确的，因为它会尝试每条路径。
它不会记住已经探索过的索引，所以当答案是 false 时，必须排除每一条路径。在 [4, 3, 2, 1, 0, 5] 中，0 前面的每个索引都能到达 0，因此有 8 条路径通向它。有 30 个这样的索引时，路径数量会超过 5 亿条。
算法
- 编写一个辅助函数
reach(i)，用于判断：你能否从索引i到达最后一个索引？ - 如果
i是最后一个索引，就返回true。 - 否则，尝试从
i+1到min(i+nums[i], n-1)的每个落点next，只要reach(next)返回true，就立即返回true。 - 如果没有可行的落点，就返回
false。 - 答案是
reach(0)。
def canJump(nums):
last = len(nums) - 1
def reach(i):
# Can you get from index i to the last index?
if i == last:
return True
for nxt in range(i + 1, min(i + nums[i], last) + 1):
if reach(nxt):
return True
return False
return reach(0)记住哪些索引可以完成任务
结果正确，但无法在最大的测试中运行完毕
思路
如果你能从某个下标出发到达终点，就称它是好下标。最后一个下标是好下标；如果从 i+1 到 i+nums[i] 的某个下标是好下标，那么下标 i 也是好下标。每个下标只取决于它右侧的下标，因此从右向左填写表格，并且只判断每个下标一次。在第一个示例中，下标 2 可以到达下标 5，所以它是好下标；下标 0 也一样，因为它可以到达下标 2。
判断一个下标时，仍可能需要扫描 n 个单元格。在 [9998, 9997, …, 1, 0, 7] 中，每个下标都能到达 0，但无法到达 0 后面的任何位置，因此每个下标都会扫描整个范围：对于 10^4 个元素，大约需要进行 5 × 10^7 次检查。
算法
- 创建一个长度为
n的布尔数组good，并将good[n-1]设为 true。 - 让
i从n-2递减到 0。 - 扫描
j，范围从i+1到min(i+nums[i], n-1)。如果任意一个good[j]为 true，就将good[i]设为 true，并停止扫描。 - 返回
good[0]。
def canJump(nums):
n = len(nums)
good = [False] * n # good[i]: from i you can reach the last index
good[n - 1] = True
for i in range(n - 2, -1, -1):
for j in range(i + 1, min(i + nums[i], n - 1) + 1):
if good[j]:
good[i] = True
break
return good[0]记录最远可到达的索引
思路
从一个可到达的索引 i 出发，你可以到达 i+1 到 i+nums[i] 之间的任意位置，中间没有间隔。这段范围从已经到达的区块内部开始，因此区块会不断扩展，不会出现空缺，并且始终是 [0, farthest]。
从左到右遍历 i。只要 i ≤ farthest，索引 i 就可到达，并会将 farthest 扩展到 max(farthest, i+nums[i])。如果 i 超过了 farthest，就没有任何可到达的索引能跳到 i，而且区块永远无法跨过这个间隔，因此最后一个索引无法到达。只保留右端点不会丢失任何信息：你不会预先决定跳到哪里，而且所有更近的落点都在区块内。
在第二个示例中，farthest 依次变为 0、1、4，并在连续三个 0 处保持为 4。索引 5 超出了它的范围，因此答案是 false。
算法
- 将
farthest = 0。 - 从左到右遍历每个索引
i：如果i > farthest，则返回false。 - 否则，将
farthest = max(farthest, i+nums[i])。 - 如果循环结束，说明每个索引都可到达，因此返回
true。
def canJump(nums):
farthest = 0 # every index up to farthest can be reached
for i, jump in enumerate(nums):
if i > farthest:
return False # nothing reachable jumps to i
farthest = max(farthest, i + jump)
return True
易错点和边界情况
- 始终正好跳
nums[i]步。对于[2, 5, 0, 0]，从索引 0 完整跳跃会落在 0 上，而跳 1 步到索引 1 就能到达终点。 - 一看到 0 就返回
false。[2, 0, 1]会跳过 0，答案是true。 - 在检查
i > farthest之前更新farthest。无法到达的索引不能扩大可达范围。 - 把只有一个元素的数组当作失败。你已经站在最后一个索引上，即使它的值是 0 也一样。
- 对很长的数组使用递归。路径可能长达 10,000 次跳跃，在几种语言中会导致调用栈溢出；Python 默认会在 1,000 层嵌套调用时停止。
常见问题3
Jump Game 的时间复杂度是多少？
最远可达位置的遍历会访问每个索引一次，因此时间复杂度为 O(n)，额外空间复杂度为 O(1)。表格方法在最坏情况下的时间复杂度为 O(n²)，而尝试每条路线则需要指数级时间。
跳跃游戏是一个动态规划问题吗？
可以这样做：从右向左遍历，当某个索引能到达的落点中有一个是好的，就将该索引标记为好，时间复杂度为 O(n²)。目前找到的最左侧好索引才是关键，因为只要某个索引能到达右侧任意一个好索引，就能到达那个索引。每当 i+nums[i] ≥ goal 时，就将 goal 更新为 i。
如何找到最少的跳跃次数？
分层使用最远可达位置的思路。记录当前跳跃次数能到达的区间末尾，以及下一跳能到达的最远索引。当 i 超过当前区间末尾时，就多计一次跳跃，并将区间延伸到该最远索引。这仍然只需进行一次 O(n) 遍历。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def canJump(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [2, 0, 3, 1, 0, 2]
预期输出
true