怕npy的牛牛题解

30分解法:

可以枚举所有子串,子串一共有n^2个,然后再对每个子串o(n)判断是否同时含有n,p,y即可,时间复杂度o(n^3),空间复杂度o(n)。

100分解法:

n范围1e7,对于1s的时间o(nlogn)的算法都很难通过,考虑时间复杂度o(n)的算法,很容易想到尺取法(也就是two-points)。首先移动右端点找到第一个含有npy的区间,因为这一时刻子串刚含有npy,所以此时右端点向左移动一个单位就不同时含有npy了,所以用图片说明 更新最大长度。然后每次更新后移动左指针至不包含npy,再移动右指针至第一次包含npy即可,重复此次操作直至右端点越界即可。时间复杂度o(n),空间复杂度o(1),代码如下:

class Solution {
public:
    /**
     * 返回符合题意的最长的子串长度
     * @param x string字符串 
     * @return int整型
     */
    int Maximumlength(string x) {
        // write code here
        int l=-1,r=-1;
        int maxn=0,flag1=0,flag2=0,flag3=0;
        int n=x.size();
        while(1)
        {
            while(r<n)
            {
                r++;
                if(x[r]=='n')flag1++;
                if(x[r]=='p')flag2++;
                if(x[r]=='y')flag3++;
                if(flag1&&flag2&&flag3)break;
            }
            maxn=max(maxn,r-l-1);
            if(r==n)break;
            while(l<n)
            {
                l++;
                if(x[l]=='n')flag1--;
                if(x[l]=='p')flag2--;
                if(x[l]=='y')flag3--;
                if(flag1==0||flag2==0||flag3==0)break;
            }
        }
        return maxn;
    }
};
全部评论

相关推荐

做黑夜里的那道光:两年电赛完赛没必要写,纯扣分
双非本科求职如何逆袭
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务