Leetcode 1871. Jump Game VII

[Woodyiiiiiii]

这道题我还想着用BFS来做，但发现在最坏情况下(minJump=1, maxJump=99999)会达到O(n^2)的复杂度，那么BFS就不能做了。

再看下题目，把重点放在minJump和maxJump这两个变量上，有点类似sliding window / two pointers。遍历数组，到某个点i，如何判断这个点i是否在之前的某个有效j的辐射范围[j+minJump, j+maxJump]里呢？直接判断i-minJump/i-maxJump就行了。如果在多个范围内，就用一个变量叠加表示。

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        if (s.charAt(n - 1) == '1') {
            return false;
        }
        boolean[] dp = new boolean[n];
        dp[0] = true;
        int prev = 0;
        for (int i = 1; i < n; ++i) {
            if (i >= minJump) {
                prev += dp[i - minJump] ? 1 : 0;
            }
            if (i > maxJump) {
                prev -= dp[i - maxJump - 1] ? 1 : 0;
            }
            dp[i] = prev > 0 && s.charAt(i) == '0';
        }
        return dp[n - 1];
    }
}

---

• 1871. Jump Game VII