美团笔试 3.25 已AK，附思路

第一题

描述：给定入栈序列和出栈序列，判断是否合理。

思路：使用栈来模拟，使用p指向出栈序列起始位置，循环向栈中push入栈序列，每次push之后while判断栈顶元素是否等于出栈序列p位置，若是，则栈poll，p+1。最终判断栈是否为空即是否合理。

第二题

糖果美味值 I

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

dp[i]表示前i个糖果的最大美味值，dp[0]=a[0], dp[1] = max(dp[0], dp[1]), dp[2] = max(dp[0], dp[1], dp[2]), 转移方程dp[i] = max(dp[i - 3] + a[i], dp[i - 1]) (i > 2)，此外注意a.length分别等于0，1，2时的特殊情况处理

第三题

装巧克力

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

M<=10¹⁸

首先计算巧克力质量数组并排序，然后使用贪心算法求解，不过以题目的数据量，这样子会超时。故而需要优化，可以采用前缀和加二分进行优化，计算质量数组的前缀和数组，由于前缀和数组单调递增，故只需对质量前缀和数组进行二分求解即可。

第四题

key-value

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

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

使用Map直接过

第五题

糖果美味值 I

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

求最大美味值

定义dp[i][j]表示对于前i天的糖果、用了j次机会且选择了a[i]的最大美味值，则dp[0][0] = a[0], dp[1][0] = a[1], dp[1][1] = a[0] + a[1], 则转移方程为：j == 0时，dp[i][j] = max(dp[0][j]...dp[i - 2][j]) + a[i], j>0时，dp[i][j] = max(max(dp[0][j]...dp[i - 2][j]) + a[i], dp[i-1][j-1]+a[i]) (i > 1)，需要注意的是，最终答案是所有状态的最大值，不一定是最后一个状态