题目1

题意：给一个01串，问是1的连续串长度长还是0的连续串长度长，1返回true，0返回false；

签到题

class Solution {
public:
    bool checkZeroOnes(string s) {
        int n=s.size();
        int a=-1,b=-1,cnt1=0,cnt0=0;
        for(int i=0;i<n;){
        if(s[i]=='1'){
            while(s[i]=='1') cnt1++,i++;
            a=max(a,cnt1);
            cnt1=0;
        }
        if(s[i]=='0'){
            while(s[i]=='0') cnt0++,i++;
            b=max(b,cnt0);
            cnt0=0;
        }
        }
        //cout<<a<<" "<<b;
        if(a>b) return true;
        else return false;
    }
};

题目2

题目描述

思路：
数据范围1e5，n方的时间复杂度肯定不行，只能nlogn或n，就想到二分查找速度，然后check一下；

超时代码，***：

class Solution {
public:
    bool chk(int n,vector<int>& dist,double hour){
        double cnt=0;
        for(int i=0;i<dist.size();i++){
        if(i!=dist.size()-1) cnt+=dist[i]/n+1;
            else cnt+=dist[i]*1.0/n;
        }
        if(hour-cnt>=0) return true;
        else return false;
    }
    int minSpeedOnTime(vector<int>& dist, double hour) {
        int l=0,r=1e9;
        int ans=0;
        while(l<r){
        int mid=(l+r)>>1;
        if(chk(mid,dist,hour)) ans=mid,r=mid;
        else l=mid-1；//这个地方应该是mid+1；所以超时
    }
        if(ans) return ans;
        return -1;
    }
};

正确代码：

class Solution {
public:
    double get(vector<int>& dist, int mid) {
        double res = 0;
        for (auto x: dist)
            res += (x + mid - 1) / mid;//因为浮点数不能取余，这里是浮点数向上取整的一个小技巧，加上一个mid，来自y总
        int x = dist.back();
        res -= (x + mid - 1) / mid;
        res += (double)x / mid;
        return res;
    }

    int minSpeedOnTime(vector<int>& dist, double hour) {
        int l = 1, r = 2e7;
        while (l < r) {
            int mid = l + r >> 1;
            if (get(dist, mid) <= hour) r = mid;
            else l = mid + 1;
        }
        if (r == 2e7) return -1;
        return r;
    }
};

题目3

题目描述：

思路：
理解题意以后就可以很容易想到，如果是i+a~i+b之间所有的s[i]=='0'就可以找到，就是在一段区间加上一个数，马上就想到了前缀和与差分数组。但是当时不知道怎么写。

代码：

class Solution {
    public boolean canReach(String s, int minv, int maxv) {
        int n = s.length();
        if(s.charAt(n-1) != '0') return false;
        int[] d = new int[200010];
        int sum = 0;
        for(int i = 0; i < n; i ++){
            sum += d[i];
            if(i == 0 || sum > 0 && s.charAt(i) == '0'){
                d[i + minv]++;
                d[i + maxv + 1]--;
            }
        }
        return sum > 0;
    }
}

另外一种思路，dp递推,

代码：

class Solution {
public:
    bool canReach(string str, int a, int b) {
        int n = str.size();
        vector<int> f(n + 1), s(n + 1);
        f[1] = 1;//记录是否能够到达
        s[1] = 1;//f的前缀和
        for (int i = 2; i <= n; i ++ ) {
            if (str[i - 1] == '0' && i - a >= 1) {
                int l = max(1, i - b), r = i - a;
                if (s[r] > s[l - 1]) f[i] = 1;//s[r]-s[l-1]求l~r的区间和。
            }
            s[i] = s[i - 1] + f[i];
        }
        return f[n];
    }
};