LeetCode1871 跳跃游戏VII-EW帮帮网

LeetCode 跳跃游戏 IV：二进制字符串的跳跃问题

题目描述

给定一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump。初始时，你位于下标 0 处（保证该位置为 '0'）。你需要判断是否能到达字符串的最后一个位置（下标为 s.length - 1）。移动规则如下：

从位置 i 移动到 j，需满足 i + minJump ≤ j ≤ min(i + maxJump, s.length - 1)。
目标位置 j 必须为 '0'。

解题思路分析

动态规划 + 前缀和优化

核心思想

动态规划数组 dp：dp[i] 表示是否能到达位置 i。
前缀和数组 pre：记录从 0 到当前位置的可达状态总和，用于快速计算区间和。
有效区间：对于位置 j，其可跳跃的起始位置范围为 [j - maxJump, j - minJump]。通过前缀和数组快速判断该区间内是否有可达的位置。

关键步骤

初始化：
- 若最后一个字符为 '1'，直接返回 false。
- dp[0] = true（初始位置可达）。
- 前缀和数组 pre 记录可达位置的累计数量。
遍历每个位置 j：
- 若当前位置为 '1'，跳过。
- 计算可跳跃的起始位置范围 [left, right]。
- 利用前缀和数组快速查询该区间内是否有可达位置。
- 更新 dp[j] 和前缀和数组 pre。

代码实现

方法一：标准动态规划 + 前缀

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        if (s.charAt(n - 1) != '0') return false;
        
        boolean[] dp = new boolean[n];
        dp[0] = true;
        int[] pre = new int[n + 1]; // pre[i] 表示前i个位置的可达数
        pre[1] = 1;
        
        for (int j = 1; j < n; j++) {
            if (s.charAt(j) != '0') {
                pre[j + 1] = pre[j];
                continue;
            }
            
            int left = j - maxJump;
            int right = j - minJump;
            left = Math.max(left, 0);
            right = Math.min(right, j - 1);
            
            if (left > right) {
                pre[j + 1] = pre[j];
                continue;
            }
            
            int sum = pre[right + 1] - pre[left];
            dp[j] = sum > 0;
            pre[j + 1] = pre[j] + (dp[j] ? 1 : 0);
        }
        return dp[n - 1];
    }
}

方法二：简化前缀和处理

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        if (s.charAt(n - 1) != '0') return false;
        
        boolean[] dp = new boolean[n];
        dp[0] = true;
        int pre = 0; // 当前窗口内的可达数
        
        for (int i = 1; i < n; i++) {
            if (i >= minJump) pre += dp[i - minJump] ? 1 : 0;
            if (i > maxJump) pre -= dp[i - maxJump - 1] ? 1 : 0;
            dp[i] = s.charAt(i) == '0' && pre > 0;
        }
        return dp[n - 1];
    }
}

代码解释

方法一关键点

前缀和数组 pre：
- pre[i] 表示前 i 个位置（即索引 0 到 i-1）的可达数。
- 通过 pre[right+1] - pre[left] 快速计算区间 [left, right] 的可达数。
有效区间计算：
- left = j - maxJump，right = j - minJump，确保区间不越界。
- 若区间为空（left > right），则当前位置不可达。

方法二优化

滚动窗口优化：
- 直接维护当前窗口内的可达数 pre，无需额外数组。
- 当 i 超过 minJump 时，将 dp[i - minJump] 加入窗口。
- 当 i 超过 maxJump 时，将 dp[i - maxJump - 1] 移出窗口。

复杂度分析

时间复杂度： $O(n)$ ，每个位置仅遍历一次。
空间复杂度： $O(n)$ ，需存储 dp 数组和前缀和数组（方法一）或仅 dp 数组（方法二）。

总结与优化

动态规划是核心：通过 dp 数组记录状态，避免重复计算。
前缀和优化：将区间查询复杂度从 $O(n)$ 降至 $O(1)$ ，大幅提升效率。
空间优化：方法二中仅需维护一个 pre 变量，进一步减少空间消耗。

扩展思考：若题目允许跳跃到 '1' 位置，但需额外条件（如跳跃次数限制），如何调整算法？

希望这篇博客对您有所帮助！如果需要进一步优化或补充细节，可以随时告诉我～

LeetCode1871 跳跃游戏VII