[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;
}