首页 > 8.8 美团笔试
头像
牛客607108722号
发布于 2021-08-08 12:05
+ 关注

8.8 美团笔试

总共五道题,4+1的形式。

第一题,要特判等于0的情况,否则是91%

第二题,忘掉了。

第三题,对于a[i],找到之前小于它的最大的数,可以维护一个set,每次处理完当前a[i],就插入到set中。对于处理,可以直接利用set的lower_bound(val),然后根据迭代器减1判断情况。

第四题,任选x修改为y,使得序列前一半与后一半相同,可以处理出不同的 pair{ a[i] , a[i+n/2] },然后默认first为较小值,去一下重 ( 相同的对计算一次贡献 ),然后建立无向图。优先从入度小的点出发DFS,每走一步就是一个花费,图遍历完就得答案。

第五题,对换左右子树,这个可以直接用数组表示存二叉树,点值对应题目要求的点序号,下标0开始,初始时左右儿子分别为2*x+1,2*x+2,然后根据修改,分别修改Lchild和Rchild的指向。第五题代码还没删掉,如下。

#include<bits/stdc++.h>
using namespace std;
int a[100020];
typedef pair<int,int> pii;
int n,m,k;
int loc[100020];
struct node{
    int val;
    int L,R;
}p[10000];
struct pre{
    int L,R;
}has[10000];
void solve(int x) {
    if(x>=n) return;
    loc[p[x].val]=x;
    p[x].L=p[x].R=0;
    int cur=p[x].val;
    int Lval=has[cur].L;
    int Rval=has[cur].R;
    if(Lval) {
        p[x].L=2*x+1;
        p[2*x+1].val=Lval;
        solve(2*x+1);
    }
    if(Rval) {
        p[x].R=2*x+2;
        p[2*x+2].val=Rval;
        solve(2*x+2);
    }
}
void print(int x) {
    if(p[x].L) print(p[x].L);
    cout<<p[x].val<<" ";
    if(p[x].R) print(p[x].R);
}
int main()
{
    cin>>n>>m>>k;
    p[0].val=k;
    for(int i=1;i<=n;i++) {
        cin>>has[i].L>>has[i].R;
    }
    solve(0);
    for(int i=1;i<=m;i++) {
        int x;
        cin>>x;
        int id=loc[x];
        swap(p[id].L,p[id].R);
    }
    print(0);
}


全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