[LeetCode 1871] 跳跃游戏 7(Ⅶ)

题面：

数据范围：

$2\le s.length\le 10^5$
$s[i]$ 要么是 ${}^{\prime }{0}^{\prime }$ ，要么是 ${}^{\prime }{1}^{\prime }$
$s[0]==0$
$1\le minJump\le maxJump<s.length$

思路 & Code

重点： 当 $s[i]==0$ 时，才能继续跳，也才能被跳到。
So，自然会想到存储所有能够跳到的 $0$ 点，而当前 $0$ 点必然是从存储的 $0$ 点跳过来的。容易想到可以暴力状态转移。

用一数组 $dp$ 存储下标状态：

1. $dp[index]==0$，说明 $index$ 位置没有被跳到
2. $dp[index]==1$，$index$ 可以被跳到

那么，对于当前点 $index$ 都得判断 $[min(i-maxJump),0),i-minJump]$ 区间内的所有可跳点，这样太暴力了，$O(nk)$。必须考虑优化。

差分维护

时间复杂度： $O(n)$
空间复杂度： $O(n)$

维护个前缀和，每次到 $s[i]={=}^{\prime }{0}^{\prime }$（可跳点）时，判断区间 $[min(i-maxJump),0),i-minJump]$是否存在可跳点 $0$，即 $pre[i-minJump]-pre[i-maxJump-1]$是否大于零。（当然了，区间得注意下）

Code：

bool canReach(string s, int minJump, int maxJump) {
    int n = s.size();
    vector<int> dp(n, 0), pre(n, 0);
    dp[0] = 1;
    for(int i = 0; i < minJump; ++i) pre[i] = 1;
    for(int i = minJump; i < n; ++i) {
        int l = i - maxJump, r = i - minJump;
        // 差分判断可跳区间内是否存在 0 点
        if(s[i] == '0' && pre[r] - (l >= 1 ? pre[l - 1] : 0) > 0) dp[i]=1;
        pre[i] = pre[i-1] + dp[i];
    }
    return dp[n-1];
    /* 
    当然了，不用dp数组维护也可以
    写成：
    for(int i = minJump; i < n; ++i) {
		int l = i - maxJump, r = i - minJump;
		if(s[i] == '0' && pre[r] - (l >= 1 ? pre[l - 1] : 0) > 0) {
			if(i == n-1) return true;
			pre[i] = pre[i-1]+1;
		} else pre[i] = pre[i-1];
	}
	return false;
    */
}

当然了，由于可跳区间其实就是一个滑动窗口，直接拿个临时变量存储可跳点个数就行，但得存个状态哈

Code：

bool canReach(string s, int minJump, int maxJump) {
    int n = s.size(), cnt = 1;
    vector<bool> dp(n, false);
    dp[0] = true;
    for(int i = minJump; i < n; ++ i) {
        if(s[i] == '0' && cnt) dp[i] = true;
        // 可跳区间要右移啦（其实就是动态维护滑动窗口的思想啦）
        // 如果左端点是可跳的，cnt--；如果要加入的点（右端点）是可跳的，cnt++
        if(i - maxJump >= 0 && dp[i - maxJump]) --cnt;
        if(i - minJump + 1 < n && dp[i - minJump + 1]) ++ cnt;
    }
    return dp[n-1];
}

动态维护滑动窗口（可跳区间）

上面都提到滑动窗口了，那直接拿个队列去维护滑动窗口也很简单啦。时间复杂度和空间复杂度都是 $O(n)$。

Code：

bool canReach(string s, int minJump, int maxJump) {
    int n = s.size();
    if(s[n-1] == '1') return false;
    queue<int> q;
    q.push(0);
    for(int i = minJump; i < n; ++i) {
        if(s[i] == '1') continue;
        while(!q.empty() && q.front() < i - maxJump) q.pop();
        if(!q.empty() && q.front() <= i - minJump) {
            if(i == n-1) return true;
            q.push(i);
        }
    }
    return false;
}