美团后端开发进度

9.2 笔试 100 100 100 45 33.33

蹲大佬们分享第四五题题解,没啥思路,找边界条件骗分了

希望有面试机会

9.4 约一面
全部评论
第四题是dp题:例如 6 4 1 4 3 7 6 2 题解如下: 1.首先删除4个数等价于留下2个数。 2.跟数组顺序无关,因此先将数组排序成:1 2 3 4 6 7 3.枚举每个元素a比其大的且成倍数关系的元素,例如: 1有{2,3,4,6,7} 2有{2,4,6} 3有{6} 4有{} 6有{} 7有{} 4.推导状态转移方程,先思考留下1个数,当留下1个数的时候,dp[i][1]的方案数都等于1。留下2个数,对于每一个元素,只要累加比其大且成倍数关系的元素j的dp[j][2-1]即可。此时dp[1][2]等于5、dp[2][2]等于3、dp[3][2]等于1,其余元素都是0,将其加起来就是8,就等于方案数。依次类推到n,时间复杂度O(n^2)。
1 回复 分享
发布于 2023-09-02 22:54 广东
第四题dp就行,因为要删k个就是留n-k个,循环n-k次,可以理解成每次循环找到保留i个数时以当前数为结尾的序列个数。 每次用一个一维数组tmp记录能除尽当前数的所有数的dp和,记录完后用tmp覆盖dp数组进入下一轮。不过直接这么写会超时,我是把每个数对应的能除尽他的数的下标额外存进了一个二维数组,这样每次tmp数组只要遍历那个数对应的下标数组就行。就100%了
点赞 回复 分享
发布于 2023-09-02 21:37 湖北
第四题二维dp
点赞 回复 分享
发布于 2023-09-02 21:27 安徽
第五题直接输出n/2就过了
点赞 回复 分享
发布于 2023-09-02 21:18 重庆

相关推荐

不愿透露姓名的神秘牛友
07-21 13:41
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
1
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务