LeetCode Jump Games
44 Jump Games II
虽然名字上第二个，但题目编号反而要比1要早
求跳到尾部的最小步数1。
解①DP
这个题目本身带有 DP 的标签，首先也就想到了简单的 DP 思路：记录跳到每个位置所需要的最小步数，从左到右扫描，每到一个位置，就用当前步数加一来更新该位置下一步所能到达的那一些位置。
def solve(nums: List[int]) -> int:
dp = [len(nums)] * len(nums)
dp[0] = 0
for i in range(0, len(nums)-1):
for j in range(i+1, min(i+nums[i]+1, len(nums))):
dp[j] = min(dp[j], dp[i]+1)
return dp[-1]
这个算法的时间复杂度在官解和很多题解里直接标了 $O(n^2)$ ，但这是不准确的，因为根据题目标明的数据范围 nums[i] 的最大值与 len(nums) 的最大值不同，前者要小一个数量级，实际上是 1000 ，很多情况这可能只是一个稍微大一点的常数。
实际运行 3862 ms (beats 25.91%)
说差也差，说不差，还有 10000+ ms 通过的朋友。
解②Greedy：
做多了 DP 的题目，再想 Greedy 思路反而变得不太直观，所谓看山不是山。
算法推论：
探测每个位置下一步能够跳到的所有位置，比较它们下一步能够跳到的最远的位置，最远的那一个就是下一步要跳到的地方，这样直到可以等于或者超过终点。
贪心的归纳法证明：
定义：把用最小步数跳到终点的一个跳法儿称作一个最短序列。
只需要证明，这个算法的跳的每一个位置都在同一个最短序列里：
-
初始时刻，起始位置显然一定在最短序列里
-
假如上一个位置 $i_0$ 在最短序列里，那么从该位置出发，比较所有下一步可以跳到的位置，假如下一步跳最远的位置是 $j$ ，而存在另一个位置 $j_1\neq j$ 是这个最短序列里的下一步:
定义通过 $j_1$ 的最短序列上的下一个位置为 $j_1’$ ，则：
2.1. 如果 $j_1’ \geqslant j$ ，那是不是说明通过 $j_1$ 能够跳到的位置，通过 $j$ 也能跳到
2.2. 如果 $j_1’ \lt j$ ，则有 $i \lt j_1 \lt j_1’$ ，那为什么不直接一步从 $i_0$ 跳到 $j_1’$ ，而是要花两步跳？ 这又和最短序列矛盾了
证毕。
贪心成立关键在于：
- 跳的步数是一个连续地范围
- 跳的步数是非负值
def solve(nums: List[int]) -> int:
if len(nums) == 1:
return 0
i0 = 0 # prev i
i = nums[i0]
step = 1
while i < len(nums) - 1:
i0, i = max(
[(j, j+nums[j]) for j in range(i0+1, i0+1+nums[i0])],
key=lambda x: x[1]
)
step += 1
return step
扫描了多长的候选位置，就至少跳过多少候选位置，时间复杂度为 $O(n)$ 。
运行时间：120 ms (beats 96.35%)，绝对地最优解。
55 Jump Games I
虽然名字上第一个，但题目编号反而要比2要晚
解①Greedy-1：
这个问题和上面 Games II 的题干看起来非常像，可以用一模一样的方法
def solve(nums: List[int]) -> bool:
if len(nums) == 1:
return True
i0 = 0
i = nums[i0]
while i < len(nums) - 1:
if i0 == i:
return False
if i0+nums[i0] >= len(nums) - 1:
return True
i0, i = max(
map(lambda j: (j, j+nums[j]), range(i0+1, i0+1+nums[i0])),
key=lambda x: x[1]
)
return True
但是数据的规模发生了变化，nums[i] 的最大值反而要比 len(nums) 的最大值大一个数量级，时间复杂度应该类似于上面 Games II 的 DP 解法。
实际运行时间：6041 ms (beats 8.5%)
解② Greedy-2：
由于本题 len(nums) 比 nums[i] 有较小的数据规模，何况追求得最小步数而是最大可达位置，最好是可以只扫描 nums 数组。
可以这样考虑：如果终点是不可达的，那么在 nums 上一定存在一个真正的终点位置，如果能够找到这个终点位置，就可以进行判断了。
可是终点是什么样的呢？
首先终点的步长应该是零，否则从它就可以跳到更右边的位置，而它也就不是终点了。
其次，任何终点左边的位置一步之内都最多跳到终点。
如果从 nums 的尾部开始向左扫描，如果一个位置可以一步到达尾部，那么就可以把尾部设置到该位置，如果在结束的时候尾部没有归为零，终点就是尾部前一个位置。
def solve(nums: List[int]) -> bool:
lf = len(nums) - 1
for i in range(len(nums)-2, -1, -1):
if i + nums[i] >= lf:
lf = i
return lf == 0
运行时间：394 ms (beats 98.95%)
也可以从正面开始扫描，寻找终点，但除了让代码更复杂一点没有任何好处。
def solve(nums: List[int]) -> bool:
to = 0
for i in range(0, len(nums)-1):
if i > to:
return False
if i+nums[i] >= len(nums)-1:
return True
to = max(to, i+nums[i])
return to >= len(nums) - 1
运行时间：428 ms (beats 96.53%)
1306 Jump Games III
从给定位置开始跳，每次有左右两个方向，不是跳一个范围，而是一个固定地步长。
谈不到什么算法的简单题目。
from typing import List
def solve(arr: List[int], start: int) -> bool:
""" false: unvisited, true: visited """
n = len(arr)
stack = [start]
cache = [False] * n
while stack:
i = stack.pop()
if arr[i] == 0:
return True
if not cache[i]:
cache[i] = True
if i+arr[i] < n:
stack.append(i+arr[i])
if i-arr[i] >= 0:
stack.append(i-arr[i])
return False
运行时间：249 ms (beats 98.79%)，内存占用： 23.6 MB (beats 47.8%， ~ 100%)
题目很简单，但是有两点细节很值得一提：
- 这个题目内存占用最低地情况就是 23 MB ，如果不创建新的结构，而是直接在
arr上就地修改2，几乎不会节约任何内存占用，只少了大概 0.3 MB ，不知道造成这个原因的技术细节是什么，可能只是 Python 的内存分配器一次性地申请了很大的内存3； - 而更令人意想不到地是这个题目的解的内存占用可以达到 80 MB！粗略地看了一下，它们全都是使用了基于哈希表的数据结构（
set，map，default_dict，etc.）而不是数组来标记访问，一方面它们的访问速度相较于列表并没有明显地更慢，另一方面它们占用了有点儿意料之外地更多的内存。
对于第一点，CPython 显然不如 JVM 那样有很详细或者冗繁地参数控制，更不如编译型语言对内存使用那样地节约，这没什么好说的。
对于第二点，必须申明地是，必须实际地考虑哈希表的实现，由于负载因子（fill factor）的存在4，至少内部的空间容量就是原数组的倍数，再考虑存储碰撞元素的列表甚至树形结构指针的开销，实际地哈希表占据的空间如果有个数组的两倍也毫不奇怪（但是像 Python 这样确实有些夸张，内存开销大概是普通列表的 1000 倍的级别，只能说完全地对象语言是这样的）。
因此一个很重要地原则是，如果是追踪一个已知列表的每个元素状态，直接使用列表无论时间还是空间性能都要优于使用哈希表。
1345. Jump Game IV
固定跳点，每个点可以跳到三类地方，+1/-1/同值点，求从头跳到尾的最小步数。
非常类似于 Games III ，前者被标定为 Medium 难度，现在只不过又缝了一个哈希表的使用，难度就被定位到 Hard 级了。56
运用哈希表统计同值点，用 BFS 求取最小步数，需要注意得是哈希表上的元素在被访问过后必须弹出，否则时间复杂度会劣化到 $O(n^2)$ 。
def solve(arr: List[int]) -> int:
n = len(arr)
val = defaultdict(list)
for i, v in enumerate(arr):
val[v].append(i)
step = 0
queue = [0] if arr[1:] else []
visited = [False] * n
while queue:
nxt_queue = []
step += 1
for i in queue:
if i+1 < n and not visited[i+1]:
visited[i+1] = True
nxt_queue.append(i+1)
if i+1 == n-1:
return step
if i-1 >= 0 and not visited[i-1]:
visited[i-1] = True
nxt_queue.append(i-1)
while val[arr[i]]:
j = val[arr[i]].pop()
if not visited[j]:
visited[j] = True
nxt_queue.append(j)
if j == n-1:
return step
queue = nxt_queue
return step
运行时间：549 ms (beats 98.59%)，内存占用：29.6 MB （beats 94.3%）
关于使用什么样的算法和数据结构来对同值位置进行统计，可以继续 Games III 的讨论，当一般地值域比元素数大一个数量级，就是一定要使用哈希表的情况。
1340. Jump Game V
有单独一篇博文来讨论： LeetCode1340
1696. Jump Game VI
乍看起来很简单，但是做起来令人有些不快，因为它作为中等难度的题，但寻找 $O(n)$ 的解决方案并不如我预计得那样容易。
题目求解最大的跳的位置和，也是跳一个连续范围，看起来就是利用贪心地思想寻找一个简单方法就 OK 了，但是没有这样的方法，想了很长时间，就是发现在所有位置的值中，如果是正的，一定在序列里，但如果是负的，就存在一个更少的步数但更大（绝对值）的负值与更多的步数而更小的负值，这就不适合贪心算法了。
解①分治+DP：
只能一步一步考虑，从索引 $0$ 的位置，第一步跳到的位置，有 $k$ 个，可以线性地计算出它们的最大值，包括这个长度为 $k$ 数组的后缀最大值，那么对于下一个 $k$ 长度的区间，它们每个位置的最大访问和就可以通过前 $k$ 个的后缀最大值和当前 $k$ 个的前缀最大值计算得出，这样一直到计算出了到最后一个位置的最大访问和，整个时间复杂度都是线性的。
from typing import List
def solve(nums: List[int], k: int) -> int:
init = nums[0]
nums = nums[1:]
n = len(nums)
cache = [0] * k
prev_postfix_max = [0] * k
cur_prefix_max = [0] * k
blk_rem = n % k
max_blks = n // k + (1 if blk_rem else 0)
acc = 0
for i, v in enumerate(nums[:k]):
cache[i] = v + acc
if v > 0:
acc += v
for blk in range(1, max_blks):
prev_postfix_max[k-1] = cache[k-1]
for j in range(k-2, -1, -1):
prev_postfix_max[j] = max(prev_postfix_max[j+1], cache[j])
cur_prefix_max[0] = cache[0] = prev_postfix_max[0] + nums[blk*k]
if blk == max_blks-1 and blk_rem:
tail = blk_rem
else:
tail = k
for j in range(1, tail):
cache[j] = max(prev_postfix_max[j], cur_prefix_max[j-1]) + nums[blk*k+j]
cur_prefix_max[j] = max(cur_prefix_max[j-1], cache[j])
return init + cache[(k+blk_rem-1) % k]
时间复杂度 $O(n)$ 。
运行时间：826 ms (beats 80.95%)，内存占用：30.50 MB (beats 52.38%)
解②双头单调栈+DP：
本方法是上面方法的规整解，可以使用优先级队列维护之前最大的统计和的位置，当堆顶的元素过期（即与当前位置差距超过 $k$ ）就弹出，不过这样每次弹出栈顶元素需要的时间复杂度就是 $O(\text{log}n)$ ，总共的时间复杂度 $O(n\text{log}n)$ 。
可以用双头的单调栈，从头到尾严格减的顺序，每次检查栈头最大值，如果“过期”就弹出（$i$ 最多增加一次，因此只需要检测一次），用栈顶的访问最大值和当前值加和计算出当前位置的访问最大值，把栈尾所有不超过当前访问最大值的索引位置弹出，然后把当前索引位置插入尾部。
from typing import List
from collections import deque
def solve(nums: List[int], k: int) -> int:
n = len(nums)
q = deque([0])
dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
if i-q[0] > k:
q.popleft()
dp[i] = nums[i] + dp[q[0]]
while q and dp[q[-1]] <= dp[i]:
q.pop()
q.append(i)
return dp[-1]
时间复杂度 $O(n)$ 。
运行时间：773 ms (beats 97.14%)，内存占用：30.53 MB (beats 52.38%)
1871 Jump Game VII
首先吐槽下这个题的测试用例很不健全，导致有些 $O(n^2)$ 复杂度的算法甚至比 $O(n)$ 的算法都快 。
这个题目是单向跳，跳的步长是一个固定的范围： [minJump, maxJump] ，而且只能跳到值为 ‘0’ 的位置，从头开始跳，看能否跳到最后一个。
又是一个跳的这个范围不是从 $1$ 开始，但仍然是连续的，这就启发我们仍然可能找到一个基于贪心地思想的 $O(n)$ 的解决方案。
把值为 ‘0’ 的位置称为可跳位置，事实上，这个题目破题的关键是向前查找可跳位置是否可以跳到。
解🄋贪心：序
可以用一个列表保存所有可跳到的位置，然后使用最多两次二分搜索就可以判断出 [minJump, maxJump] 范围内是否有可跳到的位置跳到当前位置：
from bisect import bisect_left
def solve(s: str, minJump: int, maxJump: int) -> bool:
n = len(s)
stack = [0]
for i in range(1, n):
if s[i] == '0':
if i-maxJump <= stack[-1] and i-minJump >= 0:
l = bisect_left(stack, i-maxJump)
if stack[l] == i-maxJump:
stack.append(i)
continue
r = bisect_left(stack, i-minJump)
if l < r or stack[r] == i-minJump:
stack.append(i)
continue
return stack[-1] == n-1
时间复杂度是 $O(n\text{log}n)$
运行时间：439 ms (beats 36.99%)，内存占用：21.1 MB (beats 25.62%)
解①贪心：双头栈
如果能悟出了贪心算法，那么马上就能想到前面 Jump Game VI 里面使用过的双头单调栈，只不过这里更简单，序号本来就是自然增长的，不需要特别维护单调性，弹出头部所有小于 i-maxJump 的索引。
因为之后永远都不会检查到这些位置了，然后检查新的栈头是否大于等于 i-minJump ，成立的话就说明存在前面一个可跳到的位置能够跳到当前位置，这就把当前位置索引插入到尾部，当然如果所有栈已经空了，就提前返回失败，因为已经没有任何可跳到的位置能继续向前跳了。
最后检查栈的尾是否有最后一个索引编号。
from collections import deque
from itertools import islice
def solve(s: str, minJump: int, maxJump: int) -> bool:
n = len(s)
stack = deque([0])
for i, v in islice(enumerate(s), 1, None):
if v == '0':
while stack and stack[0] < i-maxJump:
stack.popleft()
if not stack:
return False
if stack[0] <= i-minJump:
stack.append(i)
return bool(stack) and stack[-1] == n-1
时间复杂度 $O(n)$ 。
运行时间：201 ms (beats 96.49%)，内存占用：20.50 MB (beats 48.76%)
解②贪心：其他
这里介绍本质相同地另外几个 $O(n)$ 的算法：
DP + 滑动窗口
利用一个数组 dp 记录扫描过的位置是否可跳达，使用一个变量 cnt 来追踪当前位置$i$ 的 [i-maxJump, i-minJump] 范围里可跳达位置的数量，到时候检查这个变量是否为零，就可以判断当前可跳位置是否可以跳到。
维护 cnt：
- 当
dp[i-minJump]是true时，说明随着窗口滑动新进来了一个可跳到的位置，cnt就加一； - 当
dp[i-maxJump-1]是false时，说明随着窗口滑动，原本尾部的可跳到的位置出去了，cnt就减一
基本代码和下面方法一样，这里就不赘写了。
前缀和
这个是官解，只不过用了一个记录可跳到位置的数量和的前缀数组 prefix 代替 dp，用前缀和之差代替对 cnt 的追踪。
这个有点儿意思得地方是，它用了 prefix[i-minJump] - prefix[i-maxJump-1] 来计算 [i-maxJump, i-minJump] 范围内可跳到位置的数量，让人想起了树状数组也采用同样的方法来计算区间值。
有一点让人不爽地是，必须单独处理 [0, maxJump+1] 部分的内容来初始化前缀树组。
from itertools import islice
def solve(s: str, minJump: int, maxJump: int) -> bool:
n = len(s)
if s[-1] != '0':
return False
if n <= maxJump+1:
return True
prefix = [1] * n
it = enumerate(s)
for i, v in islice(it, minJump, maxJump+1):
prefix[i] = prefix[i-1]
if v == '0':
prefix[i] += 1
for i, v in it:
prefix[i] = prefix[i-1]
if v == '0' and prefix[i-minJump] - prefix[i-maxJump-1]:
prefix[i] += 1
return prefix[-1] - prefix[-2] == 1
算法复杂度 $O(n)$ 。
运行时间：173 ms (beats 97.52%)，内存占用：21.07 MB (beats 25.62)
注解
