美团26暑期实习笔试
📍公司：美团26暑期实习
👜岗位：后端开发
📖问题：
一共三道编程题，两道水题，一道高级数据结构题。
字符串模拟
- 题目简介：初始一个空字符串。给一组操作，如果操作是数字就记录下来更新变量g（g初始为0）。否则先将字符串循环右移g位再判断操作，如果该操作是'R'，翻转字符串否则将该操作对应的字符加到字符串后面。
- 代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
string s, res = "";
int g = 0;
cin >> s;
for (char op : s) {
if (isdigit(op)) {
g = g * 10 + (op - '0');
continue;
}
if (res.size()) g %= res.size();
res = res.substr(g) + res.substr(0, g);
if (op == 'R') reverse(res.begin(), res.end());
else res += op;
}
cout << res << endl;
}
return 0;
}
炮能打到的敌人数
- 题目简介：在一个无限大的2D棋盘上有n个炮。每个炮有个坐标（x,y）。该炮的正上方如果有超过两个棋子，则他可以打该方向。正下方，正左边，正右边同理。问这n个炮每个能打到几个方向。
- 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node {
int x, y, id;
}g[N];
int cnt[N];
bool cmp_x(node a, node b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
bool cmp_y(node a, node b) {
if (a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> g[i].x >> g[i].y;
g[i].id = i;
}
sort(g + 1, g + n + 1, cmp_x);
for (int i = 1; i <= n; ++i) {
int L = i - 2, R = i + 2, idx = g[i].id;
cnt[idx] += (L >= 1 && g[L].x == g[i].x);
cnt[idx] += (R <= n && g[R].x == g[i].x);
}
sort(g + 1, g + n + 1, cmp_y);
for (int i = 1; i <= n; ++i) {
int L = i - 2, R = i + 2, idx = g[i].id;
cnt[idx] += (L >= 1 && g[L].y == g[i].y);
cnt[idx] += (R <= n && g[R].y == g[i].y);
}
for (int i = 1; i <= n; ++i) {
cout << cnt[i] << endl;
}
return 0;
}
找BUG
- 题目简介：有一颗树，树上每个节点对应一个字母，问给定的u->v的简单路径上有没有"BUG"这个子序列。有输出"NO"，没有输出"YES"。
- 代码（树链剖分，暴力O(n^2)是0分）
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int h[N], e[N], ne[N], idx;
int n, q, siz[N], dep[N], fa[N], son[N], top[N], id[N], rid[N], cnt;
vector<int> nw[N][3];
char s[N];
string bug = "BUG";
unordered_map<char, int> ump = {
{'B', 0}, {'U', 1}, {'G', 2}
};
void add(int u, int v) {
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
void init_dfs(int u, int f) {
siz[u] = 1;
fa[u] = f;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == f) continue;
dep[v] = dep[u] + 1;
init_dfs(v, u);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs(int u, int t) {
id[u] = ++cnt; rid[cnt] = u; top[u] = t; nw[t][ump[s[u]]].push_back(cnt);
if (!son[u]) return;
dfs(son[u], t);
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa[u] || v == son[u]) continue;
dfs(v, v);
}
}
int find(int x, vector<int> &a) {
int l = 0, r = a.size() - 1, res = -1;
while (l <= r) {
int mid = l + r >> 1;
if (a[mid] <= x) res = mid, l = mid + 1;
else r = mid - 1;
}
return res;
}
string query(int u, int v) {
int ch = 0, ct = 2; // head and tail (head u->v tail v->u)
while (top[u] != top[v]) {
if (dep[top[u]] >= dep[top[v]]) { // find u->v
int tu = top[u];
int f = find(id[u], nw[tu][ch]);
if (~f) u = rid[nw[tu][ch++][f]];
else u = fa[top[u]];
}
else { // find v->u
int tv = top[v];
int f = find(id[v], nw[tv][ct]);
if (~f) v = rid[nw[tv][ct--][f]];
else v = fa[top[v]];
}
if (ch > ct) return "NO";
}
while (u != v) {
if (dep[u] >= dep[v]) {
int tu = top[u];
int f = find(id[u], nw[tu][ch]);
if (~f) {
u = rid[nw[tu][ch++][f]];
if (u < v) break;
}
else break;
}
else {
int tv = top[v];
int f = find(id[v], nw[tv][ct]);
if (~f) {
v = rid[nw[tv][ct--][f]];
if (v < u) break;
}
else break;
}
if (ch > ct) return "NO";
}
if (u == v && ch == ct && s[u] == bug[ch]) return "NO";
return "YES";
}
int main() {
cin >> n >> q;
memset(h, -1, sizeof h);
cin >> s + 1;
for (int i = 1; i <= n; i++) {
int f;
cin >> f;
add(f, i); add(i, f);
}
init_dfs(1, 0);
dfs(1, 1);
while (q--) {
int u, v;
cin >> u >> v;
cout << query(u, v) << endl;
}
return 0;
}
/*
14 4
UBGBUBGGBUGBGU
0 1 1 2 2 4 4 5 3 9 9 10 10 10
6 3
11 14
11 4
11 7
*/
以上代码均为参考代码。最后一题我赛时没掏上，后面口胡补的。
#软件开发笔面经#
查看6道真题和解析
