程序员基德

03-17 14:19 已编辑中国科学技术大学 C++ 发布于浙江

关注

【春招改编笔试】美团2025.03.08题目解析

✅ 春招备战指南 ✅

💡 学习建议：

先尝试独立解题（建议用时：90分钟/套）
对照解析查漏补缺
配套练习题库

🧸 题面描述等均已深度改编，所有题面背景均为原创，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

互联网必备刷题宝典🔗

2025.03.08-研发岗题目集合

题目一：密码专家

1️⃣：字符串处理与模拟 2️⃣：按规则处理数字和非数字字符 3️⃣：实现字符串左移和反转操作

整体难度：中等

该题目要求实现一个特殊的字符串解密算法。解密过程需要处理数字（更新位移值）和非数字字符（左移字符串、反转或添加字符），按照规则逐步构建解密结果。时间复杂度O(n²)，其中n是加密字符串的长度。

题目二：游戏设计师

1️⃣：二维坐标排序 2️⃣：分别处理四个方向的攻击情况 3️⃣：利用哈希表或有序集合快速查找

整体难度：中等偏难

该题目涉及二维平面上的"炮"攻击问题，需要计算每个炮在四个方向上能攻击到的其他炮的数量。通过对坐标排序并分别处理每个方向，可以高效地解决问题。时间复杂度O(n log n)，其中n是炮的数量。

题目三：安全路径检测

1️⃣：树上路径查询 2️⃣：最近公共祖先(LCA)算法 3️⃣：子序列匹配判断

整体难度：困难

该题目要求判断树上两点之间路径上的字母序列是否包含特定子序列"BUG"。需要先找到两点间的路径（通过LCA），然后判断路径上的字母序列是否包含目标子序列。时间复杂度O(n + q·log n)，其中n是节点数，q是查询次数。

01. 密码专家

问题描述

小毛是一位密码学专家，他设计了一种特殊的字符串解密算法。他给了你一个加密字符串，希望你能按照他的规则将其解密。

解密过程如下：

初始时，解密结果字符串 $t$ 为空，位移值 $p$ 为 $0$ 。
从左到右依次处理加密字符串 $s$ 中的每个字符：
- 如果当前字符是数字 $x$ ，则更新位移值 $p$ ：
  - 若 $p = 0$ ，则将 $p$ 设为 $x$
  - 若 $p \neq 0$ ，则将 $p$ 中的数字向高位移动一位，并在个位添加 $x$ （即 $p = 10p + x$ ）
- 如果当前字符不是数字，则：
  - 先将字符串 $t$ 左移 $p$ 位（即 $t_1t_2...t_pt_{p+1}...t_{|t|} \rightarrow t_{p+1}...t_{|t|}t_1t_2...t_p$ ）
  - 然后将 $p$ 重置为 $0$
  - 接着处理当前字符：
    - 若字符为 $R$ ，则反转字符串 $t$
    - 否则，将该字符添加到 $t$ 的末尾

请你实现这个解密算法，输出最终的解密结果。

输入格式

第一行输入一个整数 $T(1 \leq T \leq 10)$ ，表示测试数据的组数。

接下来的 $T$ 行，每行输入一个由大小写字母和数字组成的字符串 $s(1 \leq |s| \leq 10^3)$ ，表示加密字符串。

输出格式

对于每组测试数据，输出一行字符串，表示解密后的结果。

样例输入

2
meRD2o
D0ame3

样例输出

Demo
Dame

数据范围

$1 \leq T \leq 10$
$1 \leq |s| \leq 10^3$
字符串 $s$ 由大小写字母和数字组成

样例解释说明

