题目如下

数据范围

显然n平方的时间复杂度会报超时错误,所以这道题不宜暴力。
这道题可以这么思考:
	设字符串为s minjump为min maxjump为max
	当s[i] = '0' 时考虑 当 i ∈[i - max,i - min](其中i - max ＞ 0)时可达
	所以这道题实际上就转变为判断当在[i - max,i - min]是否有'0'
	故我们可以使用前缀和来辅助同时用另一个数组来存储各个位置可达信息。

通过代码

class Solution {
public:
 
bool canReach(string s, int minJump, int maxJump) {
    int n = s.size();
    vector<int> pre(n);
    vector<int> ans(n);
    int left ,right;
    ans[0] = 1;
    for(int i = 0;i < minJump;i++) {
        pre[i] = 1;
    }
    for(int i = minJump;i < n;i++) {
        left = (i - maxJump >= 0)?(i - maxJump):0;
        right = i - minJump;
        if(s[i] == '0') {
            if(pre[right] - ((left - 1 >= 0)?pre[left - 1]:0) > 0) {
                ans[i] = 1;
            }else {
                ans[i] = 0;
            }
            
        }
        pre[i] = pre[i - 1] + ans[i];
    }

    return ans[n - 1];
}
};