首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
AI面试、笔试、校招、雇品
HR免费试用AI面试
最新面试提效必备
登录
/
注册
小乌
2016-08-02 23:06
电子科技大学 Java
关注
已关注
取消关注
网易笔试Android编程题第三题最大乘积
大家的思路是什么啊,我当时想的是dp,后来发现不适合有负数的,或者我不知道怎么适用于负数
提示
全部评论
推荐
最新
楼层
wj_杭
杭州电子科技大学 算法工程师
有大神共享答案了,穷举法做的: http://blog.csdn.net/siphiababy/article/details/52116246 大神没有加注释,我自己加了注释,希望有用: import java.util.ArrayList; import java.util.List; /** * 用穷举法,列出了所有可能性 * 原理如下: * 比如从左到右总共有20个值(编号1,2,3,...,20),而其中按顺序被选中的只有5个,不考虑别的条件,也就是说,此时要把选中的5个的所有可能心都列出来 * 初始为前五个(1,2,3,4,5),也就是说,最后最大的5个选择只有(16,17,18,19,20) * 所以之后会有: * 1,2,3,4,6 1,2,3,4,7 1,2,3,4,8 ... 1,2,3,4,20(只有最后一个数字变化) * 1,2,3,5,6 1,2,3,5,7 1,2,3,5,8 ... 1,2,3,5,20 * 1,2,3,6,7 1,2,3,6,8 1,2,3,6,9 ... 1,2,3,6,20 * ... * 1,2,4,5,6 1,2,4,5,7 1,2,4,5,8 ... 1,2,4,5,20 * ... * 根据规律即可写出相应的代码来列举出所有可能 * 可以看出,每行的每个值都只有最后一个数字在变化,所以每行可以看成是一个集合ai;总共的列数又是一个集合A * * 之后根据每行结果中,相邻之间的差d,将不满足要求的ai给remove掉,剩余的集合A就是满足条件的所有情况 * 然后根据A中每个集合元素中的编号,求出最终的最大乘积 */ public class Test_4 { /** * * @param n 总数 * @param k 按顺序选中的人数 * @param d 编号相邻之间的最大差 * @param a n个人,每人的能力值 * @return */ static int com(int n, int k, int d, int[] a) { if (n < k || n <= 0 || k <= 0) { System.out.println("n,k数据输入不合理"); return 0; } //为方便计算,数组坐标从1开始,0不考虑 int[] b = new int[k + 1]; //用来临时存储按先后顺序的k个编号,此时先不考虑编号间的差d int[] fg = new int[k + 1]; //整个数组a中,最大的一种编号顺序,当然是a的最后k个连续的编号 for (int i = 1; i <= k; i++) { b[i] = i; //初始化时候,第一种最小的情况,就是前k个编号 fg[i] = i - k + n; //最大的情况,最后k个编号 } //(具体看原理解释)泛型为集合,是因为根据前面原理描述的,每行存储多种情况,只有最后一个数字变化。列和列之间,也只有一个数字在变化 List<List<Integer>> comList = new ArrayList<>(); while (true) { List<Integer> comp = new ArrayList<Integer>(); for (int i = 1; i <= k; i++) comp.add(b[i]); //把规律计算出的可能性存入当前一行的集合 ,行(具体看原理解释) comList.add(comp); //放入整个外层集合,列(具体看原理解释) if (b[1] == n - k + 1) //当列完了最后一种最大的情况(就是数组的随后k个编号),则退出循环 break; /** * 此循环的简单解释 * 每种可能中,都从最后一个编号开始计算每种可能性, * 最后一种全都列举完,那就从倒数第二种开始再列每种可能性,此时要考虑的是最后2个编号的变化,依次3个编号的变化。。。 * 最好看最前面原理中示例的演示 */ for (int i = k; i >= 1; i--) { //每次用当前的编号顺序和最大的比 if (b[i] < fg[i]) { b[i]++; //编号顺序的最后一个依次往后递增 for (int j = i + 1; j <= k; j++) //此过程需要根据原理中列举的示例来演示,不好描述 b[j] = b[j - 1] + 1; //后一个起始永远都是前一个加一 break; } } } //从此时开始考虑编号间隔不大于d for (int i = 0; i < comList.size(); i++) { //剔除所有情况中,不满足间隔不大于d的所有情况 List<Integer> cc = comList.get(i); for (int j = 1; j < cc.size(); j++) { if (cc.get(j) - cc.get(j - 1) > d) { //发现有超过d的就移除,移除后,当前cc为空,需要跳出当前内部循环 comList.remove(i); //移除后,外层集合少去一个,顺序发生变化,所以要i=i-1 i = i - 1; break; } } } /** * 下方不需要再具体解释了,一目了然 */ int max = 0; for (int i = 0; i < comList.size(); i++) { int j = 0; int product = 1; while (j < k) { //comList中存储的是每种满足条件的编号序列,可以对应到数组a中取出相应的值 //最初计算编号是按1开始的,所以下方需要-1 product = product * a[comList.get(i).get(j) - 1]; j++; } if (product > max) max = product; } return max; } public static void main(String[] args) { int[] i = {5,10,56,-30,-15,-25,-40,26,15,10}; //测试数据 System.out.println(com(10, 3, 3, i)); } }
点赞
回复
分享
发布于 2016-08-05 02:41
324234
快手_Android研发工程师
咦。 那这样子就是穷举法对吧?
点赞
回复
分享
发布于 2016-08-03 09:48
牛客722894号
C++
记录当前的最大最小,但是最后才发现这个题的数据非常大,还需要用大数么?。。
点赞
回复
分享
发布于 2016-08-03 09:31
forgot93
杭州电子科技大学 Java
每次DP 记录最大最小。 注意合理初始化就行了
点赞
回复
分享
发布于 2016-08-02 23:20
〝No_Body〞
武汉大学 算法工程师
Leetcode原题 我记得
点赞
回复
分享
发布于 2016-08-02 23:16
schizophrenia
中国科学院大学 C++
最大最小一起搞?
点赞
回复
分享
发布于 2016-08-02 23:10
暂无评论,快来抢首评~
相关推荐
昨天 11:22
桂林电子科技大学 Java
已经练成了面试吹牛神功
我都不敢相信我能输出这么多,简直不知道自己在说啥,,,能找到工作就行
点赞
评论
收藏
分享
不愿透露姓名的神秘牛友
07-03 15:55
暑假找实习太难了吧
为什么就招一个实习生非要叫一堆人去面试,现在这种天气,这么热,而且实习岗位又不是什么技术含量,非得叫一堆人去线下面试。面试结束问什么时候出结果说后面还有面试可能一周后,一问招多少人,结果就招一个然后叫一堆人去面试,真的破防,天气这么热,来回交通费十几二十块,大学生找实习就活该这样吗?真的是累了,工资基本就是一百一天,有的还没有,累了
点赞
评论
收藏
分享
06-03 19:26
西北农林科技大学 C++
这是什么中老年人的发言
上来就是就业毫无难度😅
Twilight_m...:
经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞
评论
收藏
分享
05-15 17:23
华中科技大学 Java
🙀
这是招了多少实习生啊,怎么都到沙发上办公了
深夜书店vv:
腾讯是这样的,去年很多走廊都加桌子当工区
点赞
评论
收藏
分享
07-02 21:56
快手_快STAR广告引擎(准入职员工)
快手内推
在快手做了三个多月的后端开发实习,在这里浅浅分享下我的实习体验~ 工作节奏: 基本上是早10晚9,周末双休。整体来说工作强度还是不小的,不过应该也是互联网常态了吧QAQ 福利待遇: 技术岗是400/天,晚上8点以后下班会发30餐补,入职也会一次性发180能量券,学校不在当地的话还可以申请1500/月的房补。¥这块老铁厂还是挺大方的哈哈。 实习生培养: 团队氛围很nice,我的mentor人真的很好,有问题向他请教都会很细致很耐心地给我解答,好感度upup~不过同事们平时可能都比较忙,捕捉到他们不容易,所以每次沟通或者汇报前最好提前做好准备。具体工作职责的话,一开始基本是接同事们剩下的活,直接上...
快手公司福利 842人发布
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
点赞
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
🌟择难路,未有疑,四非学院本运气拉满,春招拿下大厂后端
6.4W
2
...
其实主包早就找到工作了,但还是每天都刷
1.2W
3
...
史上最细SQL实战系列:sql笔试例题总结篇(建议收藏)
1.1W
4
...
恋爱四年没想到过自己会出轨
6476
5
...
快star-x二面凉经
4514
6
...
离开软件测试才发现外面没有雨
4157
7
...
字节拒绝、百度毁约,7.1 腾讯 Offer 到手:25 届双非碎碎念(25届最晚Offer)
3906
8
...
小红书二面(第二天oc)
3902
9
...
没实习 == 秋招凉?
3665
10
...
从天坑文科到大二腾讯的经历
3663
创作者周榜
更多
正在热议
更多
#
计算机有哪些岗位值得去?
#
4324次浏览
37人参与
#
社会教会你的第一课
#
11949次浏览
159人参与
#
实习生的蛐蛐区
#
15703次浏览
125人参与
#
神州信息工作体验
#
14631次浏览
64人参与
#
应届生,你找到工作了吗
#
11149次浏览
94人参与
#
被AI治愈的瞬间
#
58211次浏览
620人参与
#
你找工作的时候用AI吗?
#
4975次浏览
39人参与
#
说说你知道的学历厂
#
9935次浏览
71人参与
#
哪一瞬间觉得自己长大了
#
2892次浏览
40人参与
#
你认为小厂实习有用吗?
#
4567次浏览
43人参与
#
歌尔求职进展汇总
#
56600次浏览
335人参与
#
面试尴尬现场
#
7282次浏览
43人参与
#
下班后的时间你怎么安排
#
2609次浏览
27人参与
#
简历当中有水分算不算造假?
#
13368次浏览
128人参与
#
秋招盘点:机械人值得去的企业
#
74734次浏览
672人参与
#
秋招想进国企该如何准备
#
72643次浏览
416人参与
#
三一集团提前批进度交流
#
25204次浏览
139人参与
#
双非应该如何逆袭?
#
182465次浏览
3173人参与
#
材料进Fab厂真的劝退吗?
#
45492次浏览
186人参与
#
毕业旅行去哪玩儿
#
11204次浏览
130人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务