网易互联网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

相关推荐

点赞 5 评论
分享
牛客网
牛客企业服务