给你一个下标从 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 <= 10^5
s[i] 要么是 '0' ,要么是 '1'
s[0] == '0'
1 <= minJump <= maxJump < s.length
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jump-game-vii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
类似题目:
class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
if(s.back() == '1')
return false;
int n = s.size(), end = 0;//最远可到达的位置 end
vector<bool> vis(n, false);
vis[0] = true;
for(int i = 0; i < n && i <= end; i++)
{
if(!vis[i]) continue;
int p1 = i+minJump;
int p2 = min(n-1, i+maxJump);
for(int j = max(p1, end+1); j <= p2; ++j)//max保证每个位置只检查1次
{
if(s[j] == '0')
{
vis[j] = true;
if(j == n-1)//走到最后了
return true;
}
}
end = p2;//更新end位置
}
return false;
}
};
44 ms 15.7 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!