美团2024年秋招第一场笔试题解【技术】

1.包裹分类

小美在美团外卖工作，负责处理包裹的分类。每个包裹都有一个唯一的标识符（ID），ID由一串字母和数字组成。你需要根据包裹的ID来判断它属于哪一类。

分类规则如下：

输入例子：
5
A123
1ABC
A1B2C3
123ABC
A!23

输出例子：
standard
special
mix
invalid
invalid

import sys

n = int(input())
ID = []
for i in range(n):
    ID.append(input().strip())

def contains_alpha_and_digit(s):
    has_alpha = any(c.isalpha() for c in s)
    has_digit = any(c.isdigit() for c in s)
    return has_alpha and has_digit

for idd in ID:
    idclass = str(idd[0])
    idcontent = str(idd[1:])
    if idclass.isalpha() and idcontent.isdigit():
        print("standard")
    elif idclass.isdigit() and idcontent.isalpha():
        print("special")
    elif idclass.isalpha() and contains_alpha_and_digit(idcontent):
        print("mix")
    else:
        print("invalid")

2.小美的密码

小美准备登录美团，需要输入密码，小美忘记了密码，只记得密码可能是 nn 个字符串中的一个。小美会按照密码的长度从小到大依次尝试每个字符串，对于相同长度的字符串，小美随机尝试，并且相同的密码只会尝试一次。小美想知道，她最少需要尝试多少次才能登录成功，最多需要尝试多少次才能登录成功。小美不会重新尝试已经尝试过的字符串。成功登录后会立即停止尝试。

输入例子：
4
ab
abc
ab
ac
ac

输出例子：
1 2
例子说明：
小美可能按照 ["ab", "ac", "abc"] 的顺序尝试，第一次尝试成功，也可能按照 ["ac", "ab", "abc"] 的顺序尝试，第二次尝试成功。
小美在尝试 "ac" 发现不正确后不会继续尝试 "ac"。

import sys
import math
from functools import cmp_to_key

remember = []
n = int(input())
if n==0:
    print(0)
elif n==1:
    print(1)
else:
    right = input().strip()
    for _ in range(n):
        remember.append(input().strip())
    if len(remember)==1:
        print(1)

    def strorder(x, y):
        if len(x) < len(y):
            return -1
        elif len(x) > len(y):
            return 1
        else:
            return 0

    remember = list(set(remember))
    remember.sort(key=cmp_to_key(strorder))
    a = math.inf
    b=0
    for i,key in enumerate(remember):
        if len(key) == len(right):
            a = min(a,i)
            if i == n-1:
                b = n-1
            continue
        if len(key)>len(right):
            b = i-1
            break
        
print(a+1,b+1)

3.小美的数组删除

小美有一个长度为 nn 的数组 a1,a2,…,ana1​,a2​,…,an​ ，他可以对数组进行如下操作：

● 删除第一个元素 a1a1​，同时数组的长度减一，花费为 xx。

● 删除整个数组，花费为 k×MEX⁡(a)k×MEX(a) （其中 MEX⁡(a)MEX(a) 表示 aa 中未出现过的最小非负整数。例如 [0,1,2,4][0,1,2,4] 的 MEX⁡MEX 为 33 ）。

 小美想知道将 aa 数组全部清空的最小代价是多少，请你帮帮他吧。

输入例子：
1
6 3 3
4 5 2 3 1 0
输出例子：
15
例子说明：
若不执行操作一就全部删除，\operatorname{MEX}\{4,5,2,3,1,0\}=6，花费 18 ；
若执行一次操作一后全部删除，\operatorname{MEX}\{5,2,3,1,0\}=4，花费 3+12 ；
若执行两次操作一后全部删除，\operatorname{MEX}\{2,3,1,0\}=4，花费 6+12 ；
若执行三次操作一后全部删除，\operatorname{MEX}\{3,1,0\}=2，花费 9+6 ；
若执行四次操作一后全部删除，\operatorname{MEX}\{1,0\}=2，花费 12+6 ；
若执行五次操作一后全部删除，\operatorname{MEX}\{0\}=1，花费 15+3 ；
若执行六次操作一，\operatorname{MEX}\{\}=0，花费 18 ；

时间超限制了，回来再想想时间复杂度更小的解法：

n = int(input().strip())
beta = []
data = []
cur = 0
import copy


def MEX(num):
    if len(num) == 0:
        return 0
    mex = 0
    sort_num = sorted(num)
    for i in range(len(sort_num)):
        if i != sort_num[i]:
            return i
        else:
            mex = i + 1
    return mex


for i in range(n):
    beta.append(list(map(int, input().split())))
    data.append(list(map(int, input().split())))

while cur < n:
    min_cost = MEX(data[cur]) * beta[cur][1]
    for i in range(beta[cur][0] - 1):
        data[cur].pop(0)
        temp = beta[cur][2] * (i + 1) + MEX(data[cur]) * beta[cur][1]
        min_cost = min(min_cost, temp)
    print(min_cost)
    cur += 1