当前位置：首页 > news >正文

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

news 来源：原创 2025/8/26 1:27:10

题面：

在这里插入图片描述

数据范围：

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

思路 & Code

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

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

$d p [in d e x] == 0$ ，说明 $in d e x$ 位置没有被跳到
$d p [in d e x] == 1$ ， $in d e x$ 可以被跳到

那么，对于当前点 $in d e x$ 都得判断 $[min (i - ma x J u m p), 0), i - min J u m p]$ 区间内的所有可跳点，这样太暴力了， $O (nk)$ 。必须考虑优化。

差分维护

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

维护个前缀和，每次到 $s [i] = =^{'} 0^{'}$ （可跳点）时，判断区间 $[min (i - ma x J u m p), 0), i - min J u m p]$ 是否存在可跳点 $0$ ，即 $p re [i - min J u m p] - p re [i - ma x J u m p - 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;
}

题面：

数据范围：

思路 & Code

差分维护

Code：

Code：

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

Code：

相关文章：