黄钻9
A
题意：
牛牛从牛毕那里拿了一根长度为n的白木板，木板被等分成了n段（没有被切割，只是虚拟划分成了n段），其中有些段被牛毕用颜料染成了黑色。
牛牛非常不喜欢黑色，它找来了一桶清洗剂决定对木板进行清洗，但是牛牛发现自己的清洗剂最多只能清洗m段。
清洗完后，牛牛会把木板锯成纯色的几段。例如假设木板是 （黑黑黑白白白白黑黑黑 ），就会被锯成（黑黑黑）（白白白白）（黑黑黑）三段。
牛牛想知道，它足够聪明地清洗木板，能获得的纯白色木板的最大长度是多少。

输入：
给定n,m两个整数
和一个长度为n的数组a，为1表示白色，为0表示黑色

输出：
一行一个数字表示能获得的纯白色木板的最大长度是多少
思路：数组sum求前i段中黑色的段数，然后遍历一遍sum，找到黑色段数小于m且区间长度最大的区间。
代码：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int sum[1000005];//如上所述
    int solve(int n, int m, vector<int>& a) {
        // write code here
        for(int i=0;i<a.size();i++){
            sum[i+1]=sum[i];
            if(a[i]==0)sum[i+1]++;
        }
        int ans=0,l=0,r=1;
        for(int i=1;i<=n;i++){
            while(l<=n&&sum[r]-sum[l]>m)l++;
            while(r<=n&&sum[r]-sum[l]<=m)r++;
            ans=max(ans,r-1-l);
        }
        return ans;
    }
};

B
题目
给定一棵有n个结点的二叉树的先序遍历与后序遍历序列，求其中序遍历序列。
若某节点只有一个子结点，则此处将其看作左儿子结点.
思路：看到题目就想直接将这棵二叉树构造出来，然后想半天没想起数据结构课咋讲的。不太明白的话还是直接复习数据结构吧。
代码：

class Solution {
public:
    /**
     * 返回所求中序序列
     * @param n int整型 二叉树节点数量
     * @param pre int整型vector 前序序列
     * @param suf int整型vector 后序序列
     * @return int整型vector
     */
    vector<int>v;
    int l[100005],r[100005],fa[100005];
    map<int,int>mp;
    void dfs(int u)
    {
        if(u==0)return;
        dfs(l[u]);
        v.push_back(u);
        dfs(r[u]);
    }
    vector<int> solve(int n, vector<int>& pre, vector<int>& suf) {
        // write code here
        for(int i=0;i<suf.size();i++)mp[suf[i]]=i;
        fa[0]=0;
        //根据序列构造树
        for(int i=0;i<pre.size()-1;i++){
            int u=pre[i],v=pre[i+1];
            if(mp[v]<mp[u]){
                l[u]=v;
                fa[v]=u;
            }else{
                while(mp[v]>mp[u])u=fa[u];
                r[u]=v;
                fa[v]=u;
            }
        }
        //再跑一遍树，确定中序序列
        dfs(pre[0]);
        return v;
    }
};

C
题意：

游戏是在一个N*N的网格图中进行的，图中的网格分为四种类型，0表示空地可以通过，1表示墙壁无法通过，2表示不仅可以通过，还可以在该格放置一个传送门，3表示有且仅有的唯一的固定传送门。
思路：看起来就是个模拟，实际上还是个模拟。直接暴力搜到达该点的最小步数，然后同时找到最近的2放置传送门用来更新最远的3（直接一步传送）。需要注意的是要从（0，0）出发搜一遍，然后从（N-1，N-1）出发搜一遍，看样例就知道两个起始点算出来的答案不一样，取决于2和3怎么放。
代码：

class Solution {
public:
    /**
     * 返回最终要输出的答案
     * @param N int整型 表示地图的大小
     * @param a int整型二维数组 地图的描述
     * @param aRowLen int a数组行数
     * @param aColLen int* a数组列数
     * @return int整型
     */
    int vis[550][550],x=0,y=0,temp,temp1,ans;
    void dis(int N,int** a,int sx,int sy)//从(sx,sy)出发
    {
        queue<pair<int,int>>q;
        q.push(make_pair(sx,sy));
        memset(vis,0x3f3f3f3f,sizeof(vis));
        temp=0x3f3f3f3,temp1=0x3f3f3f3f;
        vis[sx][sy]=0;
        while(!q.empty()){
            x=q.front().first,y=q.front().second;
            q.pop();
            if(a[x][y]==3&&temp+1<vis[x][y])vis[x][y]=temp+1;
            else if(a[x][y]==2&&vis[x][y]<temp)temp=vis[x][y];//因为最近的2一般出现在最远的3前面，如果不在，那也不用更新了
            //上下左右
            if(x-1>=0&&a[x-1][y]!=1&&vis[x][y]+1<vis[x-1][y]){
                q.push(make_pair(x-1,y));
                vis[x-1][y]=vis[x][y]+1;
            }
            if(y-1>=0&&a[x][y-1]!=1&&vis[x][y]+1<vis[x][y-1]){
                q.push(make_pair(x,y-1));
                vis[x][y-1]=vis[x][y]+1;
            }
            if(x+1<N&&a[x+1][y]!=1&&vis[x][y]+1<vis[x+1][y]){
                q.push(make_pair(x+1,y));
                vis[x+1][y]=vis[x][y]+1;
            }
            if(y+1<N&&a[x][y+1]!=1&&vis[x][y]+1<vis[x][y+1]){
                q.push(make_pair(x,y+1));
                vis[x][y+1]=vis[x][y]+1;
            }
        }
    }
    int solve(int N, int** a, int aRowLen, int* aColLen) {
        // write code here
        dis(N,a,0,0);
        ans=vis[N-1][N-1];
        dis(N,a,N-1,N-1);
        ans=min(ans,vis[0][0]);
        return ans;
    }
};