美团 0903 机器学习岗 算法笔经
题目组成：4编程 3选择
时长：120分钟
编程题：
1: 两个人打乒乓球, 目前比分为a和b. 获胜条件为至少得11分(即a>=11)且a比b赢两分以上(即a-b>=2）
问最优情况下还要赢几把，a才能获胜?(简单)
2: mex()一个数列, 得出这个数列缺失的最小非负整数：
样例:
输入数的数量4
输入数 5 0 3 1
然后分别在删除5, 0, 3, 1的情况下 返回数列的mex值
如: mex([0,3,1]), mex([5,3,1]), mex(5, 0, 1), mex(5,0,3)
就会分别输出 2 0 2 1
思路：
先找出5 0 3 1的mex_num, 然后遍历删除数
可能因为用了两次for 循环， 导致出现了runtime error.
优化方向(不知道对不对): 找mex_num的时候不要用for循环. 如果有大佬看到刚好有做这个笔试，还请大佬指正.
在此贴个runtime error的代码, 欢迎大家讨论
n = int(input())
nums = list(map(int, input().split()))
ans = []
for i in range(len(nums)):
if i not in nums:
mex_num = i
for num in nums:
if num > mex_num:
ans.append(mex_num)
else:
ans.append(num)
print(' '.join(list(map(str,ans))))
3: 没做，是二叉树相关题目
4: 计算最优任务回报
当前在城市k, 一共有n个城市, m个任务
城市编号为c[i]
如果接任务的城市和当前所在城市相同, 报酬为a[i]
如果接任务的城市和当前所在城市不同, 报酬为b[i]
或者也可以选择不接任务, 报酬为0, 同时所在城市不变.
样例:
输入
n, m, k = 3, 5, 1
c = [2,1,2,3,2]
a = [9,6,2,1,7]
b = [1,3,0,5,2]
输出
13
思路：回溯法
-----------------
0904: 补充：今天中午睡觉的时候有点不服气，就又想了一下第四题，睡觉的时候缕清思路把这题写出来了(仅样例通过, 因为没在笔试了, 不知道如果是笔试的时候会不会超时)
python思路：写一个函数，函数内参数包含: 当前所在城市，任务序号, 是否接受任务, 当前收益
测试样例:
#美团笔试# n, m, k = 3, 5, 1
c=[2,1,2,3,2]
a = [9,6,2,1,7]
b = [1,3,0,5,2]
预期输出结果: 13
代码:
ans = []
cur = 1 #表示当前所在城市编号:
i=0
def back_track(cur,i,task,revenue): #cur表示当前城市, i表示第几次任务, task表示是否接受任务, 用False和True来表示
if i == 5:
ans.append(revenue)
return #这里不需要返回任何东西, 只需要把该条路径的收益放进ans备选即可
if not task: #如果不接任务
cur = cur #当前城市不变
back_track(cur,i+1,False,revenue) and back_track(cur,i+1,True,revenue)
else: #如果接任务
if cur == c[i]:
back_track(cur,i+1,True,revenue+a[i]) and back_track(cur,i+1,False,revenue+0)#本地接任务
else:
back_track(c[i],i+1,True,revenue=b[i]) and back_track(c[i],i+1,False,revenue+0)
return ans
back_track(cur,0,False,0)
back_track(cur,0,True,0)
print(max(ans))
类似资料：