題目描述:
給定一個二進位字串 s(由 '0' 和 '1' 組成),以及整數 minJump 和 maxJump。起始位置為索引 0,只能跳到值為 '0' 的位置,每次跳躍距離在 [minJump, maxJump] 之間。判斷能否到達最後一個位置。
解題思路: 使用 DP + 前綴和(或滑動窗口差分技巧)。
dp[i] = 是否能到達位置 i。初始 dp[0] = true。s[i] == '0' 且存在某個 j 滿足 i - maxJump <= j <= i - minJump 使得 dp[j] = true。pre[i] = dp[0] + dp[1] + ... + dp[i],則範圍內的可達位置數 = pre[i-minJump] - pre[i-maxJump-1],若大於 0 則 i 可達。時間複雜度:O(n) — 一次遍歷,每個位置做常數操作。
空間複雜度:O(n) — DP 陣列。
1. If s[n-1] == '1', return false 2. Initialize dp[0..n-1] = false, dp[0] = true 3. Initialize reachable = 0 (count of true dp values in sliding window) 4. For i from 1 to n-1: a. If i >= minJump and dp[i - minJump] is true: reachable++ b. If i > maxJump and dp[i - maxJump - 1] is true: reachable-- c. If s[i] == '0' and reachable > 0: dp[i] = true 5. Return dp[n-1]
BFS O(n):從位置 0 開始 BFS,維護一個指標記錄已經嘗試過的最遠位置,避免重複訪問。每個位置最多入隊一次,總時間 O(n)。
前綴和 DP O(n):用整數前綴和陣列替代滑動窗口計數器,pre[i] = sum(dp[0..i])。dp[i] = (s[i]=='0') && (pre[i-minJump] - pre[max(0, i-maxJump)-1] > 0)。邏輯等價但需要額外的前綴和陣列。