样例1第一组	处理"meRD2o"： 1. 添加'm'， $t$ ="m" 2. 添加'e'， $t$ ="me" 3. 遇到'R'，反转字符串， $t$ ="em" 4. 添加'D'， $t$ ="emD" 5. 遇到'2'， $p$ =2 6. 遇到'o'，先左移2位， $t$ ="Dem"，再添加'o'， $t$ ="Demo"
样例1第二组	处理"D0ame3"： 1. 添加'D'， $t$ ="D" 2. 遇到'0'， $p$ =0（无变化） 3. 添加'a'， $t$ ="Da" 4. 添加'm'， $t$ ="Dam" 5. 添加'e'， $t$ ="Dame" 6. 遇到'3'， $p$ =3（后续无字符，不影响结果）

题解

这道题是一个字符串处理问题，要求我们按照特定规则解密一个字符串。解密过程涉及到字符串的添加、反转和左移操作，以及数字的处理。

解题思路很直接，就是模拟整个解密过程：

初始化解密结果字符串 $t$ 为空，位移值 $p$ 为 0
从左到右遍历加密字符串 $s$ 的每个字符：
- 如果是数字，更新位移值 $p$
- 如果不是数字，先左移字符串，重置 $p$ ，然后根据字符类型进行操作

关键点在于如何高效实现字符串的左移和反转操作：

对于左移操作，我们可以使用字符串的切片功能（在Python中）或者substring（在C++和Java中）
对于反转操作，可以使用语言内置的反转函数或者手动实现

在实现时需要注意几个细节：

字符串为空时的处理（此时左移操作不会有效果）
位移值 $p$ 可能大于字符串长度，需要取模处理
数字的累积处理（从0变为单个数字，或者将已有数字左移后添加新数字）

时间复杂度分析：

对于每个测试用例，我们需要遍历加密字符串的每个字符，时间复杂度为 O(|s|)
字符串操作（左移和反转）的时间复杂度也是 O(|s|)
因此总时间复杂度为 O(T * |s|)，其中 T 是测试用例数量，|s| 是加密字符串的长度

空间复杂度：O(|s|)，主要用于存储解密结果字符串。

参考代码

Python

import sys
input = lambda:sys.stdin.readline().strip()

def decrypt(s):
    """解密函数，处理单个加密字符串"""
    t = []  # 使用列表存储解密结果
    p = 0   # 初始位移值为0
    
    # 遍历加密字符串的每个字符
    for c in s:
        if c.isdigit():  # 如果是数字
            x = int(c)
            # 更新位移值p
            p = x if p == 0 else p * 10 + x
        else:  # 如果不是数字
            if t:  # 如果t不为空
                # 计算实际左移位数（取模处理）
                shift = p % len(t)
                # 执行左移操作
                t = t[shift:] + t[:shift]
            
            p = 0  # 重置位移值
            
            if c == 'R':  # 如果是'R'，反转字符串
                t.reverse()
            else:  # 否则，添加到末尾
                t.append(c)
    
    return ''.join(t)  # 将列表转换为字符串返回

def main():
    # 读取测试用例数量
    t = int(input())
    
    # 处理每个测试用例
    for _ in range(t):
        s = input()
        print(decrypt(s))

if __name__ == "__main__":
    main()

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 解密函数，处理单个加密字符串
string solve(const string& s) {
    string t;  // 解密结果
    int p = 0; // 位移值
    
    // 遍历加密字符串的每个字符
    for (char c : s) {
        if (isdigit(c)) {  // 如果是数字
            int x = c - '0';
            // 更新位移值
            p = (p == 0) ? x : p * 10 + x;
        } else {  // 如果不是数字
            if (!t.empty()) {  // 如果t不为空
                // 计算实际左移位数（取模处理）
                int shift = p % t.size();
                // 执行左移操作
                t = t.substr(shift) + t.substr(0, shift);
            }
            
            p = 0;  // 重置位移值
            
            if (c == 'R') {  // 如果是'R'，反转字符串
                reverse(t.begin(), t.end());
            } else {  // 否则，添加到末尾
                t.push_back(c);
            }
        }
    }
    
    return t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;  // 读取测试用例数量
    
    while (t--) {
        string s;
        cin >> s;  // 读取加密字符串
        cout << solve(s) << endl;  // 输出解密结果
    }
    
    return 0;
}

