2023-03-25 21:18 已编辑 河海大学 后端工程师 发布于江苏
关注
美团笔试 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])；
最后再提一嘴，提交完所有的题目后，用电脑的截屏软件将题目保存到本地，是想考完后复盘一下的，请问这样会被判作弊吗？
今天五道题不难
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])；
最后再提一嘴，提交完所有的题目后，用电脑的截屏软件将题目保存到本地，是想考完后复盘一下的，请问这样会被判作弊吗？
没有标题
https://gw-c.nowcoder.com/api/sparta/jump/link?link=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fzhan-de-ya-ru-dan-chu-xu-lie-lcof%2F
全部评论
sdsibie
东吴大学 Java
从哪里看这些题目啊
在鼓楼健身的小西瓜
南京大学 Java
用Go写的，第一题超时，卡81，跟**上的答案几乎一模一样，到现在没找到原因
lemonlemon777
美团_后端开发
我们思路包括最后一题的dp数组几乎一模一样了
相关推荐
查看9道真题和解析 点赞 评论 收藏
分享