腾讯笔试第三题思路哪错了&第四题为什么topk超时

第三题把一个数组分成两个数组a1,a2,要求两个数组长度差不超过1并且数组和的差sum(a1)-sum(a2)最小。
我的想法是原数组排序后从最后大的开始分配,a1的和小就分配到a1,a2和小就a2。直到分配完或者某一个数组的长度到达原数组长度的一半,把剩下的都分到另一个数组里去(原数组长度奇数的话,留下一个最小值分给和小的)。然后一个case也没过⊙▽⊙,自己没测试出会出错的case,不知道哪里错了。

第四题是类似于topk堆排,一次次找最小,如果减去该减的值小于零不符合条件就继续找下一个最小。为啥只过了0.7?有更好的方法吗?

#腾讯#
全部评论
我想到反例了 就比如说这样做下来a1比a2和小2,但a1中恰好有个7然后a2里有个8,这俩虽然当初因缘际会放进了现在的位置,但现在一交换就可以让数组和的差更小。
点赞 回复 分享
发布于 2019-09-20 22:41
第四题没那么复杂 #include <bits/stdc++.h> int main(int argc, const char* argv[]) {     std::ios::sync_with_stdio(false);     size_t N, K;     std::cin >> N >> K;     std::vector<size_t> val(N);     for(size_t i = 0; i < N; i++) {         std::cin >> val[i];     }     std::sort(val.begin(), val.end());     size_t idx = 0;     size_t previous = 0;     for(size_t i = 0; i < K; i++) {         if(idx == N) {             std::cout << "0\n";             continue;         }         std::cout << val[idx] - previous << std::endl;         previous = val[idx];         for(; idx < N; idx++) {             if(val[idx] != previous) {                 break;             }         }     }     return EXIT_SUCCESS; } 第三题举反例,最大数远大于其他数,然后最佳解应该是【最大数+较小的一半数】/【除了最大外的较大的一半数】
点赞 回复 分享
发布于 2019-09-20 22:18
第四题,感觉差不多,我是存一个差值s,然后每次pop一个如果等于差值就扔掉,不然的话就打印同时更新差值,这都不用排序
点赞 回复 分享
发布于 2019-09-20 22:51
第三题你应该不能这么做,你想想,这题除了限定个数,是不是零一背包。。。贪心是不可能对的,不然就没必要用动规做零一背包了
点赞 回复 分享
发布于 2019-09-20 22:37
大佬1、2都A了吗
点赞 回复 分享
发布于 2019-09-20 22:34
第四题AC过了 不需要一直找0 就是找差值的过程 import java.util.Arrays; import java.util.Scanner; public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int m = sc.nextInt();         int[] a = new int[n];         for (int i = 0; i < n; i++) {             a[i] = sc.nextInt();         }         int[] c = getResult(m,a);         for (int i = 0; i < m; i++) {             System.out.println(c[i]);         }     }     public static int[] getResult(int k, int[] a){         int[] b = new int[k];         if (a.length==0){             return b;         }         Arrays.sort(a);         b[0] = a[0];         int x=1;         for (int i = 1; i < a.length; i++) {             if (a[i] != a[i-1]&&x<k) b[x++] = a[i]-a[i-1];         }         return b;     } }
点赞 回复 分享
发布于 2019-09-20 22:18
第3题贪心肯定不行的,我也想不出怎么做😂 第4题我用堆排AC了(用的是STL里面的set)
点赞 回复 分享
发布于 2019-09-20 22:16
第四题是因为代码太耗时吗?我的太暴力了 所以运行不完所有的case 只AC了0.6😶️
点赞 回复 分享
发布于 2019-09-20 22:15
第四题,实际上就是排序后求差分 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() {     int n, k;     cin >> n >> k;     vector<int> arr(n);     for(int i = 0; i < n; i++) cin >> arr[i];     sort(arr.begin(), arr.end());     int j = 0;     cout << arr[j] << endl;     j++;     int i = 1;     while(j < n){         if(arr[j-1] == arr[j]){             j++;             continue;         }         else{             cout << arr[j] - arr[j-1] << endl;             j++;             i++;             if(i >= k) break;         }     }     for(j = i; j < k; j++) cout << 0 << endl;     return 0; }
点赞 回复 分享
发布于 2019-09-20 22:14
。。。。你这个
点赞 回复 分享
发布于 2019-09-20 22:14
(后端题,第三题是员工有战斗力,游戏分组,分成人数差不多战斗力也差不多的两组玩游戏。第四题是不断找不为0的最小值输出然后剩下的减掉这个最小值)
点赞 回复 分享
发布于 2019-09-20 22:13
但是自己怎么会知道哪个case会出错呢
点赞 回复 分享
发布于 2019-09-20 22:13

相关推荐

