美团笔试 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<=1018

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

第四题

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),需要注意的是,最终答案是所有状态的最大值,不一定是最后一个状态

全部评论
附代码 https://paste.ubuntu.com/p/xTZTFvFsfv/
4 回复 分享
发布于 2023-03-25 21:34 福建
这次题目这么简单,可能不招人了
3 回复 分享
发布于 2023-03-25 22:08 江苏
tql,我只ac了3.5,第3题64%,第五题没写
2 回复 分享
发布于 2023-03-26 11:21 香港
请问第二题的动态规划这个递推式max(dp[i - 3] + a[i], dp[i - 1])是怎么递推出来的呀?
1 回复 分享
发布于 2023-03-26 19:21 广东
为啥你们有些有第五题
1 回复 分享
发布于 2023-03-26 11:03 上海
状态转移方程是不是有点小问题:j == 0时,dp[i][j] = max(dp[i - 1][j], dp[i-2][j]+a[i])
1 回复 分享
发布于 2023-03-26 10:18 四川
我第三题和第五题都是只能过18%。。。真的不懂哪里出问题了
1 回复 分享
发布于 2023-03-26 06:35 美国
原来都ak了
点赞 回复 分享
发布于 2023-03-26 00:27 江西
大佬第三题排序一下直接双指针会方便很多
点赞 回复 分享
发布于 2023-03-25 22:52 广东
想请教一下大佬第二题,这个递推公式是不是没有考虑右边相邻两个糖果不能选的情况?我觉得应该dfs考虑才对吧
点赞 回复 分享
发布于 2023-03-25 21:53 北京
话说参加第二次笔试的话会覆盖第一次笔试的成绩吗
点赞 回复 分享
发布于 2023-03-25 21:40 上海

相关推荐

面试官人很好,态度和蔼可亲,没答出来时也会引导你去思考。由于是晚上面的,导致我白天一天都有点紧张,面的时候状态也不是很好,正常可能面试官提问完应该思考几秒再答,而我就像抢答一样一口气把所有会的都说出来,这样就导致逻辑比较混乱,东一句西一句的。首先是自我介绍,先把会的技术大致讲一下,由于我八股背的多所以着重讲了一下,Java,go,jvm,MySQL,Redis,计网,操作系统这些,然后一小部分闲聊,然后先问了一下项目,面试官问我这个项目是否落实之类的,直接坦言说是写的练手的,包括之前也写过IM通讯,外卖之类的。然后面试官就把提问的重点放在了八股上。先问了Java:类加载器(答:3种+自定义类加载器、tomcat、原因+双亲委派+好处)JVM参数(答:xmx,xms,newsize这些,问我是如何设定的,我回答是把内存分一半给堆,再把堆分一半给新生代,这方面确实不太了解)然后问了一下并发相关的:线程池(答:线程池的7个参数(忘了线程工厂和阻塞时间了),3个重要参数,还有线程如何启用,为什么要设计最大线程数之类的,提到Java栈默认分配1MB运行时不可以更改)AQS(答:先讲clh是自旋锁+list,然后是AQS在这个基础上做的两个优化,然后举了一下reentrantlock根据state如何获取资源)CAS(答:使用三个字段,aba问题,然后将通常搭配自旋锁实现,面试官问通常会自旋多少次,这个不太了解,答的100,然后问100次大概多少秒,回答微秒级,然后面试官讲了一下怎么做资源可能没用完,意识到可能还需要进行阻塞操作)然后考虑一下Linux命令(top,ps,如何使用管道符过滤线程和使用Linux启动线程没答出来)然后问Redis:持久化机制(答:三种aof,rdb,混合,aof的三个参数刷盘策略,rdb以快照保存,使用bgsave会使用子线程来保存不会阻塞,而aof虽然会阻塞但是只在写完数据后追加一条命令,不会太影响,然后是他俩的优缺点,还有混合是怎么保存数据的)集群模式(答:三种,主从复制到缺点再到哨兵机制,正常使用三个哨兵互相监督,主节点挂了投票选主哨兵然后选主节点,然后额外讲一下脑裂的问题,主节点进行数据更新然后把命令写入aof来同步从节点,最后cluster集群,如何实现,使用16383个哈希槽(艹答成16384了),先根据哈希码取余,再根据节点数取余决定放在哪个节点上,然后问了一下我会怎么选集群模式,首先是cluster的问题,会让管道操作之类的失效,然后哨兵会导致整个集群结构变得复杂,使用小项目可能会考虑哨兵,大的考虑cluster,然后考了一下cluster如果一个节点挂了怎么办,根据节点数重新取余然后数据转移,面试官说这么转移比较慢,有没有别的办法,我隐约记得使用一个类似环形数组的方式,想不起来了)然后考了一下MySQL的b+树(这方面的知识点太多了,导致我什么都想讲逻辑就比较乱,讲了一下聚簇索引,树的叶子节点对应着一张页16KB,MySQL有一个区的概念,把这些页放在同一个区中,这样叶子节点的双向链表遍历时速度更快,然后b+树的扇出比较大(非常二,说成扇度之类的,面试官以为说的是扇区)这样层数就比较小,一行1kb数据的话3层可以放心2000w数据)其他的暂时想不起来了算法是lru,面试官问要不要提示,我说写个,然后写了10分钟左右,说大概写好了,但是面试官指出了2个小错误,第一个马上就改回来了,第二个一直没看出来(大脑这时候已经停止工作了)反问:问学习建议,说根据实际的项目进行深入,考虑应该怎么做,还问了一下组里面是做Java的吗?面试官说他是做go的,组里什么语言都有,语言影响不大,连忙补充了一句我对go的底层有深入源码的学习)结束。总体感觉答得不太好,没有太体现出深度,细节也不够全面。
下一个更好呗:佬,我投完云智一直没消息,多久约的一面啊
查看14道真题和解析
点赞 评论 收藏
分享
评论
26
54
分享

创作者周榜

更多
牛客网
牛客企业服务