美团笔试 美团算法笔试 0809
笔试时间：2025年8月9日
往年笔试合集：
第一题
小美有一个长度为n，仅由大小写英文字母组成的字符串s。需执行m次操作： 操作类型op=1时，给定两个小写字母letter1、letter2（满足letter1 ≤ letter2）， 将字符串中所有位于字母表中[letter1, letter2]区间的小写字母转为对应大写字母； 操作类型op=2时，给定两个大写字母letter1、letter2（满足letter1 ≤ letter2）， 将字符串中所有位于字母表中[letter1, letter2]区间的大写字母转为对应小写字母。
输入描述
一行输入两个整数n, m (1 ≤ n,m ≤ 2×10^5)，分别表示字符串长度和操作次数； 一行输入长度为n的字符串s； 接下来m行，每行输入整数op和两个字符letter1、letter2（op=1时为小写且letter1≤letter2；op=2时为大写且letter1≤letter2 ）。
输出描述
执行完所有操作后得到的最终字符串。
样例输入
3 1
abc
1 a c
样例输出
ABC
说明： 在此样例中，初始字符串"abc"，将区间[a,c]的小写字母统一转换成大写，得到"ABC"。
参考题解
用 index_map 维护 52 个字母（0..25 表示 'a'..'z'，26..51 表示 'A'..'Z'）的复合映射。 读到操作： op == 1：把当前映射到小写区间 [lo, hi] 的项转成对应的大写：index_map[i] = cur + 26。 op == 2：把当前映射到大写区间 [lo, hi] 的项转回小写：index_map[i] = v（其中 v = cur - 26）。 因为每次都基于 index_map 的当前值改，所以天然完成函数的复合。 最后逐字符用 index_map 取最终目标码位，组合成 out 并输出。整体复杂度 O(52*num_ops + n)。
C++：
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
int main() {
string line;
getline(cin, line);
istringstream iss(line);
int n, num_ops;
string text;
iss >> n >> num_ops >> text;
// 0..25 -> 'a'..'z'，26..51 -> 'A'..'Z'
vector<int> index_map(52);
for (int i = 0; i < 52; ++i) {
index_map[i] = i;
}
for (int op_idx = 0; op_idx < num_ops; ++op_idx) {
int op;
char lch, rch;
cin >> op >> lch >> rch;
if (op == 1) { // 小写区间转大写
int lo = lch - 'a';
int hi = rch - 'a';
for (int i = 0; i < 52; ++i) {
int cur = index_map[i];
if (cur < 26 && lo <= cur && cur <= hi) {
index_map[i] = cur + 26;
}
}
} else { // 大写区间转小写
int lo = lch - 'A';
int hi = rch - 'A';
for (int i = 0; i < 52; ++i) {
int cur = index_map[i];
if (cur >= 26) {
int v = cur - 26;
if (lo <= v && v <= hi) {
index_map[i] = v;
}
}
}
}
}
string out;
for (char c : text) {
int t;
if (c >= 'a' && c <= 'z') {
t = index_map[c - 'a'];
} else {
t = index_map[26 + (c - 'A')];
}
if (t < 26) {
out += (char)('a' + t);
} else {
out += (char)('A' + (t - 26));
}
}
cout << out << endl;
return 0;
}
Java：
import java.util.Scanner;
public class CaseTransformer {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int numOps = scanner.nextInt();
String text = scanner.next();
// 0..25 -> 'a'..'z'，26..51 -> 'A'..'Z'
int[] indexMap = new int[52];
for (int i = 0; i < 52; i++) {
indexMap[i] = i;
}
for (int opIdx = 0; opIdx < numOps; opIdx++) {
int op = scanner.nextInt();
char lch = scanner.next().charAt(0);
char rch = scanner.next().charAt(0);
if (op == 1) { // 小写区间转大写
int lo = lch - 'a';
int hi = rch - 'a';
for (int i = 0; i < 52; i++) {
int cur = indexMap[i];
if (cur < 26 && lo <= cur && cur <= hi) {
indexMap[i] = cur + 26;
}
}
} else { // 大写区间转小写
int lo = lch - 'A';
int hi = rch - 'A';
for (int i = 0; i < 52; i++) {
int cur = indexMap[i];
if (cur >= 26) {
int v = cur - 26;
if (lo <= v && v <= hi) {
indexMap[i] = v;
}
}
}
}
}
StringBuilder out = new StringBuilder();
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
int t;
if (c >= 'a' && c <= 'z') {
t = indexMap[c - 'a'];
} else {
t = indexMap[26 + (c - 'A')];
}
if (t < 26) {
out.append((char)('a' + t));
} else {
out.append((char)('A' + (t - 26)));
}
}
System.out.println(out.toString());
}
}
Python：
import sys
tokens = iter(sys.stdin.read().split())
n = int(next(tokens))
num_ops = int(next(tokens))
text = next(tokens)
# 0..25 -> 'a'..'z'，26..51 -> 'A'..'Z'
index_map = list(range(52))
for _ in range(num_ops):
op = int(next(tokens))
lch = next(tokens)
rch = next(tokens)
if op == 1: # 小写区间转大写
lo = ord(lch) - 97
hi = ord(rch) - 97
for i in range(52):
cur = index_map[i]
if cur < 26 and lo <= cur <= hi:
index_map[i] = cur + 26
else: # 大写区间转小写
lo = ord(lch) - 65
hi = ord(rch) - 65
for i in range(52):
cur = index_map[i]
if cur >= 26:
v = cur - 26
if lo <= v <= hi:
index_map[i] = v
out = []
for c in text:
if'a' <= c <= 'z':
t = index_map[ord(c) - 97]
else:
t = index_map[26 + ord(c) - 65]
out.append(chr(97 + t) if t < 26 else chr(65 + t - 26))
print(''.join(out))
第二题
给定一批训练样本与若干测试样本，需手写实现主成分分析（PCA）： 仅保留第一主成分来压缩-重建数据，最后输出每个测试样本在重建后的均方误差（MSE）。步骤：
- 输入读取： train - 二维列表，每行是一个m维数值特征向量； test - 二维列表，维度同train。
- 去均值(mean-center)：X_c = X - μ，其中μ是train的均值。
- 协方差矩阵（总体方差，ddof=0）：Σ = (1/n) * X_c^T * X_c 。
- 求第一主成分： 用numpy.linalg.eigh得到全部特征对(λ_i, v_i)； 按特征值从大到小选取第一主成分v_max； 方向标准化规则——若v_max首个非零分量为负，则整体乘以-1，保证方向唯一。
- 投影-重建： z = (x - μ)^T * v_max ，x_hat = μ + z * v_max 。
- 输出： 对每个测试样本计算MSE(x) = (1/m) * Σ(x_j - x_hat_j)^2 （结果保留两位小数，用JSON数组包裹所有测试样本的MSE输出）。
输入描述
标准输入仅一行，为如下JSON对象： { "train": [[...], [...], ...], "test": [[...], [...], ...] } 其中train长度n≥2，每行长度m≥2；test任意条数，维度同train；所有值为整数或浮点数，无额外空行。
输出描述
标准输出仅一行——测试集中每个样本MSE的字符串形式（两位小数），用JSON数组包裹。
补充说明：算法不含随机过程（无需设置随机种子）。仅允许使用NumPy库与Pandas库实现本题。使用总体方差np.var(x, ddof=0)。
样例输入
{"train": [[0,0],[0,1],[1,0],[1,1]], "test": [[0.5,0.5],[1.5,1.5]]}
样例输出
["0.00", "0.50"]
参考题解
首先读取输入的训练集和测试集数据并转换为 numpy 数组，计算训练集均值并对训练数据进行去均值处理；接着计算协方差矩阵，通过特征值分解得到特征值和特征向量，选取特征值最大的特征向量作为第一主成分并标准化其方向（若首个非零分量为负则取反）；然后对每个测试样本，先去均值后投影到第一主成分，再从投影结果重建样本，计算原始样本与重建样本的均方误差并保留两位小数；最后将所有测试样本的 MSE 结果以 JSON 数组形式输出。
C++：
#include <iostream>
#include <vector>
#include <nlohmann/json.hpp>
#include <Eigen/Dense>
#include <iomanip>
#include <cmath>
using json = nlohmann::json;
using namespace Eigen;
using namespace std;
int main() {
// 读取输入JSON
json input_data;
cin >> input_data;
// 解析训练数据
auto& train_json = input_data["train"];
int num_samples = train_json.size();
int num_features = train_json[0].size();
MatrixXd train_data(num_samples, num_features);
for (int i = 0; i < num_samples; ++i) {
for (int j = 0; j < num_features; ++j) {
train_data(i, j) = train_json[i][j];
}
}
// 解析测试数据
auto& test_json = input_data["test"];
int num_test_samples = test_json.size();
MatrixXd test_data(num_test_samples, num_features);
for (int i = 0; i < num_test_samples; ++i) {
for (int j = 0; j < num_features; ++j) {
test_data(i, j) = test_json[i][j];
}
}
// 计算训练数据均值
RowVectorXd mean_train = train_data.colwise().mean();
// 中心化训练数据
MatrixXd centered_train = train_data.rowwise() - mean_train;
// 计算协方差矩阵
MatrixXd covariance_matrix = (centered_train.transpose() * centered_train) / num_samples;
// 计算特征值和特征向量
SelfAdjointEigenSolver<MatrixXd> solver(covariance_matrix);
VectorXd eigenvalues = solver.eigenvalues();
MatrixXd eigenvectors = solver.eigenvectors();
// 找到最大特征值对应的特征向量（第一主成分）
int max_eigen_idx = 0;
double max_eigenvalue = eigenvalues[0];
for (int i = 1; i < eigenvalues.size(); ++i) {
if (eigenvalues[i] > max_eigenvalue) {
max_eigenvalue = eigenvalues[i];
max_eigen_idx = i;
}
}
VectorXd first_component = eigenvectors.col(max_eigen_idx);
// 调整符号
int non_zero_idx = -1;
for (int i = 0; i < first_component.size(); ++i) {
if (abs(first_component[i]) > 1e-12) {
non_zero_idx = i;
break;
}
}
if (non_zero_idx != -1 && first_component[non_zero_idx] < 0) {
first_component = -first_component;
}
// 计算每个测试样本的MSE
vector<string> mse_results;
for (int i = 0; i < num_test_samples; ++i) {
RowVectorXd test_sample = test_data.row(i);
RowVectorXd centered_test = test_sample - mean_train;
// 计算投影
double projection = centered_test * first_component;
// 重建样本
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
查看6道真题和解析
米哈游一面188人在聊
投递淘天集团等公司10个岗位