美团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代码我再去研究一会