class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
}
};
1871. 跳跃游戏 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 <= 105s[i] 要么是 '0' ，要么是 '1's[0] == '0'1 <= minJump <= maxJump < s.length原站题解
java 解法, 执行用时: 10 ms, 内存消耗: 43.4 MB, 提交时间: 2023-07-05 10:30:30
class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
int len = s.length();
// 最后 s.length - 1 处，如果不是 ‘0’ 则不可能为 true
if(s.charAt(len-1) == '1'){
return false;
}
// can[i] 为 true 表示 下表 i 处可达到
boolean[] can = new boolean[len];
// 【题意】下标 0 处，且该位置的值一定为 '0'
can[0] = true;
for(int i=0,limit=0;i<len;i++){
if(can[i] == false){
continue;
}
// 向前探索是否可达，对于已经探索过的位置[0 ～ limit) 则跳过
int left = Math.max(limit, i + minJump), right = Math.min(i+maxJump, len-1);
for(int j=left; j <= right;j++){
can[j] = s.charAt(j) == '0';
}
// limit 表示坐标 [0 ～ limit) 的位置已经判断过是否可到达
limit = right + 1;
}
return can[len -1];
}
}
java 解法, 执行用时: 7 ms, 内存消耗: 43.2 MB, 提交时间: 2023-07-05 10:29:32
/**
* 差分数组
* 假设原数组为a,差分数组 diff, 在遍历的时候sum + =diff[i],sum即为a[i]，
* 条件(sum>0 && s.charAt(i)=='0')满足时表示第i个位置可以达到，
* 将原数组a[i+minJump]~a[i+maxJump]均+1，等价于diff[i+minJump]+1，diff[i+maxJump+1]-1
**/
class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length(),sum = 0;
int[] diff = new int[n+maxJump+1];
diff[0] = 1;
diff[1] = -1;
for ( int i=0; i<n; i++) {
sum += diff[i];
if ( sum > 0 && s.charAt(i) == '0' ) {
diff[i+minJump]++;
diff[i+maxJump+1]--;
}
}
return sum > 0 && s.charAt(n-1) == '0';
}
}
golang 解法, 执行用时: 12 ms, 内存消耗: 8 MB, 提交时间: 2023-07-05 10:26:56
func canReach(s string, minJump int, maxJump int) bool {
n := len(s)
if s[n - 1] == '1' {
return false
}
q := []int{0}
for i := 1; i < n; i++ {
for len(q) > 0 && q[0] + maxJump < i {
q = q[1:]
}
if len(q) > 0 && s[i] == '0' && q[0] + minJump <= i {
q = append(q, i)
}
}
return len(q) > 0 && q[len(q) - 1] == n - 1
}
golang 解法, 执行用时: 12 ms, 内存消耗: 7.1 MB, 提交时间: 2023-07-05 10:26:01
// 前缀和优化dp
func canReach(s string, minJump, maxJump int) bool {
n := len(s)
sum := make([]int, n+1)
sum[1] = 1
for i := 1; i < n; i++ {
sum[i+1] = sum[i]
if i >= minJump && s[i] == '0' && sum[i-minJump+1] > sum[max(0, i-maxJump)] {
sum[i+1]++
}
}
return sum[n] > sum[n-1]
}
func max(a, b int) int { if a > b { return a }; return b }
python3 解法, 执行用时: 384 ms, 内存消耗: 21.1 MB, 提交时间: 2023-07-05 10:23:43
class Solution:
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
n = len(s)
f, pre = [0] * n, [0] * n # f[i]: 从0开始，s[i]是否可达
f[0] = 1
# 由于我们从 i=minJump 开始动态规划，因此需要将 [0,minJump) 这部分的前缀和预处理出来
for i in range(minJump):
pre[i] = 1
for i in range(minJump, n):
left, right = i - maxJump, i - minJump
if s[i] == "0":
total = pre[right] - (0 if left <= 0 else pre[left - 1])
f[i] = int(total != 0)
pre[i] = pre[i - 1] + f[i]
return bool(f[n - 1])
cpp 解法, 执行用时: 36 ms, 内存消耗: 16.5 MB, 提交时间: 2023-07-05 10:22:33
class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
int n = s.size();
vector<bool> dp(n, false); // dp[i], s[i]是否可达
dp[0] = true;
int cnt = 1; //滑窗cnt初始化，一开始i = 0是可达的，所以cnt初始化为1
for (int i = minJump; i < n; ++i) {
//判断当前坐标是否可达
if (s[i] == '0' && cnt > 0) {
dp[i] = true;
}
//滑窗移动后左端坐标离开带来的更新
if (i >= maxJump && dp[i - maxJump]) {
--cnt;
}
//滑窗移动后右端坐标加入带来的更新
if (dp[i - minJump + 1]) {
++cnt;
}
}
return dp[n - 1];
}
};