Java

import java.util.*;

public class Main {
    // 解密函数，处理单个加密字符串
    private static String decrypt(String s) {
        List<Character> t = new ArrayList<>();  // 使用列表存储解密结果
        int p = 0;  // 位移值
        
        // 遍历加密字符串的每个字符
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {  // 如果是数字
                int x = c - '0';
                // 更新位移值
                p = (p == 0) ? x : p * 10 + x;
            } else {  // 如果不是数字
                if (!t.isEmpty()) {  // 如果t不为空
                    // 计算实际左移位数（取模处理）
                    int shift = p % t.size();
                    // 执行左移操作
                    List<Character> temp = new ArrayList<>(t.subList(shift, t.size()));
                    temp.addAll(t.subList(0, shift));
                    t = temp;
                }
                
                p = 0;  // 重置位移值
                
                if (c == 'R') {  // 如果是'R'，反转字符串
                    Collections.reverse(t);
                } else {  // 否则，添加到末尾
                    t.add(c);
                }
            }
        }
        
        // 将列表转换为字符串
        StringBuilder result = new StringBuilder();
        for (char c : t) {
            result.append(c);
        }
        
        return result.toString();
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();  // 读取测试用例数量
        sc.nextLine();  // 读取换行符
        
        // 处理每个测试用例
        for (int i = 0; i < t; i++) {
            String s = sc.nextLine();  // 读取加密字符串
            System.out.println(decrypt(s));  // 输出解密结果
        }
        
        sc.close();
    }
}

02. 游戏设计师

问题描述

小基是一位战略游戏设计师，正在设计一款新的棋盘游戏。在这个游戏中，有一种特殊的棋子叫"炮"，它的攻击方式非常独特。

在无限大的二维棋盘上，有 $n$ 个炮，第 $i$ 个炮的坐标是 $(x_i, y_i)$ 。每个炮的攻击规则如下：

炮必须选择一个攻击方向（上、下、左、右）
在选定的方向上，炮需要先看到一个棋子作为"炮架"
炮可以通过炮架攻击到炮架后面的第一个棋子

小基想知道，对于每个炮，如果它进行第一次攻击，最多能攻击到多少个其他的炮。

输入格式

第一行输入一个正整数 $n(1 \leq n \leq 10^5)$ ，表示炮的数量。

接下来的 $n$ 行，每行输入两个整数 $x_i, y_i(-10^5 \leq x_i, y_i \leq 10^9)$ ，表示第 $i$ 个炮的坐标。

输出格式

输出 $n$ 行，每行一个整数，表示第 $i$ 个炮最多能攻击到的炮的数量。

样例输入

样例输出

数据范围

$1 \leq n \leq 10^5$
$-10^5 \leq x_i, y_i \leq 10^9$

样例解释说明

样例1	第1个炮(0,0)可以： 1. 向上攻击：以(0,1)为炮架攻击(0,2)，共1个 2. 向右攻击：以(1,0)为炮架攻击(2,0)，共1个所以最多能攻击2个炮第2个炮(0,1)无法攻击任何炮，因为在任何方向上都没有两个以上的炮第3个炮(0,2)可以向下攻击：以(0,1)为炮架攻击(0,0)，共1个第4个炮(1,0)可以向左攻击：以(0,0)为炮架，但没有更多的炮向右攻击：以(2,0)为炮架攻击(3,0)，共1个第5个炮(2,0)可以向左攻击：以(1,0)为炮架攻击(0,0)，共1个第6个炮(3,0)可以向左攻击：以(2,0)为炮架攻击(1,0)，共1个

题解

这道题考察的是对二维平面上点的处理和查询。我们需要计算每个炮能攻击到的最大炮数量。

首先，我们需要理解炮的攻击规则：炮只能在上、下、左、右四个方向攻击，且需要一个"炮架"（即中间必须有一个棋子），然后才能攻击到炮架后面的第一个棋子。

解题思路如下：

