登录/注册
87. 跳跃游戏 VII(中等leetcode1871)
jackdonglk
阅读 48
发表于 08/03 12:04:56

给你一个下标从 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: 我们可以假设f[i]为是否能到达i点,然后求f[s.length-1]。可以从f[0]开始,判断所有能到达的点,记忆下来即可
方法2:假设f[i] 由i点,是否能到达n-1。那么我们从后往前遍历,然后用滑动窗口维护a,b可跳跃位置能到达n-1的数量。那么就可以初始化所有的f值,求f[0]
难点: 记忆化搜索,dp,滑动窗口

0
0
暂无评论 :(