美团第一次笔试

1、模拟即可,注意模一下

#include <bits/stdc++.h>
typedef long long ll;
const int MAXN = 1e3 + 10;
char s[MAXN], t[MAXN], x[MAXN];
int main() {
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%s", s + 1); int n = strlen(s + 1);
    int p = 0, r = 0;
    for (int i = 1; i <= n; ++i) {
      if (s[i] >= '0' && s[i] <= '9') {
        p = p * 10 + s[i] - '0';
      } else {
        if (r > 0) p %= r;
        int xx = 0;
        for (int j = p + 1; j <= r; ++j) {
          x[++xx] = t[j];
        }
        for (int j = 1; j <= p; ++j) {
          x[++xx] = t[j];
        }
        for (int j = 1; j <= r; ++j) {
          t[j] = x[j];
        }
        p = 0;
        if (s[i] == 'R') {
          std::reverse(t + 1, t + 1 + r);
        } else {
          t[++r] = s[i];
        }
      }
    }
    t[r + 1] = 0;
    printf("%s\n", t + 1);
  }
  return 0;
}

2、题面写得像史,一开始题读假了,好在代码改一下就能过。按xy分别排序后存起来二分即可

#include <bits/stdc++.h>
typedef long long ll;
const int MAXN = 1e5 + 10;
struct Node {
  int x, y, idx;
} a[MAXN];
int alls[MAXN];
int get(int x) {
  return x > 0;
}
int main() {
  int n; scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &a[i].x, &a[i].y);
    a[i].idx = i;
  }


  std::unordered_map<int, std::vector<int>> xs, ys;


  std::sort(a + 1, a + 1 + n, [](Node a, Node b) {
    if (a.x == b.x) return a.y < b.y;
    else return a.x < b.x;
  });
  for (int i = 1; i <= n; ++i) {
    xs[a[i].x].push_back(a[i].y);
  }


  std::sort(a + 1, a + 1 + n, [](Node a, Node b) {
    if (a.y == b.y) return a.x < b.x;
    else return a.y < b.y;
  });
  for (int i = 1; i <= n; ++i) {
    ys[a[i].y].push_back(a[i].x);
  }


  for (int i = 1; i <= n; ++i) {
    int x = a[i].x, y = a[i].y;
    int posx = std::lower_bound(xs[x].begin(), xs[x].end(), y) - xs[x].begin();
    int posy = std::lower_bound(ys[y].begin(), ys[y].end(), x) - ys[y].begin();
    int ans = 0;


    ans += get(posx - 1);
    ans += get((int)xs[x].size() - 2 - posx);
    ans += get(posy - 1);
    ans += get((int)ys[y].size() - 2 - posy);
    
    alls[a[i].idx] = ans;
  }


  for (int i = 1; i <= n; ++i) {
    printf("%d\n", alls[i]);
  }
  return 0;
}

3、糊了一个裸LCA+暴力上去0分,没绷住。时间不太够了,讨论下来应该是每个点向下向上维护最近的BUG三个字母,然后LCA即可,不太好写。

*更:似乎有用树链剖分做的,没板子谁写得出来啊

最难绷的是选择题有一道做的时候感觉不太对,但是还是直接交了,结果糊LCA的时候发条消息过来说改题了,做题系统必须提交才能退出去改。

唉,AI面得像史,笔试还得二战

全部评论
佬A了两道还用二战嘛
1 回复 分享
发布于 03-08 21:53 北京
最后一题有lca就好了,可以dfs预处理维护一个mb[i]数组表示祖先中离i最近的B在哪,然后和lca深度比较,再用这个位置找最近的U,然后找G,另一边就是反过来先找G再找U再找B
点赞 回复 分享
发布于 03-09 01:05 天津
我和你差不多,A了两道。选择题双端队列那里做了好几遍,都觉得有3个选项是对的,没办法乱选了一个。后面也没时间去改。 话说AI面试面些啥呀?我还没面,加班背八股中
点赞 回复 分享
发布于 03-08 21:41 广东
我第一题不知道为什么没a,我用的python
点赞 回复 分享
发布于 03-08 21:31 湖北

相关推荐

03-29 22:01
中南大学 Java
##&nbsp;3.25美团一面1.&nbsp;自我介绍2.&nbsp;redis的使用场景,以及为什么使用redis?3.&nbsp;Zset的底层结构是什么?4.&nbsp;为什么Zset要使用两种结构来实现?5.&nbsp;jemeter压测比较关注什么数据?6.&nbsp;高并发场景的稳定性你是怎么理解的?7.&nbsp;介绍一下秒杀的流程?8.&nbsp;如果出现库存扣减成功但是异步调用失败了怎么办?9.&nbsp;还是库存扣减成功了,但是调用mq的rpc接口失败了,怎么办?(我回答的是事务,回滚)10.承接上问,如果因为上述的问题,库存扣减了,mq没有接收到消息,导致库存不一致怎么办?11.redis的k,v结构是怎么设计的?12.怎么保证redis的数据不会丢失?13.主从集群有延迟,主节点刚存进去数据,还没同步就挂了,这时从节点没有数据,&nbsp;那怎么办?14.mysql,订单表怎么设计的?15.如果活动很火爆,有100万QPS的访问量,只持续一分钟,或者5分钟的话,只有一个节点的话根本扛不住,怎么处理?16.场景题:大公司里给员工发工资,十分种以内发十万个人的工资。有一个表存的是公司的账户,里面存的金额。另一个表是员工表,记录的员工的信息。怎么处理?17.算法:删除链表倒数第N个节点(核心代码模式)##&nbsp;3.26美团二面1.自我介绍2.聊以前的经历(高考,考研)3.项目中,你写了个异步处理和加redis缓存将相应时间降低50%,怎么个处理方式,以及是什么业务场景?4.什么样的场景使用消息对立比较合适?或者哪些任务你需要用消息队列去异步处理,你是怎么划分的?5.redis的哪些原理和特性,导致它是个高性能缓存工具?6.介绍自己研究生期间的成果,这个成果的想法怎么产生的,为什么业界的大公司都没想打你能想到。7.本地缓存和分布式缓存的区别,以及使用场景?8.radis的数据一致性相对于本地缓存比较好,是怎么保证?9.怎么保证redis和数据库的数据一致性?(先更新数据库再删除缓存)10.那为什么不先改数据库数据再去更新缓存呢?11.mq在什么场景下使用?12.设计分布式锁怎么去考量,比如key,value的设计,怎么避免死锁?13.rpc从发起到接收,用哪些协议,有哪些阶段哪些流程?14.讲一下高并发架构的设计15.对ai的理解16.闲聊(无手撕)#牛客AI配图神器##面经java##美团约面#
点赞 评论 收藏
分享
评论
3
12
分享

创作者周榜

更多
牛客网
牛客企业服务