首页 > 美团3.13笔试题
头像
精神病科黄主任
编辑于 2021-03-14 10:42
+ 关注

美团3.13笔试题

感觉题目比较简单

第一题:就是一个n行m列矩阵,让你输出行列翻转。
输入:
3 3
1 2 3
4 5 6
7 8 9

输出:
1 4 7
2 5 8
3 6 9

c语言语法题
/*
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-13 16:01:11
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e2+50;
int a[N][N];
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

第二题:给你一个字符串,你提取数字后,对数字进行从小到大输出,数字要去除前导0

简单模拟题
/*
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-13 16:10:08
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e2+50;
int main(){
    string s;cin>>s;
    vector<string > ans;
    for(int i=0;i<s.size();i++){
        if(s[i]>='0' && s[i]<='9'){
            string q="";
            while(i<s.size() && s[i]>='0' && s[i]<='9'){
                q+=s[i];
                ++i;
            }
            --i;
            string a="";
            int flag=0;
            for(int j=0;j<q.size();j++){
                if(q[j]=='0' && !flag) continue;
                flag=1;
                a+=q[j];
            }
            if(a.size()==0) a="0";
            ans.push_back(a);
        }
    }
    sort(ans.begin(),ans.end(),[](string a,string b){
        if(a.size()!=b.size()) return a.size()<b.size();
        return a<b;
    });
    for(auto &x:ans) cout<<x<<endl;
    return 0;
}
第三题:给n个数,求每个窗口大小为m的众数是多少
输出n-m+1行

我的做法是考虑维护一个版本号机制,就是延迟删除即可,优先队列维护一个当前的值和当时的版本号,这里的版本号指当时这个数字出现的次数。
/*
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-13 16:12:48
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
int a[N];
struct node{
    int val,cnt;
    friend bool operator<(node a,node b){
        if(a.cnt!=b.cnt) return a.cnt<b.cnt;
        return a.val>b.val;
    }
};
map<int,int>mp;
int main(){
    int n,m;cin>>n>>m;
    priority_queue<node> que;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i<=m){
            que.push({a[i],++mp[a[i]]});
        }
    }
    cout<<que.top().val<<endl;
    for(int i=m+1;i<=n;i++){
        mp[a[i-m]]--;
        que.push({a[i],++mp[a[i]]});
        while(!que.empty()){
            node now=que.top();
            if(now.cnt!=mp[now.val]){
                que.pop();
                continue;
            }
            break;
        }
        cout<<que.top().val<<endl;

    }

    return 0;
}

第四题:给一棵树,每个点有权值,让选择点,要求选择不相邻的点,求使得权值最大,在使得权值最大的情况下,求选择的点中最小的权值最大是多少

树型dp
其实就是树型dp入门题,那个没有上司的舞会。
只不过他多要求输出最小点权的最大值
那么只需要在dp转移的时候维护一个mi数组一起转移就可以啦
/*
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-13 16:23:05
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
ll val[N];
vector<int> e[N];
ll dp[N][2];//表示以i为根的子树选了  1/0  当前根/不选根 的最大值
ll mi[N][2];
void dfs(int x,int fa){
    dp[x][1]=val[x];
    mi[x][1]=val[x];
    dp[x][0]=0;
    for(auto &son:e[x]){
        if(son==fa) continue;
        dfs(son,x);
        dp[x][1]+=dp[son][0];
        mi[x][1]=min(mi[x][1],mi[son][0]);

        dp[x][0]+=max(dp[son][1],dp[son][0]);
        if(dp[son][1]>dp[son][0]) mi[x][0]=min(mi[x][0],mi[son][1]);
        else if(dp[son][1]<dp[son][0]) mi[x][0]=min(mi[x][0],mi[son][0]);
        else mi[x][0]=min(mi[x][0],max(mi[son][0],mi[son][1]));

    }
}
int main(){
    memset(mi,63,sizeof mi);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>val[i];
    }
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }   
    dfs(1,0);
    ll S1=0,S2=0;
    for(int i=1;i<=n;i++){
        S1=max(S1,max(dp[i][0],dp[i][1]));
    }
    cout<<S1<<" ";
    for(int i=1;i<=n;i++){
        if(S1==dp[i][0]) S2=max(S2,mi[i][0]);
        if(S1==dp[i][1]) S2=max(S2,mi[i][1]);
    }
    cout<<S2;

    return 0;
}

第五题:给你一个图,每个点有自己的权值,现在就是说你可以选择任意一个点开始,然后你走的话,只能走到点权比当前小的点。
问最多能走多少个点。

也很简单,就是对于有边的点,我们比较一下点权大小,然后去建单向边,
然后对每个点去dfs即可,因为要去我下一个点的点权比当前小,所以构造出来的图是一片森林,因为原图可能不连通,可能是多棵树。
dfs即可。
如果我之前算过从1出发,最多能走5个点,那么我下次走到1,就无须继续走了,直接加上从1能走的最远的路即可。

/*
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-13 17:06:42
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
vector<int> e[N];
ll val[N];
ll dis[N],vis[N];
void dfs(int x,int f){
    vis[x]=1;
    ll nxt=0;
    for(auto &y:e[x]){
        if(y==f) continue;
        if(!vis[y]) dfs(y,x);
        nxt=max(nxt,dis[y]);
    }
    dis[x]+=nxt;
}
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>val[i];
        dis[i]=1;
    }
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        if(val[x]>val[y]) e[x].push_back(y);
        if(val[x]<val[y]) e[y].push_back(x);
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]) dfs(i,0);
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,dis[i]);
    }
    cout<<ans;
    return 0;
}





全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