比赛: https://ac.nowcoder.com/acm/contest/9557
A
用一个双指针扫描一遍,答案就是扫描时双指针的最大距离
a,b,c分别表示'n','p','y'的个数
当a,b,c都大于0时,左指针右移,直到不满足条件
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 返回符合题意的最长的子串长度 * @param x string字符串 * @return int整型 */ int a=0,b=0,c=0,k=0,ans=0; string p; void work() { if(p[k]=='n') a--; if(p[k]=='p') b--; if(p[k]=='y') c--; k++; return; } int Maximumlength(string x) { // write code here p=x; for(int i=0;i<x.length();i++) { if(x[i]=='n') a++; if(x[i]=='p') b++; if(x[i]=='y') c++; while(a&&b&&c) work(); ans=max(ans,i-k+1); } return ans; } };
b
考虑枚举每个字符
若为符号,取出栈顶的2个数,进行运算后的结果加入栈中
若为数字,统计到a里面
若为'#',把a添加到栈中
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 给定一个后缀表达式,返回它的结果 * @param str string字符串 * @return long长整型 */ stack<long long>q; string c; long long solve(string str) { c=str; long long a=0; long long i,j; for(long long k=0;k<c.length();k++) { if(c[k]=='#'){ q.push(a); a=0; } else if(c[k]<='9'&&c[k]>='0'){ a=a*10+c[k]-'0'; } else{ if(c[k]=='-') i=q.top(),q.pop(),j=q.top(),q.pop(), q.push(j-i); if(c[k]=='+') i=q.top(),q.pop(),j=q.top(),q.pop(), q.push(j+i); if(c[k]=='*') i=q.top(),q.pop(),j=q.top(),q.pop(), q.push(j*i); if(c[k]=='/') i=q.top(),q.pop(),j=q.top(),q.pop(), q.push(j/i); } } return q.top(); } };
C
先在原图中找到一条直径
任意删掉此直径的一个端点
再次在图中求一遍直径即为答案
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param e int整型vector 长度为n-1的数组,表示结点2到结点n的父结点 * @return int整型 */ int n,tot,rt,ans,to; int h[100006],nex[200006],ver[200006],dis[200006]; inline void add(int x,int y) { nex[tot]=h[x]; ver[tot]=y; h[x]=tot++; } inline void dfs(int u,int v) { for (int i=h[u];~i;i=nex[i]) { int j=ver[i]; if(j==v) continue; dis[j]=dis[u]+1; if(dis[rt]<dis[j]) rt=j; dfs(j,u); } } inline void find(int u,int v) { for (int i=h[u];~i;i=nex[i]) { int j=ver[i]; if(j==v||j==to) continue; dis[j]=dis[u]+1; ans=max(ans,dis[j]); find(j,u); } } int tree3(vector<int>& e) { memset(h,-1,sizeof(h)); n=e.size()+1; for (int i=0;i<n;i++) add(e[i],i+2),add(i+2,e[i]); dfs(1,0); int u=rt; memset(dis,0,sizeof(dis)); dfs(rt,0); memset(dis,0,sizeof(dis)); to=rt;find(u,0); memset(dis,0,sizeof(dis)); to=u;find(rt,0); return ans; } };