美团笔试 3.25

去年这个时候就在力扣上写过一次美团的统一在线笔试题，当时是过了4.95，后面看大佬们说是没有判断边界。

今天五道题不难
1.栈的压入弹出序列，力扣原题，链接在下面
2.吃糖 -> 这题就是力扣原题打家劫舍的稍微变种，从不能同时偷相邻的变成不能偷距离<2的
3.巧克力 -> 看到背包能装多少，我还以为背包问题，结果包的容量10^18这么大，不可能，然后想想用贪心，只要求装入巧克力块数最多，那么优先装质量最小的巧克力就行，直到背包容量不够或者巧克力全部装入背包。这种做法复杂度O(nm),超时，于是使用排序+前缀和+二分，可以在O(logn)时间定位到每次询问的最大巧克力个数，总复杂度O(mlogn).
4.字符串split后直接用hashmap存放就行，hhh没有考什么算法。
5.吃糖->最多打破a次规则，我用三维dp解决的，dp[i][j][k] ：i 表示考虑前n个糖果，j为0表示今天没吃糖，j为1表示今天吃糖了，k表示目前已经打破规则的次数。dp[i][j][k] 就表示该状态下能吃的最大美味值。
    那么转移公式如下：
        dp[i][0][j] = Math.max(dp[i-1][0][j] , dp[i-1][1][j]);
        dp[i][1][j] = Math.max(dp[i-1][1][j-1] , dp[i-1][0][j])；
最后再提一嘴，提交完所有的题目后，用电脑的截屏软件将题目保存到本地，是想考完后复盘一下的，请问这样会被判作弊吗？