03-14 12:14 已编辑 华东师范大学 算法工程师 发布于上海
关注
美团算法笔试
选择题8题，一题2.25分，一共20分
编程题4题，一题20分，一共80分
第一题求l到r内有多少个数字有奇数个因数，很明显是完全平方数的个数，所以答案是sqrt(r)-sqrt(l-1)
第二题是写朴素贝叶斯二分类器，题面把整个过程都描述出来了，对着模拟
第三题是给了一棵树，根是1，每个节点给了一个权值a[i]，然后每个节点x可以向x->1路径上第一个a[y]严格大于a[x]的节点y连一条边，最后要求每个节点到根节点1的最短路径长度，这个很明显在dfs的过程中维护单调栈找到连边，连完之后从1开始bfs即可
第四题是给了一张无向图，每个点的点权是点编号+实时的度，q次询问，每次要么删一条边，要么问节点x所在的连通块里面最大的权值，这个离线询问用并查集来做，把所有query按顺序存下来，首先将所有要删的边删掉，把其他边连起来维护并查集以及集合内最大权值，然后倒着枚举query，遇到opt=1也就是删边的query就进行连边，维护并查集，遇到opt=2也就是查询就直接查询此时x节点所在的连通块最大权值，把答案记下来，最后按照询问的顺序把这些答案输出即可
#美团笔试##美团##笔试#
编程题4题，一题20分，一共80分
第一题求l到r内有多少个数字有奇数个因数，很明显是完全平方数的个数，所以答案是sqrt(r)-sqrt(l-1)
第二题是写朴素贝叶斯二分类器，题面把整个过程都描述出来了，对着模拟
第三题是给了一棵树，根是1，每个节点给了一个权值a[i]，然后每个节点x可以向x->1路径上第一个a[y]严格大于a[x]的节点y连一条边，最后要求每个节点到根节点1的最短路径长度，这个很明显在dfs的过程中维护单调栈找到连边，连完之后从1开始bfs即可
第四题是给了一张无向图，每个点的点权是点编号+实时的度，q次询问，每次要么删一条边，要么问节点x所在的连通块里面最大的权值，这个离线询问用并查集来做，把所有query按顺序存下来，首先将所有要删的边删掉，把其他边连起来维护并查集以及集合内最大权值，然后倒着枚举query，遇到opt=1也就是删边的query就进行连边，维护并查集，遇到opt=2也就是查询就直接查询此时x节点所在的连通块最大权值，把答案记下来，最后按照询问的顺序把这些答案输出即可
#美团笔试##美团##笔试#
全部评论
相关推荐
查看18道真题和解析 点赞 评论 收藏
分享