08-29 18:29 已编辑牛客运营

发布于广东

关注

美团历年秋招笔试真题

如需获取完整资料，请点击下方链接领取《2024校招笔试真题秘籍》（实时更新中）

不收费，3人组团即可一块免费领取！限量免费10000个名额

手机端点击免费领取：https://www.nowcoder.com/link/campus_xzbs2

电脑端请扫码领取：

1、图的遍历

【题目描述】给定一张包含N个点、N-1条边的无向连通图，节点从1到N编号，每条边的长度均为1。假设你从1号节点出发并打算遍历所有节点，那么总路程至少是多少？

输入描述:

第一行包含一个整数N，1≤N≤10^5。

接下来N-1行，每行包含两个整数X和Y，表示X号节点和Y号节点之间有一条边，1≤X，Y≤N。

输出描述:

输出总路程的最小值。

输入样例:

1 2

1 3

3 4

输出样例：

【解题思路】

这其实是一棵以1为根的树。

如果要回到起点，则每条边走了恰好2次。

不回到起点，则可以选择一条停在最深的叶子节点处。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n;
vector<int> G[N];
int dep[N];

void dfs(int u, int pre) {
    for(int v : G[u]) {
        if(v != pre) {
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dep[1] = 0;
    dfs(1, 0);
    int ans = (n - 1)*2 - *max_element(dep+1, dep+n+1);
    printf("%d\n", ans);
    return 0;
}

2、最长全1串

【题目描述】给你一个01字符串，定义答案=该串中最长的连续1的长度，现在你有至多K次机会，每次机会可以将串中的某个0改成1，现在问最大的可能答案

输入描述:

输入第一行两个整数N,K，表示字符串长度和机会次数

第二行输入N个整数，表示该字符串的元素

( 1 <= N <= 300000 , 0 <= K <= N )

输出描述:

输出一行表示答案

输入样例:

10 2

1 0 0 1 0 1 0 1 0 1

输出样例：

【解题思路】

two pointers

维护0的个数不超过K个的区间。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
const int N = 300000 + 5;
int n, k;
int a[N];

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    int r = 0, cnt = 0;
    int ans = 0;
    for(int l = 1; l <= n; ++l) {
        while(r + 1 <= n && cnt + (a[r+1] == 0) <= k) {
            ++r;
            cnt += (a[r] == 0);
        }
        ans = max(ans, r-l+1);
        cnt -= (a[l] == 0);
    }
    printf("%d\n", ans);
    return 0;
}

3、外卖满减

【题目描述】你打开了美了么外卖，选择了一家店，你手里有一张满X元减10元的券，店里总共有n种菜，第i种菜一份需要A_i元，因为你不想吃太多份同一种菜，所以每种菜你最多只能点一份，现在问你最少需要选择多少元的商品才能使用这张券。

输入描述:

第一行两个正整数n和X，分别表示菜品数量和券的最低使用价格。（1≤n≤100, 1≤X≤10000）接下来一行n个整数，第i个整数表示第i种菜品的价格。（1≤A_i≤100）

输出描述:

一个数，表示最少需要选择多少元的菜才能使用这张满X元减10元的券，保证有解。

输入样例:

5 20

18 19 17 6 7

输出样例:

【解题思路】

01背包

找大于等于X的最小可达状态。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
const int N = 10100 + 5;
int n, X, C;
int dp[N];

int main() {
    scanf("%d%d", &n, &X);
    C = X + 100;
    dp[0] = 1;
    for(int i = 0; i < n; ++i) {
        int a;
        scanf("%d", &a);
        for(int j = C; j >= a; --j) {
            dp[j] |= dp[j-a];
        }
    }
    for(int i = X; i <= C; ++i) {
        if(dp[i] == 1) {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}

4、小美的送花线路

【题目描述】

小美是美团的一名鲜花快递员，鲜花是一种保质期非常短的商品，所以需要尽快送到客户手中，公司对于骑手的一个要求就是要规划送花的线路，使得骑手送完所有订单走的路程尽可能少。(骑手开始派送时带走了所有需要派送的花，不必每单后返回花店，路程结算是从花店出发，到送完最后一名客户为止，不计算从最后一名客户家回到花店的时间)

公司对于骑手的绩效评价是取决于两个指标，一是从花店到所有客户地址的距离之和，另一个是骑手实际走的路程。

设花店始终位于1号位置，客户共有n-1个，其编号为2~n。令dis(i,j)表示i号位置到j号位置的距离，即分别计算,和骑手实际所走的最短路程。

为了简化问题，我们约束这n个位置构成的是一棵树，即只有n-1条边在其中互相连接，且保证n个点彼此连通。

输入描述：

输出第一行包含一个正整数n，即花店和客户的总数。(1≤n≤30000)

接下来有n-1行，每行有三个整数u,v,w，表示在u和v之间存在一条距离为w的道路。(1≤w≤1000)

输出描述：

输出包含两个整数，中间用空格隔开，分别表示花店到所有客户地址的距离之和和骑手实际走的路程。

输入样例：

1 2 3

1 3 1

1 4 2