1871. 跳跃游戏 VII - 力扣（LeetCode）
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 -...
思路
首先题目明显的无后效性，可以用动态规划作答。
容易想到遍历一遍，从[minJump..maxJump]进行递推，但是看数据量 1 <= minJump <= maxJump < s.length <= 10^5 大概率会超时。线段树似乎可以，但是太重了。
逆向思考下，如果能够到达 x 点，那么在 [x-maxJump..x-minJump] 至少有一个点可以到达。这点借助前缀和可以在O(1)的复杂度内解决，那动态规划的方程式就由O(n^2)降到了O(n)。
代码
class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length();
// 是否可以跳到坐标
boolean[] dp = new boolean[n];
dp[0] = true;
// 到当前坐标为止能够到达的坐标数量
int[] prefix = new int[n];
// 本来prefix[0]应该设为1，但是这样需要把[0..minJump)都设为1，所以在不影响计算的情况下此处保持0
// prefix[0]= 1;
// 初始化边界，[minJump..maxJump]只要为0均可到达
for (int i = minJump; i <= maxJump; i++) {
prefix[i] = prefix[i - 1];
if (s.charAt(i) == '0') {
dp[i] = true;
prefix[i] += 1;
}
}
// 只要前面 [i-maxJump..i-minJump] 范围内有点能够到达此处就能到达
for (int i = maxJump + 1; i < n; i++) {
prefix[i] = prefix[i - 1];
if (s.charAt(i) == '0' && prefix[i - minJump] - prefix[i - maxJump - 1] > 0) {
dp[i] = true;
prefix[i] += 1;
}
}
return dp[n - 1];
}
}
1 个帖子 - 1 位参与者
来源: LinuxDo 最新话题查看原文