給定一個二進位字串
s（以 ‘0’ 開頭）和兩個整數minJump、maxJump。從位置 0 出發，每次可以跳minJump到maxJump步，但只能落在 ‘0’ 的位置上。判斷能否到達最後一個位置。
Example:
Input: s = “011010”, minJump = 2, maxJump = 3 Output: true
Intuition
TIP
用滑動視窗或前綴和記錄哪些位置可達，避免重複檢查。
- 暴力 BFS 會超時，因為每個可達位置都要檢查
maxJump - minJump + 1個後繼 - 用前綴和或滑動視窗追蹤「可達位置數」，O(1) 判斷某位置是否有可達的前驅
- 若
[i - maxJump, i - minJump]範圍內有可達位置且s[i] == '0'，則i可達
Approaches
1. BFS + Optimization — O(n) / O(n)
- Idea: 用 BFS 搜索，但維護一個指標避免重複掃描已處理的範圍。
- Time:
O(n) - Space:
O(n)
class Solution {
fun canReach(s: String, minJump: Int, maxJump: Int): Boolean {
val n = s.length
if (s[n - 1] == '1') return false
val queue = ArrayDeque<Int>()
queue.add(0)
var farthest = 0
while (queue.isNotEmpty()) {
val i = queue.removeFirst()
val start = maxOf(i + minJump, farthest + 1)
val end = minOf(i + maxJump, n - 1)
for (j in start..end) {
if (s[j] == '0') {
if (j == n - 1) return true
queue.add(j)
}
}
farthest = maxOf(farthest, end)
}
return false
}
}⭐ 2. Prefix Sum DP — O(n) / O(n)
- Idea:
dp[i]表示位置i是否可達。用前綴和記錄dp中的可達位置數，O(1) 查詢某範圍內是否有可達位置。 - Time:
O(n) - Space:
O(n)
class Solution {
fun canReach(s: String, minJump: Int, maxJump: Int): Boolean {
val n = s.length
if (s[n - 1] == '1') return false
val dp = BooleanArray(n)
dp[0] = true
var reachable = 0 // 滑動視窗內可達位置的數量
for (i in 1 until n) {
if (i >= minJump) reachable += if (dp[i - minJump]) 1 else 0
if (i > maxJump) reachable -= if (dp[i - maxJump - 1]) 1 else 0
dp[i] = s[i] == '0' && reachable > 0
}
return dp[n - 1]
}
}🔑 Takeaways
- Pattern: 滑動視窗 + DP — 用累計計數避免重複掃描跳躍範圍
- Key trick: 前綴和/滑動視窗將「範圍內是否有可達位置」的查詢降到 O(1)