公司&nbsp;HR&nbsp;打电话约面试时,特意强调:“我们招的是&nbsp;Java&nbsp;开发,最低本科,你大专学历……&nbsp;要不还是算了?”&nbsp;我正想挂电话,她又补了句:“不过老板说‘万一呢’,你过来试试吧。”面试室里,技术主管翻简历的手停在&nbsp;“学历:大专”&nbsp;那行,指节捏得发白。他把简历往桌上一墩,笔都弹起来了:“会写代码吗?别告诉我你就看过两天教程。”“会一点&nbsp;Java。”&nbsp;我指尖无意识敲着桌面,“比如&nbsp;public&nbsp;static&nbsp;void&nbsp;main,能写个入口方法。”主管手里的笔&nbsp;“啪”&nbsp;掉在地上。他弯腰捡笔时腰杆都在抖,抬头盯着我半天,突然扯开嗓子喊:“老板!快!快叫技术部所有人过来!有个会写&nbsp;main&nbsp;方法的!能启动程序的那种!”隔壁办公区的键盘声跟被掐断似的。老板踩着拖鞋冲进来,眼镜滑到鼻尖上,扒着门框喊:“真的假的?能写&nbsp;main&nbsp;方法?我们服务器上那堆代码,三个月没人能跑起来!”“不止,”&nbsp;我补充道,“还会用&nbsp;System.out.println&nbsp;(&quot;xxx&quot;),带换行的那种。”老板&nbsp;“嗷”&nbsp;一嗓子蹦起来,差点撞翻饮水机:“留!现在就签合同!月薪&nbsp;25k!住房补贴单独算!电脑给你配最新款&nbsp;Mac!”旁边刚端着茶杯进来的技术组长手一抖,茶水洒在衬衫上都没察觉:“能……&nbsp;能换行?我们之前打印日志都是手动敲&nbsp;\n,敲错一次就得改半天!”我没说的是,我还会定义&nbsp;int&nbsp;a=10;&nbsp;int&nbsp;b=20;&nbsp;然后算&nbsp;a+b——&nbsp;这底牌,得等转正再亮。刚坐到工位,运营部的大姐捧着笔记本凑过来,声音跟蚊子似的:“大佬,您说的&nbsp;main&nbsp;方法……&nbsp;是不是就是程序开头那行‘public&nbsp;static&nbsp;void……’?我之前总把&nbsp;static&nbsp;写成&nbsp;staitc,改到崩溃。”我点头的瞬间,余光瞥见好几个脑袋凑过来,有人掏出荧光笔在本子上划:“main&nbsp;方法&nbsp;=&nbsp;public&nbsp;static&nbsp;void&nbsp;main&nbsp;(String&nbsp;[]&nbsp;args),记死!”下午突然炸锅&nbsp;——&nbsp;甲方发了个紧急需求:“今晚必须跑通一个计算&nbsp;1&nbsp;到&nbsp;100&nbsp;总和的程序,我们自己写的跑一次崩一次。”&nbsp;整个技术部的人围着电脑挠头,屏幕上的代码东倒西歪,有个哥们居然在用&nbsp;for&nbsp;循环写&nbsp;i=i+1,还忘了初始化&nbsp;i。“我试试?”&nbsp;我拉过椅子。办公室突然静得能听见硬盘转。我打开&nbsp;Eclipse,先敲&nbsp;public&nbsp;class&nbsp;SumTest,回车时&nbsp;IDE&nbsp;自动补全了大括号,再写&nbsp;main&nbsp;方法,然后定义&nbsp;int&nbsp;sum=0;&nbsp;接着&nbsp;for&nbsp;(int&nbsp;i=1;i&lt;=100;i++){sum+=i;},最后&nbsp;System.out.println&nbsp;(&quot;总和:&quot;+sum);&nbsp;点击运行&nbsp;——&nbsp;控制台跳出&nbsp;“总和:5050”,连字体都透着工整。那个写&nbsp;i=i+1&nbsp;的哥们&nbsp;“嘶”&nbsp;地倒吸凉气,手机搜&nbsp;“Java&nbsp;for&nbsp;循环&nbsp;sum+=i&nbsp;是什么神仙操作”。产品经理抱着胳膊冷笑:“不就几行代码?我上我也行。”我没说话,随手按了&nbsp;Ctrl+D,刚才写的&nbsp;for&nbsp;循环自动复制了一行,改了个变量名就成了计算偶数和的逻辑。产品经理的脸噌地红透了,转身假装接电话,其实在偷偷搜&nbsp;“Eclipse&nbsp;Ctrl+D&nbsp;快捷键”。下班前,一直用&nbsp;Excel&nbsp;算数据总和的财务大姐攥着计算器过来,声音带着颤:“小老师,您这写个程序算总和的本事,在阿里腾讯不得拿&nbsp;50k?”我笑了笑,没告诉她&nbsp;——&nbsp;我其实还会用&nbsp;if&nbsp;(i%2==0)&nbsp;筛选偶数,甚至能写个带&nbsp;return&nbsp;的方法。这底牌,留着给明年涨薪用正好。
投递阿里巴巴等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

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