烟台牟平住房建设局网站,虹口房产网站建设,宁波专业seo首页优化,深圳小程序公司文章目录1. 题目2. 解题1. 题目
给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。 一开始#xff0c;你在下标 0 处#xff0c;且该位置的值一定为 0 。 当同时满足如下条件时#xff0c;你可以从下标 i 移动到下标 j 处#xff1a;
i minJump …
文章目录1. 题目2. 解题1. 题目
给你一个下标从 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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 55. 跳跃游戏贪心
创建访问标记 vis并且记录最远可达的位置保证每个位置不重复访问O(n)O(n)O(n) 时间复杂度
class Solution {
public:bool canReach(string s, int minJump, int maxJump) {if(s.back() 1)return false;int n s.size(), end 0;//最远可到达的位置 endvectorbool vis(n, false);vis[0] true;for(int i 0; i n i end; i){if(!vis[i]) continue;int p1 iminJump;int p2 min(n-1, imaxJump);for(int j max(p1, end1); 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阿明一起加油、一起学习进步
