第六章 - 高频考题(困难)
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:
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 ,并观察其是否满足上述条件即可。
代码:
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。
朴素的做法是遍历:
bools = [false, true, false, false, true];
bools[2] || bools[3];
如果我想知道任意合法区间 [s,e] 是否有 true。
则可以:
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 的个数。
代码:
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:
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. 1.
    当前点 i 可以到跳的点为 j。其中 j 属于区间[i + minJump, i + maxJump]。判断 j 是否存在于 zeros。 (操作 1)
  2. 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:
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)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。