我们可以将所有炮按照坐标分类：
- 对于每个x坐标，收集所有在该x上的y坐标
- 对于每个y坐标，收集所有在该y上的x坐标
对收集到的坐标进行排序，这样我们就可以知道每个炮在四个方向上的相邻炮。
对于每个炮，我们需要检查四个方向：
- 上方向：查找相同x坐标上，y值更大的炮
- 下方向：查找相同x坐标上，y值更小的炮
- 左方向：查找相同y坐标上，x值更小的炮
- 右方向：查找相同y坐标上，x值更大的炮
在每个方向上，如果存在至少两个炮，那么当前炮可以通过第一个炮作为炮架攻击到第二个炮。
统计每个炮在四个方向上能攻击到的炮数，取最大值作为结果。

实现上，我们可以使用哈希表（map或dict）来存储坐标分类，然后使用二分查找或直接遍历来确定每个炮在各个方向上的位置。

时间复杂度分析：

收集和排序坐标：O(n log n)
对每个炮检查四个方向：O(n)
总时间复杂度：O(n log n)

空间复杂度：O(n)，用于存储坐标分类。

参考代码

Python

import sys
from collections import defaultdict
import bisect
input = lambda:sys.stdin.readline().strip()

def main():
    # 读取炮的数量
    n = int(input())
    
    # 存储所有炮的坐标
    cannons = []
    # 按x坐标分组的y坐标列表
    x_to_y = defaultdict(list)
    # 按y坐标分组的x坐标列表
    y_to_x = defaultdict(list)
    
    # 读取每个炮的坐标并分类
    for _ in range(n):
        x, y = map(int, input().split())
        cannons.append((x, y))
        x_to_y[x].append(y)
        y_to_x[y].append(x)
    
    # 对每个分组的坐标进行排序
    for x in x_to_y:
        x_to_y[x].sort()
    for y in y_to_x:
        y_to_x[y].sort()
    
    # 计算每个炮能攻击到的最大炮数
    for i in range(n):
        x, y = cannons[i]
        max_attacks = 0
        
        # 检查垂直方向（相同x坐标）
        if x in x_to_y:
            ys = x_to_y[x]
            # 找到当前y在排序后的位置
            idx = bisect.bisect_left(ys, y)
            
            # 向上方向：检查是否有至少两个炮在当前炮的上方
            if idx < len(ys) - 2:
                max_attacks += 1
            
            # 向下方向：检查是否有至少两个炮在当前炮的下方
            if idx >= 2:
                max_attacks += 1
        
        # 检查水平方向（相同y坐标）
        if y in y_to_x:
            xs = y_to_x[y]
            # 找到当前x在排序后的位置
            idx = bisect.bisect_left(xs, x)
            
            # 向右方向：检查是否有至少两个炮在当前炮的右侧
            if idx < len(xs) - 2:
                max_attacks += 1
            
            # 向左方向：检查是否有至少两个炮在当前炮的左侧
            if idx >= 2:
                max_attacks += 1
        
        print(max_attacks)

