网易互联网9.12笔试 幸运数字7

题目
幸运数字为7,有一个整数数组nums,请找出并返回能被七整除的子集合的最大和,找不到则返回-1。

输入:(是原话)
一个正整数数组列表nums,用空格区分,1<=1ength (num3)<=100000, sum(nums) <=1000000000

问题
我做的时候怎么修改都是0%。
想问下,是不是他的输入样例有问题?

思路
1. 先把数从大到小排序
nums: 10 20 2 29 → 29 20 10 2
2. 用一个变量 i = 0 = 0000 进行遍历
i = 0 = 0 0 0 0:29 20 10 2,sum = 61,不满足sum%7==0的条件,继续
i = 1 = 0 0 0 1:29 20 10 0,sum = 59,不满足sum%7==0的条件,继续
i = 2 = 0 0 1 0:29 20 0 2,sum = 51,不满足sum%7==0的条件,继续
i = 3 = 0 0 1 1:29 20 0 0,sum = 49, 满足sum%7==0的条件,break并输出结果

原输入样例
输入:
10 20 2 29
输出
49

我猜测实际上测试集的样例
输入:
4
10 20 2 29
输出:
49

有哥们考试的时候A了这题吗?是因为给的样例和实际输入不一样么?
#网易互娱网易互联网秋招##笔试题目##网易#
全部评论
每一个数都对7取余,然后分别放进7个桶中,然后再从桶中取出0的、1和6、2和5、3和4的,然后相加。
1
送花
回复 分享
发布于 2020-09-12 17:50
这个题应该怎么处理输入呢请问?没给出输入的个数,哪Scaner怎么确定退出时机呢请问?
1
送花
回复 分享
发布于 2020-09-12 18:40
现代汽车中国前瞻数字研发中心
校招火热招聘中
官网直投
这个题我dfs剪枝AC了 先从大到小排序,剪枝是后面所有数加起来也不会比现在的值大
1
送花
回复 分享
发布于 2020-09-12 23:54
输入没问题 我用 while(scanf("%d",&x)!=EOF)
1
送花
回复 分享
发布于 2020-09-13 13:44
这道题用dp可以解决
1
送花
回复 分享
发布于 2020-09-13 13:47
楼主的做法我觉得复杂度太高了,很容易过不了,最坏情况比如,“13 7 7 7 7 7 7 7”,会从后面一直找到前面,O(2^n)。。。
1
送花
回复 分享
发布于 2020-09-13 14:13
把所有數字加起來,取餘7, 看看餘几,然後用最小的代價把餘數凑出來. 所有數字進行set排序.也就是餘1的放一塊,餘2的放一塊...以此類推. 比如縂數值是5.那麽我就檢測,能不能把5凑出來,能不能把12凑出來.這就成了一個背包問題...
点赞
送花
回复 分享
发布于 2020-11-30 07:24
比如餘2我這幾個數字分別餘1 6 6 6 6 6 6 6 6,考慮這種極端情況的話一般是7*6+(和的餘數)背包的最大無非是這個.
点赞
送花
回复 分享
发布于 2020-11-30 07:34
那么时间复杂度就是48*7,权是真实的数字,而费用是数字的余数,做完以后挨个检索5,12,19,26,33,40,47的费用的数字,挑取最小的,如果最小的是maxlongint的话,输出不行.
点赞
送花
回复 分享
发布于 2020-11-30 07:37
整理一下,首先把所有数加起来,mod7看看得到的数字是多少,这里用5举例. 然后把所有数字mod7,放进6个数组里,并且从小到大排序,余数为0的不要. 之后进行背包问题,我们的目的是为了凑出来5,12,19,26,33,40,47的费用的数字, 这里权是真实数字,费用是余数数字,要求花费最小,那么进行47*6此运算就算出来了. 如果凑不出来的话证明不行,不存在.
点赞
送花
回复 分享
发布于 2020-11-30 07:42

相关推荐

拉哥聊校招:1.大厂看中的是计算机基础,项目的深度和思考,以及你对技术栈应用在你的项目的业务的思考,以及高并发(以Java为例嘛,就是JUC的掌握),数据库缓存这些。上述掌握了 也需要很长时间的,而且大部分人掌握的还是八股,但校招来说也是够了~(当然小厂一般看中你的上手能力,也就是所谓的“技术”嘛,能写接口也可以了),至于项目这块,因为大多数人都是烂大街项目嘛,所以你需要对于你写的项目需要体现你的思考才是,这些才是你的亮点所在。(前提是进入面试) 2.因为面试官几乎就是看三个模块,一个是实习经历(包括科研经历,假如有的话),一个是项目经历,一个是技能;三个模块的排序就看你对哪个掌握比较深,哪个更深,更有自信就将该模块放在前面。 3.专业技能你写的熟悉,是否真的熟悉,所谓的熟悉是你应用场景、原理都要很懂才叫熟悉,不然的话你经不住面试官拷打很减分的;或许可以考虑换一个说法。技能这块最好是罗列一下,清晰地按照模块分层写:语言及基础、框架、中间件、计算机基础等;(不过你分层写的不错) 4.项目这块最好按照STAR法则去写,按照按照四个模块,项目描述,项目使用的技术栈,项目难点亮点(可以适当加粗),项目做完的收获这样子。我们都知道大部分同学的项目都是烂大街的,这其实没所谓,哪有那么多同学做高并发的项目呢哈哈,很多大厂里面的员工也只是负责 toB 业务的他们也不知道高并发呀~所以,重点在于你对你写的项目的深度思考,你在面对什么相对复杂的业务时用了啥技术去解决?这个技术是否经过验证?权衡?以及带来的后果是啥,浓缩成一句话,你要把你的项目当成要还原一个现成的app去写最好。你是否准备对项目的难点亮点的问题呢?项目问题你这边虽然都是技术栈堆砌,但是问题不大了,整天看起来还是可以的(这边可以给你简历的项目提一些面试官或许会问的问题或者拓展问题) 5.学历很优秀,完全有可能去大厂的呀,现在是秋招提前批和日常实习的专场了,可以好好准备一下,然后充提前批吧~做一个简介:假如需要模拟面试,可以来滴滴我哈哈,一般两次到三次模拟面试就可以避免踩坑了(再强的面霸第一次面试的时候都是做炮灰的,很多学历很好的同学的第一面往往是大厂面试,做炮灰的几率更大,因为小厂也不傻,不给机会面试,所以我们可以给你一次模拟面试,让你真正掌握面试的重点的技巧,而不只是单单背八股文而已~以及包括项目的亮点和难点辅导),简历辅导也是如此。 6.最后的最后,加油努力,祝你成功、顺利。
点赞 评论 收藏
分享
点赞 5 评论
分享
牛客网
牛客企业服务