米哈游笔试后端开发题解

第一题:模拟。直接按照题目意思模拟即可，注意p可能会很大，但是每次位移最多也就字符串的长度，所以每次增加p的值的时候可以通过取模避免溢出第二题:哈希+二分。通过哈希表记录每个x和y对应的y和x列表，排序后使用二分查找统计每个点满足条件的相邻点数量。第三题:树链剖分:通过树链剖分和状态转移预处理，快速判断树中路径上的字母序列是否包含子序列 "BUG"。 #美团#  #美团春招#  #美团笔试#

十个选择题，包含408，MySQL等内容编程第一题：字符串模拟，读题比较麻烦，没什么坑点，题目说什么照做（Accept 100%）编程第二题：排序+二分，维护一个哈希表存储每行的x坐标和每列的y坐标排个序，对每个坐标点查询对应行中的idx看左右是否有>=2个的坐标即可（Accept 100%）编程第三题：lca+dfs，不太会。。写了个暴力lca暴力判断一分不给（TLE 0%）#美团笔试# #美团#

这是我做过最无语的笔试题了，第二题求协同过滤还不给皮尔森系数的公式和解释？？？样例只有输入输出，一点解释没有，真怀疑出题人出到一半回家过年了，我用Numpy写出来了和答案不一样都不知道怎么debug,题目本身不难，整体架构没问题，就败在这种小细节上，不知道出题人在干什么，在考我们什么呢？？？而且我严重怀疑第一个用例的答案本身就是错的第四题更离谱，求节点有没有BUG，我写了个dfs求root到目的地的最短路径，我请问呢？？？怎么做到无限循环的，好不容易做出来了，最后testcase死在第一步，这种dfs我写了无数遍了，我真不理解为什么会错，出题人testcase设置极其不合理，第一个testcase能出来299次递归？？我不能理解，testcase不都是从简单到难的嘛，即使对了40%我都不至于这么生气，这个百分之0是在侮辱我40分钟的努力嘛？？？最后附上无限循环的代码def dfs(root,node,path):    if root==node:        return 1    if root==none:        return 0    path.append(root)    for child in root.children:        if dfs(child,node,path):            return 1    path.pop()    return 0