昨天 11:45 中山大学 C++ 发布于广东
关注
记录3.14美团技术类笔试编程题。
#美团笔试# 1. 求l~r中因子个数为奇数的数的个数。
要满足要求就要保证所有质因子的次幂为偶数，也就是只有完全平方数满足条件，找符合条件的完全平方数即可，复杂度根号n
2.超级斐波那契数列，每个数等于前k个数之和。q次询问，每次问第k项是多少。
动态维护最后k个数的和，每次剔除最左边的，加上最右边的。复杂度O（n）
3.给定一个无向图，每个点的权值为当前该点度数加上该点的编号。两种指令，第一种是删除图中某条边，第二种是询问某个点所在连通块中，权值最大的点的权值为多少
我的做法是从后往前处理指令序列将删边操作变为加边操作，用并查集维护连通块以及连通块中最大权值。复杂度O（n）
#美团# #笔试# #算法题#
要满足要求就要保证所有质因子的次幂为偶数，也就是只有完全平方数满足条件，找符合条件的完全平方数即可，复杂度根号n
2.超级斐波那契数列，每个数等于前k个数之和。q次询问，每次问第k项是多少。
动态维护最后k个数的和，每次剔除最左边的，加上最右边的。复杂度O（n）
3.给定一个无向图，每个点的权值为当前该点度数加上该点的编号。两种指令，第一种是删除图中某条边，第二种是询问某个点所在连通块中，权值最大的点的权值为多少
我的做法是从后往前处理指令序列将删边操作变为加边操作，用并查集维护连通块以及连通块中最大权值。复杂度O（n）
#美团# #笔试# #算法题#
全部评论
相关推荐