leetcode 1871. 跳跃游戏 VII 中等 给你一个下标从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^5s[i]要么是0要么是1s[0] 01 minJump maxJump s.length分析如果最后一个位置本身是1那么一定无法到达可以直接返回false。先把字符串中所有字符为0的位置存入数组pos中判断可以跳到哪些位置时只需要在这些0位置中寻找不需要反复扫描整个字符串。然后使用队列进行 BFS队列中保存的是当前已经可以到达的位置。初始时下标0一定是起点所以先将0入队。对于队首位置index它下一步可以到达的范围是[index minJump,index maxJump]这个区间内并且落点必须是0。使用变量temp作为指针指向pos数组中当前还没有处理过的位置。又因为pos[0]就是起点0因此 temp 初值为 1。当 BFS 扩展某个位置时就从pos[temp]开始向后扫描。如果pos[temp] left说明这个0位置太靠前当前点跳不到它。由于 BFS 中后续取出的下标只会越来越大之后的left也只会更靠后所以这个位置以后也不可能再被跳到可以直接跳过。如果pos[temp] right说明这个位置已经超过了当前能跳到的范围后面的pos更大也一定超过范围所以停止本轮扫描。如果left pos[temp] right说明这个位置可以从当前下标跳到因此将它加入队列后续继续从这个位置向外扩展。这个temp是整个 BFS 共用的而不是每次从头开始扫描。这样可以保证每个0位置最多只会被扫描一次从而避免超时。最后只需要判断最后一个位置是否被访问过如果flag[len - 1]为真说明最后一个位置可以到达否则说明无法到达。class Solution { public: bool canReach(string s, int minJump, int maxJump) { if(s[s.length()-1]1)return false; vectorintpos; int lens.length(),n,temp1; for(int i0;ilen;i) if(s[i]0)pos.push_back(i); queueintque;que.push(0);npos.size(); mapint,intflag;flag[0]1; while(!que.empty()) { int indexque.front();que.pop();flag[index]1; int leftindexminJump,rightmin(len-1,indexmaxJump); if(leftright)continue; while(tempn) { if(pos[temp]left)temp; else if(pos[temp]right)break; else que.push(pos[temp]),flag[pos[temp]]1,temp; } } if(flag[len-1])return true; return false; } };