if __name__ == "__main__":
    main()

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;  // 读取炮的数量
    
    // 存储所有炮的坐标
    vector<pair<int, int>> cannons(n);
    // 按x坐标分组的y坐标列表
    map<int, vector<int>> x_to_y;
    // 按y坐标分组的x坐标列表
    map<int, vector<int>> y_to_x;
    
    // 读取每个炮的坐标并分类
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        cannons[i] = {x, y};
        x_to_y[x].push_back(y);
        y_to_x[y].push_back(x);
    }
    
    // 对每个分组的坐标进行排序
    for (auto& [x, ys] : x_to_y) {
        sort(ys.begin(), ys.end());
    }
    for (auto& [y, xs] : y_to_x) {
        sort(xs.begin(), xs.end());
    }
    
    // 计算每个炮能攻击到的最大炮数
    for (int i = 0; i < n; ++i) {
        int x = cannons[i].first;
        int y = cannons[i].second;
        int max_attacks = 0;
        
        // 检查垂直方向（相同x坐标）
        if (x_to_y.count(x)) {
            const auto& ys = x_to_y[x];
            // 找到当前y在排序后的位置
            auto it = lower_bound(ys.begin(), ys.end(), y);
            int idx = it - ys.begin();
            
            // 向上方向：检查是否有至少两个炮在当前炮的上方
            if (idx < (int)ys.size() - 2) {
                max_attacks++;
            }
            
            // 向下方向：检查是否有至少两个炮在当前炮的下方
            if (idx >= 2) {
                max_attacks++;
            }
        }
        
        // 检查水平方向（相同y坐标）
        if (y_to_x.count(y)) {
            const auto& xs = y_to_x[y];
            // 找到当前x在排序后的位置
            auto it = lower_bound(xs.begin(), xs.end(), x);
            int idx = it - xs.begin();
            
            // 向右方向：检查是否有至少两个炮在当前炮的右侧
            if (idx < (int)xs.size() - 2) {
                max_attacks++;
            }
            
            // 向左方向：检查是否有至少两个炮在当前炮的左侧
            if (idx >= 2) {
                max_attacks++;
            }
        }
        
        cout << max_attacks << "\n";
    }
    
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 读取炮的数量
        
        // 存储所有炮的坐标
        int[][] cannons = new int[n][2];
        // 按x坐标分组的y坐标列表
        Map<Integer, List<Integer>> xToY = new HashMap<>();
        // 按y坐标分组的x坐标列表
        Map<Integer, List<Integer>> yToX = new HashMap<>();
        
        // 读取每个炮的坐标并分类
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            cannons[i][0] = x;
            cannons[i][1] = y;
            
            // 添加到x坐标分组
            if (!xToY.containsKey(x)) {
                xToY.put(x, new ArrayList<>());
            }
            xToY.get(x).add(y);
            
            // 添加到y坐标分组
            if (!yToX.containsKey(y)) {
                yToX.put(y, new ArrayList<>());
            }
            yToX.get(y).add(x);
        }
        
        // 对每个分组的坐标进行排序
        for (List<Integer> ys : xToY.values()) {
            Collections.sort(ys);
        }
        for (List<Integer> xs : yToX.values()) {
            Collections.sort(xs);
        }
        
        // 计算每个炮能攻击到的最大炮数
        for (int i = 0; i < n; i++) {
            int x = cannons[i][0];
            int y = cannons[i][1];
            int maxAttacks = 0;
            
            // 检查垂直方向（相同x坐标）
            if (xToY.containsKey(x)) {
                List<Integer> ys = xToY.get(x);
                // 找到当前y在排序后的位置
                int idx = Collections.binarySearch(ys, y);
                
                // 向上方向：检查是否有至少两个炮在当前炮的上方
                if (idx < ys.size() - 2) {
                    maxAttacks++;
                }
                
                // 向下方向：检查是否有至少两个炮在当前炮的下方
                if (idx >= 2) {
                    maxAttacks++;
                }
            }
            
            // 检查水平方向（相同y坐标）
            if (yToX.containsKey(y)) {
                List<Integer> xs = yToX.get(y);
                // 找到当前x在排序后的位置
                int idx = Collections.binarySearch(xs, x);
                
                // 向右方向：检查是否有至少两个炮在当前炮的右侧
                if (idx < xs.size() - 2) {
                    maxAttacks++;
                }
                
                // 向左方向：检查是否有至少两个炮在当前炮的左侧
                if (idx >= 2) {
                    maxAttacks++;
                }
            }
            
            System.out.println(maxAttacks);
        }
        
        sc.close();
    }
}

03. 安全路径检测

问题描述

小兰是一家软件公司的技术总监，她负责维护公司的系统架构。公司的系统架构可以描述为一棵有根树，根节点编号为 $1$ ，总共有 $n$ 个节点。

每个节点代表一个服务模块，节点 $i$ 的编号为 $i$ ，同时节点上标记了一个字母 $a_i$ ，代表该模块的状态标识。

