> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1871.jump-game-vii.md).
# 1871. 跳跃游戏 VII
### 题目地址(1871. 跳跃游戏 VII)
### 题目描述
```
给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。一开始，你在下标 0 处，且该位置的值一定为 '0' 。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处：
i + minJump <= j <= min(i + maxJump, s.length - 1) 且
s[j] == '0'.
如果你可以到达 s 的下标 s.length - 1 处，请你返回 true ，否则返回 false 。
示例 1：
输入：s = "011010", minJump = 2, maxJump = 3
输出：true
解释：
第一步，从下标 0 移动到下标 3 。
第二步，从下标 3 移动到下标 5 。
示例 2：
输入：s = "01101110", minJump = 2, maxJump = 3
输出：false
提示：
2 <= s.length <= 105
s[i] 要么是 '0' ，要么是 '1'
s[0] == '0'
1 <= minJump <= maxJump < s.length
```
### 前置知识
* BFS
* 动态规划
* 前缀和
### 公司
* 暂无
### BFS(超时)
#### 思路
我们可以对问题进行抽象。将 0 抽象为图中的点，将每一个 0 与**其能够到达的比它索引大的 0**抽象为边。那么问题转化为从索引为 0 的点与索引为 n - 1 的点**是否联通**。我们有很多方法能够解决这个问题，不妨使用 BFS。
#### 关键点
* 将题目抽象为图的联通问题
#### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
if s[-1] == '1': return False
zeroes = set([i for i in range(len(s)) if s[i] == '0'])
q = set([0])
while q:
cur = q.pop()
if cur == len(s) - 1: return True
for nxt in range(cur + minJump, min(cur + maxJump, len(s)) + 1):
if nxt in zeroes and nxt not in q:
q.add(nxt)
return False
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n^2)$
* 空间复杂度：$O(n)$
### 动态规划
#### 思路
定义 dp(i) 为从索引为 0 的点是否能够到达索引为 i 的点。显然 dp(i) 只有在满足以下两个条件才为 true：
* s\[i] == '0'
* s\[j] == '0' 其中 max(0, i - maxJump) <= j <= max(0, i - minJump)
于是，我们可以枚举所有满足条件的 j ，并观察其是否满足上述条件即可。
代码：
```py
class Solution:
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
def dp(pos):
if pos == len(s) - 1: return True
return s[pos] == '0' and any([dp(i) for i in range(pos + minJump, min(len(s), pos + maxJump + 1))])
if s[-1] == '1': return False
return dp(0)
```
由于枚举 i 和 j 的复杂度为都为 $O(n)$，因此总的时间复杂度为 $O(n^2)$，代入题目会超时。
我们需要对其进行优化。我们发现算法条件在于寻找满足条件的 j，而满足条件的 j 实际上就是区间\[max(0,i-maxJump), max(0, i-minJump)] **中可以从 0 点到达的点**。
换句话说就是 **dp 数组的区间 \[max(0,i-maxJump), max(0, i-minJump)] 中是否存在一个 true**。
那么这该如何求呢？我举个例子你就懂了。
比如一个数组 \[false, true, false, false, true]，我想知道区间 \[2,3] 是否有 true。
朴素的做法是遍历：
```js
bools = [false, true, false, false, true];
bools[2] || bools[3];
```
如果我想知道任意合法区间 \[s,e] 是否有 true。
则可以：
```js
bools = [false, true, false, false, true]
for(let i = s; i < min(e,len(bools)); i++) {
if bools[i]: return true
}
return false
```
实际上，我们有可以将 bools 映射到整数，其中 false 映射为 0，true 映射为 1，并对 bools 求前缀和。这样就可以通过前缀和在 $O(1)$ 时间获取到任意区间的 true 的个数。
代码：
```js
bools = [false, true, false, false, true];
// bools 映射为 [0,1,0,0,1]
// pres 为 [0,1,1,1,2]
return pres[e] - s == 0 ? 0 : pres[s - 1];
```
#### 关键点
* 对 DP 数组本身求前缀和，而不是原数组
#### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
n = len(s)
pres = [0] * n
dp = [0] * n
dp[0] = pres[0] = 1
for i in range(1, n):
l = i - maxJump - 1
r = i - minJump
dp[i] = s[i] == '0' and (0 if r < 0 else pres[r]) - (0 if l < 0 else pres[l]) > 0
pres[i] = pres[i-1] + dp[i]
return dp[-1]
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$
### 平衡二叉树
#### 思路
我们可以将所有的 0 的索引按照升序顺序存起来，不妨令这个存储 0 索引的数据结构名为 zeros。
然后继续使用前面提到的动态规划思路，即 dp(i) 表示是否可从索引为 0 的点到达索引为 1 的点。唯一不同的是，这里不使用前缀和加速。
对于每一个可以到达的点（初始为索引为 0 的点），我们都执行一下判断：
1. 当前点 i 可以到跳的点为 j。其中 j 属于区间\[i + minJump, i + maxJump]。判断 j 是否存在于 zeros。 （操作 1）
2. 如果存在 zero\[k] == j 。则令 dp\[j] = true（操作 2）
最后返回最后 dp\[n] 即可。
这种做法时间复杂度取决于 zeros 的数据结构。由于 zero 需要支持区间查找（操作 1），并且 zeros 是升序的，因此使用数组来存储就没问题。区间查找使用二分即可。
不过由于 zeros 最差的情况下可以到达 n 的数据规模，而此时操作 2 复杂度可以到达 $O(n)$，因此对于全为 0 的情况，时间复杂度为 $O(n^2)$。
我们可以使用平衡二叉树，并在每次操作 2 结束后将 v 从 zeros 移除来进行加速（平衡二叉树删除只需要 logn 时间）
并且由于 zeros 中的值都最多只会被访问一次，因此时间复杂度为 $O(n)$。但是我们使用二分查找时间复杂度是 $logn$，因此总的时间不大于 $nlogn$。之所以说不大于，是因为 zeros 在不断变小，因此每次二分时间也在不断缩减。
#### 关键点
* 使用平衡二叉树不断执行删除以降低复杂度
#### 代码
* 语言支持：Python3
Python3 Code:
```python
from sortedcontainers import SortedList
class Solution:
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
if s[-1] == '1': return False
zeroes = SortedList([i for i in range(len(s)) if s[i] == '0'])
dp = [False] * len(s)
dp[0] = True
for i in range(len(s)):
if dp[i]:
l = zeroes.bisect_left(i + minJump)
r = zeroes.bisect_right(i + maxJump)
for v in [zeroes[i] for i in range(l, r)]:
dp[v] = True
zeroes.remove(v)
return dp[-1]
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(nlogn)$
* 空间复杂度：$O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
