美团4.16笔试前四题代码复盘(第五题没做)

首先吐槽一下题量。。都是五道代码,网易互娱给两个半小时美团只给两个小时(不过美团的似乎是简单一点)
第一题:
n个学生,m个科目,现在学校要给优秀学生颁奖,评判标准是至少在一个科目上获得了最高分(就是>=其他所有同学的成绩)
实不相瞒,这题我卡了30min。。。因为我最开始看错题了,这是一个n*m数组,每一行是一个学生的各科分数,每一列是各科的各个学生的分数(不懂你们听不听得懂),反正就是,如果你要比较你是不是该科目最高分,你应该去和你那一整列的数据比大小,而不是拿行比大小。换言之,就是普通遍历二维数组不是先行后列吗,这题就是先列后行遍历
结果我最开始先是看错题,然后又在遍历的时候混乱得不行,浪费了好多好多时间。。
直接上代码吧,看代码你们就懂了
def max(list,i,j):
    res=0
    for z in range(i):
        if res<=list[z][j]:
            res=list[z][j]
    return res

n,m=map(int,input().split())#n个学生 m个考试科目
list=[]
for i in range(n):
    list.append([int (i) for i in input().split()])
res=[]
for i in range(m):
    max_grade=max(list,n,i)
    for j in range(n):
        if list[j][i]>=max_grade and j not in res:
            res.append(j)
print(len(res))

第二题:
第一题我做完心就凉了半截了,这一共五道题两小时,第一题我就花了半多个小时,我没了
但是没想到第二题,两分钟就能写完。。
题目是给定四个数a,b,m,x 然后有个运算法则是x=(a*x+b)%m,因为是取余,所以x是重复的,现在叫你把重复部分的长度打印出来(比如说是1,2,3,4,1,2,3,4....这样循环,你就输出4就行)
公式都给你了你就套着算不就行了。。。这题的意义在哪啊
a,b,m,x=map(int,input().split())
list=[]
while True:
    x=(a*x+b)%m
    if x not in list:
        list.append(x)
    else :
        break
print(len(list))
第四题:
先说第四题,因为我AC了
第四题上来先给了一个“类中位数的概念,反正就和中位数的概念差不多,但是这个类中位数一定要在非递减数组里面,并且是取地板计算(看我代码都懂什么意思了),然后现在给定一个数组和一个key,问在数组中最少添加几个数之后,这个key能成为数组的类中位数
比如说,现在给定一个数组2,3,3,3 key是2 那么你就最少需要添加两个数1,1在最前面 。因为你添加一个1后,数组变成1,2,3,3,3,中位数还是3.当你再添加一个1变成1,1,2,3,3,3后,中位数就成了2
看到这里是不是就有思路了,这不就是一个二分查找吗。和“从一个先增后减的数组中找到那个拐点”的思路一模一样啊,你二分之后的中位数要是大于key,那就在最左边添数呗,小于key就在最右边添数呗。因为这是中位数,只用保证位置相同,因为每次添数就添最大值和最小值就行(题目给了是1到1000000)
(我这个代码或许有点问题,因为当时存的时候存岔了,我交上去的代码是AC的)
def middle(list):
    n=len(list)
    temp=(n+1)//2
    return list[temp-1]

n,k=map(int,input().split())
list=[int (i) for i in input().split()]

res=0
if k not in list:
    list.append(k)
    res+=1
list.sort()
temp=middle(list)
while True:
    
    if temp>k and list[0]>=1:
        list.insert(0,1)
        res+=1
    if temp<k and list[-1]<=100000:
        list.append(100000)
        res+=1
    temp=middle(list)
    if temp ==k:
        break
    
