跳跃游戏 VII

难度: Medium

给你一个下标从 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 <= 10⁵
s[i] 要么是 '0' ，要么是 '1'
s[0] == '0'
1 <= minJump <= maxJump < s.length

Submission

运行时间: 23 ms

内存: 16.3 MB

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        dp = [True] + [False] * (n-1)
        count = 1

        for i in range(minJump, n):
            if s[i] == '0' and count > 0:
                dp[i] = True
            
            if i >= maxJump and dp[i-maxJump]:
                count -= 1
            
            if dp[i-minJump + 1]:
                count += 1

        return dp[-1]

Explain

该题解采用了动态规划的方法，其中dp数组用于记录从起点至每个位置是否可达。dp[i]为True表示可以到达位置i，初始状态是dp[0]为True（起点），其余为False。接着，使用变量count来记录在当前位置i可达时，有效的可以作为跳跃起点的位置的数目。当遍历到某个位置i时，如果该位置为'0'且count大于0，说明存在至少一个位置j（j < i）使得从j跳到i是可行的，因此将dp[i]设置为True。在遍历的过程中，如果i超过了maxJump，需要从count中减去不再在范围内的dp[i-maxJump]，同时，每当向前移动一个位置，就需要检查是否有新的位置成为有效的起跳点，并更新count。通过这种方式，可以有效地更新dp数组，最终dp[n-1]的值即为结果。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)  # 输入字符串长度
        dp = [True] + [False] * (n-1)  # 初始化dp数组，dp[0]为True，其余为False
        count = 1  # 初始化可达起点的数量

        for i in range(minJump, n):  # 从minJump开始遍历至字符串末尾
            if s[i] == '0' and count > 0:  # 如果当前位置为'0'且存在可达的起点
                dp[i] = True  # 标记当前位置可达

            if i >= maxJump and dp[i-maxJump]:  # 如果当前位置超过最大跳跃距离，更新count
                count -= 1  # 减少一个超出跳跃范围的起点

            if dp[i-minJump + 1]:  # 检查新的可达起点
                count += 1  # 增加一个可用的起点

        return dp[-1]  # 返回最后一个位置是否可达

Explore

在此题解中，`count`变量用于记录在当前遍历的位置`i`时，位于`[i-maxJump, i-minJump]`区间内的可达起点数量。由于起始位置0是确定可达的（`dp[0]`为True），所以`count`的初始值设为1。这表示在开始时，有一个确定的起跳点（即位置0），后续的遍历会根据`dp`数组的更新来调整`count`的值，确保其反映当前可用的起跳点数量。

由于玩家从位置0出发，并且每次跳跃至少需要`minJump`的距离，因此从位置0到`minJump-1`的距离内是无法直接到达的，没有必要检查这部分位置。因此，直接从`minJump`开始遍历，可以减少不必要的计算，并且遍历的起始点是根据题目给定的最小跳跃距离确定的。

`count`表示当前位置`i`前可以作为起跳点的位置数量，如果`count`大于0，意味着至少有一个位置（在`[i-maxJump, i-minJump]`范围内）是可达的，并且可以从那里跳到当前位置`i`（假设`s[i]`为'0'），这使得当前位置也变为可达。如果`count`为0，则表示没有可用的起跳点到达当前位置，当前位置`i`不可达。因此，`count > 0`是`dp[i] = True`的必要条件。