美团0812秋招笔试真题解析
- 2026-10-30 19:42:47
关注我们，每周更新两到三次大厂最新笔试题解析
前言
题目比较简单，大部分同学都可以AK的。但是有不少同学模拟题细节出错，一定要仔细仔细啊！！！美团换平台后难度有点下降呀，这次不多a两道按美团的习惯可能没面试。
小美的排列询问
小美拿到了一个排列。她想知道在这个排列中，x和y是否是相邻的。你能帮帮她吗？
排列是指一个长度为n的数组，其中 1 到n 每个元素恰好出现一次。
输入描述
第一行输入一个正整数n，代表排列的长度。
第二行输入n个正整数ai，代表排列的元素。
第三行输入两个正整数x和y，用空格隔开。
保证x≠y
输出描述
如果x和y在排列中相邻，则输出"Yes"。否则输出"No"。
示例1
输入
4
1 4 2 3
2 4
输出
Yes
示例2
输入
5
3 4 5 1 2
3 2
输出
No
思路与代码
打卡题。
直接判断即可。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
int x = sc.nextInt();
int y = sc.nextInt();
boolean flag = false;
for (int i = 0 ; i < n - 1 ; i++) {
if (nums[i] == x && nums[i+1] == y) flag = true;
if (nums[i] == y && nums[i+1] == x) flag = true;
}
if (flag) System.out.println("Yes");
else System.out.println("No");
}
}
小美走公路
有一个环形的公路，上面共有n站，现在给定了顺时针第i站到第i+1站之间的距离（特殊的，也给出了第n站到第1站的距离）。小美想沿着公路第x站走到第y站，她想知道最短的距离是多少？
输入描述
第一行输入一个正整数n，代表站的数量。第二行输入n个正整数ai，前n-1个数代表顺时针沿着公路走，i站到第i+1站之间的距离；最后一个正整数代表顺时针沿着公路走，第n站到第1站的距离。· 第三行输入两个正整数x和y，代表小美的出发地和目的地。
输出描述
一个正整数，代表小美走的最短距离。
示例1
输入
3
1 2 2
2 3
输出
2
示例2
输入
3
1 2 2
1 3
输出
2
思路与代码
打卡题。
模拟即可。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n+1];
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt(); //
}
int x = sc.nextInt();
int y = sc.nextInt();
long tmp2 = 0;
int f = x;
while (f != y) {
tmp2 += a[f];
f = (f+1)%(n+1);
if (f == 0) f = 1;
}
long tmp1 = 0;
f = x;
while (f != y) {
if (f > 1)tmp1 += a[f-1];
else tmp1 += a[n];
f = (f-1);
if (f == 0) f = n;
}
System.out.println(Math.min(tmp1,tmp2));
}
}
小美的蛋糕切割
小美有一个矩形的蛋糕，共分成了n行m 列，共n*m个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。她想切一刀把蛋糕切成两部分，自己吃一部分，小团吃另一部分。
小美希望两个人吃的部分的美味度之和尽可能接近，请你输出|s1-s2|的最小值。（其中s1代表小美吃的美味度，s2代表小团吃的美味度）。
请务必保证，切下来的区域都是完整的，即不能把某个小正方形切成两个小区域。
输入描述
第一行输出两个正整数n和m，代表蛋糕区域的行数和列数。接下来的n行，每行输入m个正整数aij，用来表示每个区域的美味度。
输出描述
一个整数，代表|s1-s2|的最小值。
示例1
输入
2 3
1 1 4
5 1 4
输出
0
说明
把蛋糕像这样切开：
1 1 | 4
5 1 | 4
左边蛋糕美味度之和是8
右边蛋糕美味度之和是8
所以答案是0。
思路与代码
二维前缀和模拟即可。
import java.util.Scanner;
public class Main {
static int[][] matrix;
static int[][] pre;
static int get(int x1,int y1, int x2, int y2) {
return pre[x2 + 1][y2 + 1] - pre[x1][y2 + 1] - pre[x2 + 1][y1] + pre[x1][y1];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
matrix = new int[n][m];
pre = new int[ n + 1][m + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = sc.nextInt();
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
int res = Integer.MAX_VALUE;
for (int j = 0 ; j < m; j++) {
// 0,0 n-1,j 0,j n-1,m-1
res = Math.min(res, Math.abs(get(0,0,n-1,j) - get(0,j,n-1,m-1)));
}
System.out.println(res);
}
}
小美的字符串变换
小美拿到了一个长度为n的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有x行y列，必须保证x*y=n，即每y个字符换行，共x行）。
该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？
注：我们定义，上下左右四个方向相邻的相同字符是连通的。
输入描述
第一行输入一个正整数n，代表字符串的长度。
第二行输入一个长度为n的、仅由小写字母组成的字符串。
1<=n<=10^4
输出描述
输出一个整数表示最小权值。
示例1
输入
9
aababbabb
输出
2
说明
平铺为3*3的矩阵：
aab
abb
abb
共有2个连通块，4个a和5个b。
思路与代码
枚举可能分割的行列，并查集检查连通性。
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
static List<Integer> get_divisors(int n) {
List<Integer> res = new LinkedList();
for (int i = 1 ; i <= n /i ; i++) {
if (n%i == 0) {
res.add(i);
if (i!=n/i) res.add(n/i);
}
}
Collections.sort(res);
return res;
}
static int[] fa;
static void init(int n) {
fa = new int[n];
for (int i = 0; i < n; i++) fa[i] = i;
}
//找到x的根节点
static int find(int x) {
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
//合并两个节点
static void union(int x, int y) {
fa[find(x)] = find(y);
}
static int getConn(int x, int y, char[] cs) {
init(x*y+1);
int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
for (int[] dir : dirs) {
int ni = i + dir[0], nj = j + dir[1];
if (ni < 0 || nj < 0 || ni >= x || nj >= y || cs[i*y+j] != cs[ni*y + nj])continue;
union(i*y+j, ni*y+nj);
}
}
}
int res = 0;
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
if (find(i*y+j) == i*y+j)res++;
}
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
String s = sc.nextLine();
List<Integer> divs = get_divisors(n);
int res = Integer.MAX_VALUE;
for (int div : divs) {
if (div != n)res = Math.min(res, getConn(div, n/div,s.toCharArray()));
}
System.out.println(res);
}
}
小美的树上染色
小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。
小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。
小美想知道，自己最多可以染红多少个节点？
输入描述
第一行输入一个正整数n，代表节点的数量。第二行输入n个正整数ai，代表每个节点的权值。接下来的n-1行，每行输入两个正整数u，v，代表节点u和节点v有一条边连接。
输出描述
输出一个整数，表示最多可以染红的节点数量。
示例1
输入
3
3 3 12
1 2
2 3
输出
2
说明
可以染红第二个和第三个节点。
请注意，此时不能再染红第一个和第二个节点，因为第二个节点已经被染红。
因此，最多染红 2 个节点。
思路与代码
树形dp。
每个节点可以染色或者不染色。
染色的话，则必须找到一个可以染色的孩子，其他节点不可以染色。
不染色的话，则孩子染色和不染色都可以，取最大值即可。
import java.util.*;
public class _5 {
public static void main(String[] args) {
new _5().solve();
}
int n;
int[] v;
List<List<Integer>> graph = new ArrayList<>();
void solve() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
v = new int[n+1];
for (int i = 1; i <= n; i++) {
v[i] = sc.nextInt();
}
for (int i = 0; i <= n; i++) graph.add(new LinkedList<>());
int res = 0;
for (int i = 0 ; i < n - 1; i ++) {
int a = sc.nextInt();
int b = sc.nextInt();
graph.get(a).add(b);
graph.get(b).add(a);
}
dp = new int[n+1][2];
dfs(1,-1);
System.out.println(Math.max(dp[1][0], dp[1][1]));
}
int[][] dp; //node 0不染色 1染色
void dfs(int node, int pre) {
for (int next : graph.get(node)) {
if (next != pre) {
dfs(next,node);
}
}
if (graph.get(node).size() == 0 && graph.get(node).get(0) == pre) {
dp[node][1] = 1;
}
//不染色
int tmp = 0;
for (int next : graph.get(node)) {
if (next != pre) {
dp[node][0] += Math.max(dp[next][0], dp[next][1]) ;
tmp += dp[next][0];
}
}
for (int next : graph.get(node)) {
if (next != pre) {
if (isAns(v[next], v[node])) dp[node][1] = Math.max(dp[node][0] - Math.max(dp[next][0], dp[next][1])+2+dp[next][0], dp[node][1]);
}
}
}
boolean isAns(int a, int b) {
if (a < 0 || b < 0) return false;
long c = a*b;
int sq = (int) Math.sqrt(c);
return sq*sq == c;
}
}
最后插一下我们的进阶一对一辅导啦
我们是一个针对技术岗（前后端开发、测试、测开、大数据开发）校招一对一进阶提高的工作室。我们从2020年2月份开始，迄今整整三年的时间，带领300+学员斩获1500+大厂offer，参加活动的同学人均5个中大厂offer以上，以下是我们活动内容的介绍！ 万诺coding
我们主要是针对有一定基础的同学提供一对一笔试和面试辅导，针对每个同学不同的情况定制内容，包括但不限于“数据结构与算法”/“计算机基础知识”/“项目梳理”/“面试技巧”/“面试复盘”等内容。
摸底测试：如果有兴趣深入了解我们的活动，需要先参加我们的“摸底测试”（类似面试），方便我们了解你的具体情况（主要是code能力和计算机素养），定制出相应的辅导计划。同时这也是一个双向筛选的过程，如果基础过差的同学，抱歉我们可能无法辅导（基础过差的同学一对一辅导成本过高，对双方都不适合）；摸底测试通过的同学，我们会定制化一个针对性的提高计划。然后你再考虑是否参加我们的活动。
承诺保offer：通过摸底测试后，我们会针对每个同学的情况给定一个“保offer”计划。然后同学可以根据自己的实际情况考虑参不参加我们的活动。
有兴趣的同学可以扫码添加我们的微信（whynotlab）
