题目描述
给你一个下标从 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
。
样例
输入:s = "011010", minJump = 2, maxJump = 3
输出:true
解释:
第一步,从下标 0 移动到下标 3。
第二步,从下标 3 移动到下标 5。
输入:s = "01101110", minJump = 2, maxJump = 3
输出:false
限制
2 <= s.length <= 10^5
s[i]
要么是'0'
,要么是'1'
。s[0] == '0'
1 <= minJump <= maxJump < s.length
算法1
(队列) $O(n)$
- 使用队列记录当前符合条件的转移下标。初始时维护一个队列,队列中只有 $0$ 下标。
- 遍历每个位置,如果当前队列为空,则直接返回 $false$。
- 如果队头元素的下标小于 $i - maxJump$,则出队。
- 如果当前位置为
0
,且队头元素的下标小于等于 $i - minJump$,则当前位置进队。因为当前位置可以从队头的位置转移过来。 - 如果 $s.length - 1$ 位置入队了,则返回 $true$。
时间复杂度
- 每个位置最多进队一次,出队一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储队列。
C++ 代码
class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
const int n = s.size();
queue<int> q;
q.push(0);
for (int i = 1; i < n && !q.empty(); i++) {
while (!q.empty() && q.front() < i - maxJump)
q.pop();
if (s[i] == '0' && !q.empty() && q.front() <= i - minJump) {
if (i == n - 1)
return true;
q.push(i);
}
}
return false;
}
};
算法2
(前缀和) $O(n)$
- 假设 $i$ 位置可以到达,则 $i$ 位置的权值为 $1$,维护一个权值的前缀和。
- 对于当前位置 $i$,求出可被转移的区间 $[i - maxJump, i - minJump]$,如果区间和大于 $0$,且当前位置为
0
,则 $f(i) = f(i - 1) + 1$;否则为 $f(i) = f(i - 1)$。 - 判断 $s.length - 1$ 的权值是否为 $1$。
时间复杂度
- 每个位置遍历一次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储前缀和数组。
C++ 代码
class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
const int n = s.size();
vector<int> f(n, 0);
f[0] = 1;
for (int i = 1; i < n; i++) {
int l = max(0, i - maxJump);
int r = i - minJump;
if (l <= r && s[i] == '0')
f[i] = (f[r] - (l == 0 ? 0 : f[l - 1])) > 0;
f[i] += f[i - 1];
}
return f[n - 1] - f[n - 2] > 0;
}
};