美团笔试美团算法笔试 0809

笔试时间：2025年8月9日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

小美有一个长度为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 春招笔试合集文章被收录于专栏

2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南