美团 3/25 笔试 后端

第一题

场景：火车入站出站。小美记录了顺序，判断是否记错；（火车编号不重复）

LC原题，出栈顺序的合法性。

第二题

糖果美味值 I

描述：吃第i个糖果就不能吃第i-1, i-2 , i+1 ,i+2个，每个糖果有一个美味值，求最大美味值。

dp

第三题

装巧克力

描述：给一些巧克力，巧克力边长已知，质量假定为边长平方，给一堆背包，背包重M，输出每个背包最多可装巧克力数量。

M<=10¹⁸

背包问题，先给所有背包排序再贪心求解。

第四题

key-value

输入字符串，形如“HOME=\bash\ssh;LONGNAME=xiaomei;”，构建键值对；

输入查询字符串（键），输出其值，若不存在，输出EMPTY，若重复，输出最后一组。

map直接过

第五题

糖果美味值 I

描述：若干天，每天有一种糖果，糖果具有一定美味值；规定小美今天吃了明天就不能吃，但有K次机会打破规则。

求最大美味值

DP。类似美团18号商店题，甚至简单一点点。