小兰发现系统中可能存在安全隐患。她的安全团队发现，当从节点 $u$ 到节点 $v$ 的路径上，如果字母序列的子序列中包含"BUG"，则该路径存在安全风险。而如果不包含"BUG"子序列，则为安全路径。

现在小兰需要进行多次安全检测，每次给定两个节点 $u$ 和 $v$ ，判断从 $u$ 到 $v$ 的路径是否安全。请你帮助她完成这项工作。

注意：子序列是指从原始序列中选择一些元素（可以不连续），而不改变它们的相对顺序组成的新序列。例如，"BUG"是"ABCUDGEF"的一个子序列，但不是"BGCU"的子序列。

输入格式

第一行输入两个整数 $n$ 和 $q(3 \leq n, q \leq 10^5)$ ，分别表示节点个数和查询次数。

第二行输入 $n$ 个整数，其中第 $i$ 个整数表示节点 $i$ 的父节点 $father_i(1 \leq father_i \leq i-1)$ 。特别地，根节点的父节点为 $0$ 。

第三行输入 $n$ 个大写字母，第 $i$ 个字母为 $a_i('A' \leq a_i \leq 'Z')$ ，表示节点 $i$ 上标记的字母。

接下来 $q$ 行，每行输入两个整数 $u$ 和 $v(1 \leq u, v \leq n, u \neq v)$ ，表示一次查询：判断从节点 $u$ 到节点 $v$ 的路径是否安全。

输出格式

共 $q$ 行，每行输出一个字符串。如果对应的路径安全（不含"BUG"子序列），输出"YES"；否则，输出"NO"。

样例输入

样例输出

NO
YES
YES

数据范围

$3 \leq n, q \leq 10^5$
$1 \leq father_i \leq i-1$ 对于 $i > 1$ ， $father_1 = 0$
$'A' \leq a_i \leq 'Z'$
$1 \leq u, v \leq n, u \neq v$

样例解释说明

样例1	树的结构为：1为根节点，2和3是1的子节点，4是2的子节点，5是2的子节点。节点上的字母依次为A、U、G、B、C。查询1：从节点4到节点3的路径是4→2→1→3，路径上的字母为"BUG"，包含子序列"BUG"，所以不安全，输出"NO"。查询2：从节点4到节点5的路径是4→2→5，路径上的字母为"BBC"，不包含子序列"BUG"，所以安全，输出"YES"。查询3：从节点4到节点1的路径是4→2→1，路径上的字母为"BA"，不包含子序列"BUG"，所以安全，输出"YES"。

题解

这道题考察的是树上路径查询和字符串子序列匹配问题。

首先，我们需要明确几个概念：

树上从节点 u 到节点 v 的路径是唯一的，经过的节点形成一个序列
我们需要判断这个路径上的字母是否包含子序列"BUG"

一个关键点是如何高效地处理大量的路径查询。如果每次查询都遍历整个路径上的节点，时间复杂度将非常高。因此，我们需要采用一些高级的树算法和优化技巧。

解题思路如下：

树链剖分预处理：使用树链剖分将树分解为若干条重链，便于快速处理路径查询。
- 对树进行两次DFS：第一次计算每个子树的大小，第二次进行重链划分
- 对于每条重链，预处理它的状态转移函数
状态转移函数：定义状态为匹配"BUG"的进度
- 状态0：尚未匹配任何字符
- 状态1：已匹配到'B'
- 状态2：已匹配到"BU"
- 状态3：已匹配到"BUG"（此时路径不安全）
路径分解与状态转移：
- 使用LCA（最近公共祖先）算法将从u到v的路径分解为上行路径（从u到LCA）和下行路径（从LCA到v）
- 对于每段路径，应用预处理好的状态转移函数
- 如果最终状态为3，则路径不安全；否则安全
查询处理：
- 对于每次查询，计算节点u和v的LCA
- 分别计算u到LCA和LCA到v的路径上字母序列对状态的影响
- 根据最终状态判断路径是否安全