LeetCode 跳躍游戲 IV：二進制字符串的跳躍問題

題目描述

給定一個下標從 0 開始的二進制字符串?s?和兩個整數?minJump?和?maxJump。初始時，你位于下標 0 處（保證該位置為 '0'）。你需要判斷是否能到達字符串的最后一個位置（下標為?s.length - 1）。移動規則如下：

• 從位置?i?移動到?j，需滿足?i + minJump ≤ j ≤ min(i + maxJump, s.length - 1)。
• 目標位置?j?必須為 '0'。

解題思路分析

動態規劃 + 前綴和優化

核心思想

1. 動態規劃數組?dp：dp[i]?表示是否能到達位置?i。
2. 前綴和數組?pre：記錄從 0 到當前位置的可達狀態總和，用于快速計算區間和。
3. 有效區間：對于位置?j，其可跳躍的起始位置范圍為?[j - maxJump, j - minJump]。通過前綴和數組快速判斷該區間內是否有可達的位置。

關鍵步驟

1. 初始化：

   • 若最后一個字符為 '1'，直接返回?false。
   • dp[0] = true（初始位置可達）。
   • 前綴和數組?pre?記錄可達位置的累計數量。

2. 遍歷每個位置?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];}
}

代碼解釋

方法一關鍵點

1. 前綴和數組?pre：

   • pre[i]?表示前?i?個位置（即索引?0?到?i-1）的可達數。
   • 通過?pre[right+1] - pre[left]?快速計算區間?[left, right]?的可達數。

2. 有效區間計算：

   • left = j - maxJump，right = j - minJump，確保區間不越界。
   • 若區間為空（left > right），則當前位置不可達。

方法二優化

• 滾動窗口優化：
  • 直接維護當前窗口內的可達數?pre，無需額外數組。
  • 當?i?超過?minJump?時，將?dp[i - minJump]?加入窗口。
  • 當?i?超過?maxJump?時，將?dp[i - maxJump - 1]?移出窗口。

復雜度分析

• 時間復雜度：，每個位置僅遍歷一次。
• 空間復雜度：，需存儲?dp?數組和前綴和數組（方法一）或僅?dp?數組（方法二）。

總結與優化

1. 動態規劃是核心：通過?dp?數組記錄狀態，避免重復計算。
2. 前綴和優化：將區間查詢復雜度從??降至?，大幅提升效率。
3. 空間優化：方法二中僅需維護一個?pre?變量，進一步減少空間消耗。

擴展思考：若題目允許跳躍到 '1' 位置，但需額外條件（如跳躍次數限制），如何調整算法？

希望這篇博客對您有所幫助！如果需要進一步優化或補充細節，可以隨時告訴我～