题目描述

算法一仅限ac当前leetcode数据，个人复盘后感觉还是存在问题，但是未构造出能让此代码错误的数据。

仅提供解题思路，请大家批判性观看，或者提供数据，谢谢！

之后Leetcode更新数据后 应该无法AC。

20210524 更新题解2

给你一个下标从 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

感觉是某个动态规划魔改的题目
比赛时，使用BFS加上剪枝就ac了

C++ 代码

class Solution {
public:
    int dp[100010]={0};
    bool canReach(string s, int minJump, int maxJump) {
        dp[0]= 1;
        queue<int> q;
        q.push(0);
        while(!q.empty()){
            int idx = q.front(); q.pop();
            if(idx >=s.size()-1) return true;
            for(int i = idx+minJump;i<= idx+maxJump;i++){
                if(i >= s.size()) break;
                if(s[i]=='0' && dp[i]==0){
                    q.push(i); dp[i] =1;
                }else if(s[i]=='0' && dp[i] ==1){
                    break;
                }
            }
        }

        return false;
    }
};

算法2

使用dp数组就是为了避免在BFS过程中重复计算索引位置
而且算法1的使用dp数组还存在一些错误(虽然能AC)
那么我们使用一个last记录上次每次遍历检测是否能跳跃的点的位置
下次至少从该点开始遍历检测，由于BFS采取的是一次检测，所以不存在漏检，
而至少从last开始进行检测 保证避免了点的重复检测

class Solution {
public:
    int dp[100010] = { 0 };
    bool canReach(string s, int minJump, int maxJump) {
        dp[0] = 1;
        queue<int> q;
        q.push(0);
        int last = 0;
        while (!q.empty()) {
            int idx = q.front(); q.pop();
            if (idx >= s.size() - 1) {return true;}
            //每次至少从last点之后开始检测 避免重复
            for (int i =  max(last + 1, idx + minJump); i <= idx + maxJump; i++) {
                if (i >= s.size()) break;
                //更新last点
                //由于我们是遍历检测 所以保证last点之前的检测不会漏点。。 漏掉任何点. hh
                last = i;
                if (s[i] == '0' && dp[i] == 0) {
                    q.push(i); dp[i] = 1;

                }
                /*
                else if (s[i] == '0' && dp[i] == 1) {
                    //last = i;
                    break;
                }
                */
            }
        }

        return false;
    }
};

我的视频题解空间