Medium

题目描述

给你一个下标从 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 <= 10^5
  • s[i] 要么是 '0'，要么是 '1'
  • s[0] == '0'
  • 1 <= minJump <= maxJump < s.length

解题思路

这是一道动态规划题目，核心思想是使用滑动窗口优化状态转移。

基本思路： 定义 dp[i] 表示是否能到达位置 i。对于每个位置 j，如果 s[j] == '0'，需要检查在区间 [j-maxJump, j-minJump] 内是否存在可达位置。

朴素DP的问题： 直接检查区间会导致时间复杂度 O(n²)，对于 10⁵ 的数据量会超时。

滑动窗口优化： 使用滑动窗口维护当前可达位置的数量。具体来说：

  1. 维护一个窗口 [left, right]，表示当前能跳到位置 i 的所有可达位置的区间
  2. 使用 count 记录当前窗口内可达位置的数量
  3. 当窗口滑动时，动态更新 count

算法步骤：

  1. 初始化 dp[0] = true，其他位置为 false
  2. 对每个位置 i，计算能跳到它的位置区间 [left, right] = [i-maxJump, i-minJump]
  3. 使用滑动窗口维护区间内可达位置数量
  4. 如果 s[i] == '0' 且区间内有可达位置，则 dp[i] = true

这种方法将时间复杂度优化到 O(n)。

代码实现

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.length();
        vector<bool> dp(n, false);
        dp[0] = true;
        
        int count = 0; // 当前窗口内可达位置的数量
        
        for (int i = 1; i < n; i++) {
            // 计算能跳到位置i的区间[left, right]
            int left = i - maxJump;
            int right = i - minJump;
            
            // 窗口右端点进入
            if (right >= 0 && dp[right]) {
                count++;
            }
            
            // 窗口左端点移出
            if (left - 1 >= 0 && dp[left - 1]) {
                count--;
            }
            
            // 如果当前位置是'0'且窗口内有可达位置
            if (s[i] == '0' && count > 0) {
                dp[i] = true;
            }
        }
        
        return dp[n - 1];
    }
};

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        dp = [False] * n
        dp[0] = True
        
        count = 0  # 当前窗口内可达位置的数量
        
        for i in range(1, n):
            # 计算能跳到位置i的区间[left, right]
            left = i - maxJump
            right = i - minJump
            
            # 窗口右端点进入
            if right >= 0 and dp[right]:
                count += 1
            
            # 窗口左端点移出
            if left - 1 >= 0 and dp[left - 1]:
                count -= 1
            
            # 如果当前位置是'0'且窗口内有可达位置
            if s[i] == '0' and count > 0:
                dp[i] = True
        
        return dp[n - 1]

public class Solution {
    public bool CanReach(string s, int minJump, int maxJump) {
        int n = s.Length;
        bool[] dp = new bool[n];
        dp[0] = true;
        
        int count = 0; // 当前窗口内可达位置的数量
        
        for (int i = 1; i < n; i++) {
            // 计算能跳到位置i的区间[left, right]
            int left = i - maxJump;
            int right = i - minJump;
            
            // 窗口右端点进入
            if (right >= 0 && dp[right]) {
                count++;
            }
            
            // 窗口左端点移出
            if (left - 1 >= 0 && dp[left - 1]) {
                count--;
            }
            
            // 如果当前位置是'0'且窗口内有可达位置
            if (s[i] == '0' && count > 0) {
                dp[i] = true;
            }
        }
        
        return dp[n - 1];
    }
}

var canReach = function(s, minJump, maxJump) {
    const n = s.length;
    const dp = new Array(n).fill(false);
    dp[0] = true;
    
    let count = 0; // 当前窗口内可达位置的数量
    
    for (let i = 1; i < n; i++) {
        // 计算能跳到位置i的区间[left, right]
        const left = i - maxJump;
        const right = i - minJump;
        
        // 窗口右端点进入
        if (right >= 0 && dp[right]) {
            count++;
        }
        
        // 窗口左端点移出
        if (left - 1 >= 0 && dp[left - 1]) {
            count--;
        }
        
        // 如果当前位置是'0'且窗口内有可达位置
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)遍历字符串一次，每个位置的操作都是常数时间
空间复杂度O(n)使用dp数组存储每个位置的可达状态

相关题目