公司：美团

考试题型：编程 4 道、选择 3 道

笔试平台：赛码

时长：120分钟

时间：2023-03-25 19:00-21:00

编程题

火车迷

描述

小美是一个火车迷。最近她在观察家附近火车站的火车驶入和驶出情况，发现火车驶入和驶出的顺序并不一致。经过小美调查发现，原来这个火车站里面有一个类似于栈的结构，如下图所示：

例如可能1号火车驶入了火车站中的休息区s，在驶出之前2号火车驶入了。那么在这种情况下，1号火车需要等待2号火车倒车出去后才能出去（显然被后面驶入的2号火车挡住了，这个休息区s只有一个出入口）。

出于好奇，小美统计了近些天的火车驶入驶出情况，开始统计和结束统计时休息区s中均是空的。由于中途疏忽，小美觉得自己好像弄错了几个驶入驶出顺序，想请你帮她验证一下。值得注意的是，小美虽然可能弄错了顺序，但对火车的记录是不重不漏的。

形式化地来形容休息区s，我们视其为一个容量无限大的空间，假设两列火车 i 和 j 同时处于休息区s中，驶入时刻 T_in 满足 T_in(i)<T_in(j)，则驶出时间T_out必定满足T_out(i)>T_out(j)，即，先进后出。

输入描述

第一行一个整数T表示数据组数。

对每组测试而言：

第一行一个整数n，表示观察到的火车数量。

第二行n个整数 x₁,x₂,...,x_n，表示小美记录的火车驶入休息区s的顺序。

第三行n个整数 y₁,y₂,...,y_n，表示小美记录的火车驶出休息区s的顺序。

1≤T≤10,1≤n≤50000,1≤x_i,y_i≤n, 且{x_n} 、{y_n} 均为{1,2,3,...,n}的一个排列，即1~n这n个数在其中不重不漏恰好出现一次。

输出描述

对每组数据输出一行：如果小美记录的驶入和驶出顺序无法被满足则输出No，否则输出Yes。

示例

输入

3

3

1 2 3

1 2 3

3

1 2 3

3 2 1

3

1 2 3

3 1 2

输出

Yes

Yes

No

说明：

对第一组数据：

每辆火车刚驶入便立刻驶出即可满足此记录。

对第二组数据：

