怕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;
}
};
查看17道真题和解析
顺丰集团工作强度 381人发布