怕npy的牛牛

思路：以当前端点为右区间向，一个指针指向合法左端点最远的位置，维护最大的区间长度
其实就是一个队列，因为要枚举左端点，所以左端点要入队
同时要保证队列中所有的元素和发，如果同时出现了'n'、'p'、'y'，则不断出队直到区间合法，得到该左端点对应的最大合法区间

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         * 返回符合题意的最长的子串长度
         * @param x string字符串
         * @return int整型
         */
        int Maximumlength(string s) {
            // write code here
            int size=s.size(),mx=0,last=0;
            int cnt1=0,cnt2=0,cnt3=0;
            for(int i=0;i<size;++i) {
                if(s[i]=='n') cnt1+=1;
                else if(s[i]=='p') cnt2+=1;
                else if(s[i]=='y') cnt3+=1;
                while(cnt1&&cnt2&&cnt3) {
                    if(s[last]=='n') cnt1-=1;
                    else if(s[last]=='p') cnt2-=1;
                    else if(s[last]=='y') cnt3-=1;
                    ++last;
                }
                if(i-last+1>mx) mx=i-last+1;
            }
            return mx;
        }
};

牛牛与后缀表达式

思路：
真就后缀表达式，用栈去模拟。
遇到整数就入栈，遇到操作符就弹出两个数进行运算
会错可能就是没有开长整型，或者运算的顺序错了，是先入栈的减去后入栈的数。

Code：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串 
     * @return long长整型
     */
typedef long long ll;
stack<ll>st;
ll solve(string str) {
        // write code here
        int l=0,r=0;
        for(int i=0;i<str.length();i++){
            if(str[i]>='0'&&str[i]<='9') r++;
            else if(str[i]=='#'){
                string s=str.substr(l,r);
                l=i+1;
                r=0;
                ll num=stoi(s);
                st.push(num);
            }
            else if(str[i]=='+'||str[i]=='-'||str[i]=='*'){
                l=i+1;
                ll b=st.top();st.pop();
                ll a=st.top();st.pop();
                if(str[i]=='+'){
                    a+=b;
                    st.push(a);
                }
                else if(str[i]=='*'){
                    a*=b;
                    st.push(a);
                }
                else if(str[i]=='-'){
                    a-=b;
                    st.push(a);
                }
            }
        }
        return st.top();
}
};

Tree III

思路：
从距离根1最远的点出发，得到以为端点的最远距离，这个距离一定是这个有根树的最长距离。
图片说明
如图所示，如果保证2到根1的深度最大，那么以2为端点跑出来的最远距离一定是这个有根树的最长距离。

但是我们要求的这个有根树的第二长距离，以2为端点跑出来的第二长距离一定是这个有根树的第二长距离吗？
如上图所示，以2泡出来的最远距离，第二长距离，但是这个有根树的第二长距离是
不难看出，从距离2最远的点出发，得到以为端点的第二长距离也可能是这个有根树的第二长距离。

如果我们把于所有点到的距离升序排序后取倒数第三个数，那么这个数一定是第二大的数，不取排序后取倒数第二个数是因为倒数第二个数和倒数第一个数都是路径的长度，也就是说这两个数是被重复统计的。
Code：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=2e5+7;
typedef long long ll;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param e int整型vector 长度为n-1的数组，表示结点2到结点n的父结点
     * @return int整型 
     */
    int head[maxn],to[maxm],Next[maxm],m1=0,m2=0,tot=0;
    int ans[maxm],top=0;
    void add(int x,int y) {
        to[++tot]=y;
        Next[tot]=head[x];
        head[x]=tot;
    }
    void dfs(int x,int f,int dep) {
        if(dep>m1) {
            m1=dep;
            m2=x;
        }
        for(int i=head[x],y;i;i=Next[i]) {
            y=to[i];
            if(y==f) continue;
            dfs(y,x,dep+1);
        }
    }
    void dfs2(int x,int f,int dep) {
        ans[++top]=dep;
        for(int i=head[x],y;i;i=Next[i]) {
            y=to[i];
            if(y==f) continue;
            dfs2(y,x,dep+1);
        }
    }
    int tree3(vector<int>& e) {
        int n=e.size(),p1,p2;
        for(int i=0;i<n;++i) {
            add(e[i],i+2);
            add(i+2,e[i]);
        }
        dfs(1,-1,0);
        p1=m2;
        m1=m2=0;
        dfs(p1,-1,0);
        p2=m2;
        dfs2(p1,-1,0);
        dfs2(p2,-1,0);
        sort(ans+1,ans+1+top);
        return ans[top-2];
    }
};