print(res)
第三题:
第三题我做出来了但是要不就是超时一点点要不就是爆内存一点点(真的就一点点,Python要求3000ms之内,我的代码3004.。。怎么优化都优化不了)
这题给了一个数学概念,大概就是对于两个点(x,y),他们有一个排列组合(x,x),(x,y),(y,x),(x,x),注意是可以重复的。那么对于n个点来说,两两之间都可以排列,就可以排列出n^2个组合。现在对着n^2的组合进行排序,排序规则就是和字典序一样。现在叫你返回排序后第k个组合的值
比如说(1,2)就有排序(1,1),(1,2)、(2,1)、(2,2)。如果此时k=3,就输出(2,1)
首先!!!
这题不是全排列!!
全排列是不和自己排的!!反正我一开始用Python的permutations,然后就卡了二十分钟在这。。。一直没发现这个问题。其实这题就是两次遍历数组就完事了,根本不是什么鬼全排列
然后我的思路就是自己定义一下比大小,自己写个排序(我写的快排),然后最后输出。然而这样过不去我真的不知道为什么。。。有可能是Python自己的原因,因为真的有些题目是用Python怎么写的超时的。我真的想不出什么别的好方法了,难道说还可以用动规写??不可能啊
先贴一下代码,然后我再一个个解释一下
import itertools
def __sub__(self,rhs):
    if self[0]>rhs[0]:
        return 1
    elif self[0]<rhs[0]:
        return -1
    elif self[0]==rhs[0]:
        if self[1]>rhs[1]:
            return 1
        if self[1]<rhs[1]:
            return -1
        if self[1]==rhs[1]:
            return 0

def quick_sort(list,left,right): #list:[()]
    if left>=right:
        return 
    start=left
    end=right

    pivol =list[start]
    while start<end:
        while start<end and __sub__(list[end],pivol)>=0:
            end-=1
        list[start]=list[end]
        while start <end and __sub__(list[start],pivol)<=0:
            start+=1
        list[end]=list[start]
    list[start]=pivol
    quick_sort(list,left,start-1)
    quick_sort(list,start+1,right)

    
def permute(x,y,res):
    list=[x,y]
    temp=itertools.permutations(list)
    #res=[]
    for i in temp:
            res.append(i)
    return res



n,k=map(int,input().split())
list=[int (i) for i in input().split()]
#list.sort()
res=[]
for i in range(len(list)):
    for j in range(len(list)):
        res.append((list[i],list[j]))
        #res.append((list[j],list[i]))
quick_sort(res,0,len(res)-1)
print(res[k-1])
首先,permute就是那个全排列函数!!!千万不要用,用了就上当了,你只需要两次从头到尾的遍历依次加进list里面就行
Python里面(a,b)代表一个元组,元组就是一个不能修改元素的list,但是依旧可以用下标访问元组里面的数据,这里用元组存储单纯是因为输出方便
__sub__就是我自定义的减法(这好像是运算符重载但是我不会用hhhh),self和rhs就是两个组合(前文说的用元祖储存的东西),比较大小用字典序,第一个大就大,第一个小就小,第一个相等就比第二个
quick_sort就是我自己写的排序,这里用的快排,list的形式我在注释里写了 是[()]形式,所有的组合构成一个list,而各个组合用()存储(也就是前文说的元祖)
因为之前有同学反馈Python代码看不懂。。我其实学过C++和JAVA但是我都忘得差不多了,我就尽可能地用大白话描述一下我的思路
第五题:
没时间做了。。瞟了一眼题感觉好复杂啊。。求个大佬来贴一下AC代码我再去研究一会
#美团2021实习生招聘##美团##笔试题目#
全部评论
太强了!!!
点赞 回复 分享
发布于 2020-04-16 21:58
第四题一模一样的想法,哈哈哈
点赞 回复 分享
发布于 2020-04-16 22:14
请问第二题的题目意思是什么?我没有读懂,这个循环的数哪来的?为什么会循环.....
点赞 回复 分享
发布于 2020-04-16 22:44
第三题直接用sort可以吗
点赞 回复 分享
发布于 2020-08-06 19:54

相关推荐

尊尼获获:闺蜜在哪?
点赞 评论 收藏
分享
5 6 评论
分享
牛客网
牛客企业服务