美团秋招 第八场 技术笔试 10-7-2023

第一题，模拟二进制，求需要操作的次数

二进制是每次1010这样，假如输入数值是10101，只需要1次就能获得

假如输入30203，就需要3次

非常简单的题

胡乱写的解

# shuru = str(input())
shuru = '30302'
max =0
for i in range(len(shuru)):
    if(int(shuru[i]) > int(max)):
        max = shuru[i]
    if(max == '9'):
        break
print(int(max))

第二题，找宝藏

给你可以操作的次数

给你宝藏的价值列表

给你需要挖的最小价值列表

输出最多能挖多少次

import sys

# can_get = int(input())
# baoz = list(map(int,input().split()))
# zuidi = list(map(int,input().split()))
can_get =   5
baoz=[1,2,3,4,1,2]
zuidi =[3,1,2,3,2,2]
baoz.sort()
zuiduo = 0
for i in range(can_get):
    for y in range(len(baoz)):
        if zuidi[i] <= baoz[y] :
            baoz.pop(y)
            zuiduo +=1
            break
print(zuiduo)

这个n2的解是超时的，几年没玩oj一时想不到怎么优化，晚些丢gpt看看

双指针解

can_get = 5
baoz = [1, 2, 3, 4, 1, 2]
zuidi = [3, 1, 2, 3, 2, 2]
baoz.sort()

zuiduo = 0
i, j = 0, 0
while i < can_get and j < len(baoz):
    if zuidi[i] <= baoz[j]:
        i += 1
        j += 1
        zuiduo += 1
    else:
        j += 1

print(zuiduo)

第三题，最抽象的题，美

需要你找到能组成mei的多少种方法，每个方法只能删掉一个字符

例如 meili,有3种方法，不变：meili， 删掉位置3 mei i，删掉位置4 meil

例如meei，有2种方法，前一个e和后一个e

我悟了

s = "meei" #meimei #meili
ways = 0
for i in range(len(s)):
    y = s[0:i] + s[i+1:]
    if y.find("mei")!=-1:
        ways +=1
if s.find("mei")!=-1:
    ways +=1
print(ways)

第四题，找新朋友，然后输出期望值

例如输入组合 1,2 - 1,3,5 - 1,2,3,4

设他们3个为a，b，c, 我们需要2个进行组合，ab,bc,ac,

然后我们找最长且不重复的数有多少个，例如ab有1,2,3,5 = 4; ac有 1,2,3,4 =4; bc有 1,2,3,4,5 =5

4:2 5:1

4*（2/3） + 5(1/3) =4.3333333333333 7位

m_n = 3
a = set([1,2])
b= set([1,3,5])
c=set([1,2,3,4])
shuzu =[]
sumnumber ={}
shuzu.append(a)
shuzu.append(b)
shuzu.append(c)


max = 0
i = 0
for i in range(len(shuzu)-1):
    e = i +1
    while e < len(shuzu):
        n = len(shuzu[i]|shuzu[e])
        if n in sumnumber:
            sumnumber[n]+=1
        else:
            sumnumber.update({n:1})
        max +=1
        e+=1
total =0
for i in sumnumber:
    total += sumnumber[i]/max * i
print(total)

第五题，耕牛题

给你一个n，一个要求k

给你一个列表，树的节点元素

然后n行2位，母节点，子节点

递归的去找所有子节点的和，多少个因子，输出大于k数量的公因子的统计数量

工程量很大，没时间做g了，最近都是在炼丹搞模型，没怎么去刷题orz；