给你一个下标从 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 <= 105
s[i] 要么是 '0' ，要么是 '1'
s[0] == '0'
1 <= minJump <= maxJump < s.length
解题思路分析1、遍历；时间复杂度O(n)，空间复杂度O(1)
func canReach(s string, minJump int, maxJump int) bool {
n := len(s)
if s[n-1] == '1' {
return false
}
minDis, maxDis := 0, 0 // 更新最后可达到的最小 最大坐标的范围
for i := 0; i < n-1; i {
if s[i] == '0' && minDis <= i && i <= maxDis {
minDis = i minJump
maxDis = i maxJump
}
if minDis <= n-1 && n-1 <= maxDis {
return true
}
}
return false
}
2、动态规划 滑动窗口；时间复杂度O(n)，空间复杂度O(n)
func canReach(s string, minJump int, maxJump int) bool {
n := len(s)
if s[n-1] == '1' {
return false
}
dp := make([]bool, n) // dp[i] => 下标i是否可达
dp[0] = true
count := 1 // 滑动窗口里面可达数量
for i := minJump; i < n; i {
if s[i] == '0' && count > 0 { // 当前可达
dp[i] = true
}
if maxJump <= i && dp[i-maxJump] == true { // 滑动窗口左端点:-1
count--
}
if dp[i-minJump 1] == true { // 滑动窗口右端点： 1
count
}
}
return dp[n-1]
}
3、动态规划 前缀和；时间复杂度O(n)，空间复杂度O(n)
func canReach(s string, minJump int, maxJump int) bool {
n := len(s)
if s[n-1] == '1' {
return false
}
dp := make([]int, n) // dp[i] => 下标i是否可达
dp[0] = 1
arr := make([]int, n)
for i := 0; i < minJump; i { // 前缀和从minJump开始
arr[i] = 1
}
for i := minJump; i < n; i {
left := i - maxJump
right := i - minJump
if s[i] == '0' {
var total int
if left <= 0 {
total = arr[right]
} else {
total = arr[right] - arr[left-1]
}
if total > 0 { // 通过前缀和计算，范围内存在多少满足条件的坐标
dp[i] = 1
}
}
arr[i] = arr[i-1] dp[i]
}
return dp[n-1] > 0
}
4、差分数组；时间复杂度O(n)，空间复杂度O(n)
func canReach(s string, minJump int, maxJump int) bool {
n := len(s)
if s[n-1] == '1' {
return false
}
arr := make([]int, n 1)
arr[0] = 1
arr[1] = -1
sum := 0
for i := 0; i < n; i {
sum = sum arr[i]
if s[i] == '0' && sum > 0 {
arr[min(i minJump, n)]
arr[min(i maxJump 1, n)]--
}
}
return sum > 0 // 计算范围内可达到最后有几个坐标满足条件
}
func min(a, b int) int {
if a > b {
return b
}
return a
}总结
Medium题目，跳跃游戏系列题目，多种解决方法
