LeetCode 5765. 跳跃游戏 VII
原题链接
中等
作者:
ITNXD
,
2021-05-23 21:19:11
,
所有人可见
,
阅读 257
详细请查看注释
参考代码:
class Solution {
/*
状态表示:f[i]表示是否可以跳到i
状态计算:
f[i] = f[i - b] | f[i - b + 1] ..... | f[i - a]
两层循环为1e10,因此需要优化第二层循环,由于我们只需要判断i - b ~ i - a这个区间是否有可以到达的即f[x] = 1;
因此我们可以使用前缀和进行维护,前缀和大于1表示这段区间至少有一个可达,即f[i]可达!否则不可达!
前缀和:s[i]表示f[i]数组的前缀和!
*/
public:
bool canReach(string str, int a, int b) {
int n = str.size();
vector<int> f(n + 1), s(n + 1);
// 初始化:可以跳到第一个点 f[1] = 1 s[1] = 1
f[1] = 1, s[1] = 1;
for(int i = 2; i <= n; i ++){
// 当前位置为0(下标从0开始,因此为i - 1)且范围i - a >= 1才可跳!
if(str[i - 1] == '0' && i - a >= 1){
int l = max(1, i - b), r = i - a;
if(s[r] - s[l - 1] > 0) f[i] = 1;
}
// 处理前缀和
s[i] = s[i - 1] + f[i];
}
return f[n];
}
};