leet1871.jump-game-vii

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

---

思路一

带剪枝的BFS。注意几点，

1. 从某个节点出发遍历所有可达的节点，需要记录这次遍历到哪儿了，避免下一次算出来的区间和这一次重叠。

class Solution {
public:
// cf. https://leetcode.cn/problems/jump-game-vii/description/comments/2994432/
    bool canReach(string s, int minJump, int maxJump) {
        const int n = s.size();
        queue<int> q;
        q.push(0);
        int end = 0;
        
        while (!q.empty()) {
	        int i = q.front();
	        q.pop();
	        
	        if (i == n - 1) return true;
	        
	        // 上一次已经考虑到end了，所以这次的beg可以从end+1开始，前面不用再考虑
	        int beg = max(i + minJump, end + 1);
	        end = min(i + maxJump, n - 1);
	        
	        for (int j = beg; j <= end; ++j) {
		        if (s[j] == '0') q.push(j);
	        }
        }
        return false;
    }
};

思路二

不太相关的差分数组。设字符串长度为 $n$，对字符数组（字符串）做如下游戏：

1. 遍历数组，从 $i=0$ 开始（先不考虑 s[i]='0' 的条件），给子区间 $[i+minJump,i+maxJump]$ 每个索引做一次标记，表示这个索引可以从下标 $i$ 跳过来，当然，若遇到边界则以边界值为准；
2. 记数组 $\{a_i{\}}_{i=0}^{n-1}$，其中 $a_i$ 表示原数组s[i]被做标记的次数。显然，$a_i>0$ 表示s[i]可以跳到。
3. 考虑 s[i] = '0' 才能被跳到，结合起来就是遍历数组，初始值 $a_0=1$，
   1. 若 s[i] = '0' 且 $a_i>0$，给子区间 $[i+minJump,i+maxJump]$ 做标记；
   2. 否则，跳过当前索引。
4. 遍历完原数组，$a_{n-1}>0$ 并且s[n-1] = '0'表示能跳到，否则不能。

抽象成上面的流程后，发现过程中涉及对子区间的批量增加，可以利用差分数组降低复杂度。

1. 注意，初始化差分数组相当于对 [0,0] 这个子区间批量加1，于是变成diff[0] += 1; diff[1] -= 1。

class Solution {
public:
// cf. https://leetcode.cn/problems/jump-game-vii/solutions/791314/qian-zhui-he-you-hua-dp-by-endlesscheng-k9d2
    bool canReach(string s, int minJump, int maxJump) {
        const int n = s.size();
        vector<int> diff(n + 1, 0);
        
        // 初始化差分数组
        diff[0] += 1;
        diff[1] -= 1;
        
        int psum = 0; // 记录前缀和
        for (int i = 0; i < n; ++i) {
	        psum += diff[i];
	        if (psum > 0 && s[i] == '0') { // 能跳到的条件
		        // 当区间越界，直接操作边界
		        diff[min(i + minJump, n)] += 1;
		        diff[min(i + maxJump + 1, n)] -= 1;
	        }
        }
        return psum > 0 && s.back() == '0';
    }
};

思路三

滑动窗口建模。参考：https://leetcode.cn/problems/jump-game-vii/solutions/791474/hua-chuang-si-xiang-dp-bu-xu-yao-qian-zh-j865

根据题意，坐标 j 可达的条件为，

1. s[j] = '0'
2. 在区间 [j - maxJump, j - minJump] 中存在一个可达的坐标 i

维护一个大小为 maxJump - minJump 的滑动窗口，记 cnt 为窗口中所有可达坐标数量之和。

1. 遍历到坐标 i 时，如果当前 cnt > 0，则说明在闭区间 [i - maxJump, i - minJump] 中至少存在一个坐标能跳到 i. 反之则说明此区间内不存在能移动到 i 的坐标。
2. 每次遍历判断完当前是否可达后，需要更新滑窗的信息。每次遍历，滑窗整体向右移动一格，因此需要考虑左边界缩减和右边界扩展对 cnt 的影响。当滑窗右移一格时，
   1. 左边界 i - maxJump 离开，如果 i - maxJump 是可达坐标，此时 cnt 需要减一
   2. 右边界 i - minJump + 1 新加入，如果这个坐标可达，此时 cnt 需要加一
3. 遍历时，直接从 i = minJump 开始，因为当 i < minJump 时，滑窗右边界 i - minJump < 0，即此时不存在对应的闭区间。

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        const int n = s.size();
        vector<int8_t> reachable(n, 0);
 
        int cnt = 1; // 因为 s[0] 可达
        reachable[0] = 1;
 
        for (int i = minJump; i < n; ++i) {
	        if (s[i] == '0' && cnt > 0) {
		        reachable[i] = 1;
	        }
	        // 左边界痛失可达
	        if (i >= maxJump && reachable[i - maxJump]) {
		        --cnt;
	        }
	        // 右边界新增可达
	        if (reachable[i - minJump + 1]) {
		        ++cnt;
	        }
        }
        return reachable[n-1] == 1;
    }
};