1871. 跳跃游戏 VII

题目地址(1871. 跳跃游戏 VII)

https://leetcode-cn.com/problems/jump-game-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. 当前点 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:

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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。