[ <- 休息区出口 （空 初始状态）

[1 <- 休息区出口 （1号驶入）

[1 2 <- 休息区出口 （2号驶入）

[1 2 3 <- 休息区出口 （3号驶入）

[1 2 <- 休息区出口 （3号驶出）

[1 <- 休息区出口 （2号驶出）

[ <- 休息区出口 （1号驶出）

记录可以被此种方案满足。

对第三组数据：

[ <- 休息区出口 （空 初始状态）

[1 <- 休息区出口 （1号驶入）

[1 2 <- 休息区出口 （2号驶入）

[1 2 3 <- 休息区出口 （3号驶入）

[1 2 <- 休息区出口 （3号驶出）

发现1号被2号堵住，无法先于2号驶出。

可以证明，亦不存在其他驶入驶出方案使得第三组数据满足要求。

思路

使用栈这来模拟火车驶入驶出的过程，参考**************************。

代码

T = int(input())
for k in range(T):
    n = int(input())
    x = list(map(int, input().split()))
    y = list(map(int, input().split()))
    stack = []
    j = 0
    for i in x:
        stack.append(i)
        while stack and stack[-1] == y[j]:
            stack.pop()
            j += 1
    if len(stack) == 0:
        print("Yes")
    else:
        print("No")

分糖

描述

小美因乐于助人的突出表现获得了老师的嘉奖。老师允许小美从一堆 n 个编号分别为 1,2,...,n 的糖果中选择任意多个糖果作为奖励（每种编号的糖果各一个），但为了防止小美一次吃太多糖果有害身体健康，老师设定了一个限制：如果选择了编号为 i 的糖果，那么就不能选择编号为 i-1, i-2, i+1, i+2 的四个糖果了。在小美看来，每个糖果都有一个对应的美味值，小美想让她选出的糖果的美味值之和最大！作为小美的好朋友，请你帮帮她！

输入描述

第一行一个整数n，表示糖果数量。

第二行n个整数 a₁,a₂,...,a_n，其中 a_i 表示编号为 i 的糖果的美味值。

1≤n≤50000, 1≤a_i≤10000

输出描述

输出一行一个数，表示小美能获得的糖果美味值之和最大值。

示例

输入

7

3 1 2 7 10 2 4

输出

14

说明：最优的方案是选择编号为1，4，7的糖果。

思路

动态规划，参考*************************。

代码

n = int(input())
a = list(map(int, input().split()))
if n <= 3:
    print(max(a))
else:
    dp = [0] * n
    for i in range(3):
        dp[i] = max(a[0:i+1])
    for i in range(3, n):
        dp[i] = max([dp[i-3] + a[i], dp[i-2], dp[i-1]])
    print(dp[n-1])

春游

描述

小美明天要去春游了。她非常喜欢吃巧克力，希望能够带尽可能多的巧克力在春游的路上吃。她现在有n个巧克力，很巧的是她所有的巧克力都是厚度一样的正方形的巧克力板，这n个巧克力板的边长分别为 a₁,a₂,...,a_n。因为都是厚度一致的正方形巧克力板，我们认为第 i 个巧克力的重量为 a_i²。小美现在准备挑选一个合适大小的包来装尽可能多的巧克力板，她十分需要你的帮助来在明天之前准备完成，请你帮帮她。

输入描述

第一行两个整数 n 和 m，表示小美的巧克力数量和小美的询问数量。

第二行 n 个整数 a₁,a₂,...,a_n，表示 n 块正方形巧克力板的边长。注意你不能将巧克力板进行拆分。

第三行 m 个整数 q₁,q₂,...,q_n，第 i 个整数 q_i 表示询问：如果小美选择一个能装 q_i 重量的包，最多能装多少块巧克力板？（不考虑体积影响，我们认为只要质量满足要求，巧克力板总能塞进包里）

1≤n,m≤50000, 1≤a_i≤10⁴,1≤q_i≤10¹⁸

输出描述

输出一行m个整数，分别表示每次询问的答案。

示例

输入

5 5

1 2 2 4 5

1 3 7 9 15

输出

1 1 2 3 3

说明：

包最大重量为1，能装1²重量，块数为1

包最大重量为3，也最多只能装1²重量，块数为1

包最大重量为7，能装1²+2²重量，块数为2

包最大重量为9，能装1²+2²+2²重量（因为有两块巧克力板边长都为2），块数为3

包最大重量为15，也最多能装1²+2²+2²重量，块数为3

思路

贪心+前缀和+二分：优先选择重量小的巧克力。

代码

n, m = map(int, input().split())
a = list(map(int, input().split()))
q = list(map(int, input().split()))
a.sort()
pre = [0 for _ in range(n + 1)]

for i in range(1, n + 1):
    pre[i] = pre[i-1] + a[i-1] ** 2

for query in q:
    left, right = 1, n
    while left < right:
        mid = (left + right) // 2
        if pre[mid] < query:
            left = mid + 1
        else:
            right = mid
    if pre[left] == query:
        ans = left
    else:
        ans = left - 1
    print(ans, end=' ')

解释器

描述

小美因为自己差劲的表达能力而苦恼，小美想制作一个解释器，这样她可以在无法表达的情况下让解释器帮她解释。好巧不巧小美翻开了编译原理的书，找到了解释器的制作方式，她决定先制作一个书上习题中描述的小小解释器试试。

小美需要读入一行字符串，其格式为"key1=val1; key2=val2; ...; keyn-1=valn-1; keyn=valn;"（不包含引号）这样的 n 对 key,value 对，其中 key_i 和 val_i 为第 i 对 key,value 对，且均为仅包含大小写英文字母、数字与斜杠的非空字符串。例如对于字符串"SHELL=/bin/bash;HOME=/home/xiaomei;LOGNAME=xiaomei;"，那么其中包含三对 key,value 对，以 (key,value) 形式展示，分别为 (SHELL,/bin/bash)、(HOME,/home/xiaomei)、(LOGNAME,xiaomei)。

接下来，小美的解释器需要接受 q 次询问，每次询问给出一个仅包含大小写英文字母、数字与斜杠的非空字符串，如果存在某对 key,value 对的 key 值与之相同，那么输出对应的 value；如果存在多对 key,value 对的 key 值与之相同，那么输出其中编号最大的，也即最后那一对的 value 值；如果一对也不存在，那么输出 EMPTY。

输入描述

第一行一个字符串 S，满足题中所述格式。

接下来一个整数 q，表示有 q 个询问。

接下来 q 行，每行一个仅包含大小写英文字母、数字与斜杠的非空字符串，分别为 S₁,S₂,...,S_q，依次表示 q 次询问。

令 |S| 表示字符串 S 的长度。

S 中至少包含一对 key,value 对。

输出描述

输出 q 行，每行一个字符串表示答案。

样例

样例输入

LOGNAME=default;SHELL=/bin/bash;HOME=/home/xiaomei;LOGNAME=xiaomei;

4

SHELL

HOME

LOGNAME

logname

样例输出

/bin/bash

/home/xiaomei

xiaomei

EMPTY

说明：

第3个询问有两对满足，分别是第1对和第4对，选择编号大的（也就是后者），为xiaomei而不是default。

第4个询问不存在满足的，输出EMPTY。

思路

哈希表，注意去除字符串中的空格。

代码

S = input().strip()
q = int(input())
kv_list = [s.split('=') for s in S.split(';')][:-1]
d = {k: v for k, v in kv_list}
ans = []
for i in range(q):
    Sq = input().strip()
    ans.append(d.get(Sq, 'EMPTY'))
    
for i in range(q):
    print(ans[i])

选择题

可以用神经网络构造的算法

高维问题和低维嵌入

机器学习：PCA、决策树、Pearson积矩系数估计、期望-最大化（EM）算法