3.25美团算法笔试
a了3.18,那个0.18自认为思路没问题,自测也没问题,不知道为什么只对了0.18
python版本代码如下:
第一题
数火车,其实就是一个栈,给一个入栈顺序,一个出栈顺序,问你这种情况是不是可能的
T = int(input())
for _ in range(T):
flag = True
n = int(input())
x_list = list(map(int, input().split()))
y_list = list(map(int, input().split()))
def is_possible_order(x_list, y_list):
stack = []
i = 0
for x in y_list:
while not stack or stack[-1] != x:
if i == len(x_list):
return False
stack.append(x_list[i])
i += 1
stack.pop()
return True if not stack else False
flag = is_possible_order(x_list, y_list)
if flag is True:
print('Yes')
else:
print('No')
第二题
糖果美味值
经典动态规划,就是看现在这个选不选。这个选了,意味着前两个都不能选了,所以是a[i]+dp[i-3],如果不选,那就等于选到前面为止的美味值即dp[i-1]
n = int(input())
a = [int(x) for x in input().split()]
dp = [0] * n
dp[0] = a[0]
dp[1] = max(a[1], a[0])
dp[2] = max(a[2], a[0], a[1])
for i in range(3,n):
dp[i] = max(dp[i-3] + a[i], dp[i-1])
print(dp[n-1])
第三题
也是很经典的动态规划,就是不知道为什么只a了18%,这个dp就是现在能拿几块巧克力,dp[?]这个?是当前背包的容量,每选一个,就要减去当前巧克力的重量(cho[i]^2),同时多一个巧克力
import sys
n, m = map(int, sys.stdin.readline().strip().split())
cho = list(map(int, sys.stdin.readline().strip().split()))
ask = list(map(int, sys.stdin.readline().strip().split()))
bagsize = max(ask)
dp = [0] * (bagsize + 1)
for i in range(n):
for j in range(bagsize, cho[i] * cho[i]-1, -1):
dp[j] = max(dp[j], dp[j-cho[i] * cho[i]] + 1)
res = []
for i in range(m):
print(dp[ask[i]])
第四题
给一个字符串,以分号分割。每个key=value当做一个键值对存到字典里。给一串字符串查找,如果没有这个key输出empty,如果有一个就输出value,如果有多个就输出最新的(可以直接覆盖,这样找到的就是最新的)。唯一要注意的就是直接按照“;”分割会导致最后多一个空字符串,删了就可以
S = list(input().strip().split(';'))[:-1]
dic_ = {}
for i in S:
left, right = i.split('=')
dic_[left] = right
q = int(input())
for _ in range(q):
q_str = input().split()
if q_str[0] not in dic_:
print('EMPTY')
else:
print(dic_[q_str[0]])
#我的实习求职记录##软件开发2023笔面经#