华为面试题(8分钟写出代码)

zhaofusun

回复 24# windy2335
不合适;;碱值扯淡




如果给你1, 2,3 ,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 的话永远不平衡

   

zhaofusun

《〈〈〈中国难道没有程序员了？？？？？！！！！！！！！！！！！！！！！〉〉
《〈〈〈中国难道没有程序员了？？？？？！！！！！！！！！！！！！！！！〉〉
《〈〈〈中国难道没有程序员了？？？？？！！！！！！！！！！！！！！！！〉〉
《〈〈〈中国难道没有程序员了？？？？？！！！！！！！！！！！！！！！！〉〉吗？！


                       看来我是不能再低调了

还是我来讲讲吧

1:     首先将两个数组合并并排序,,,由大到小..
a[n] ; b[n]   -----> union[2n];

2; 清空a , b;并定义 变量addtoa; addtob;  diffe_ab;//diffe_ab是addtoa;addtob; 之差，

3: 暂且把union[0]---放addtoa-〉a[0]
         union[1] --->放addtob-〉b[0]
判断diffe_ab = addtoa -addtob//diffe_ab 可是个关键因素阿      问题的突破点都在这里，，，，//每一步具体算的时候还得分正负讨论。
diffe_ab 〉union[2n]-1]；
next cycle
addtoa-〉union[2n]-1]}/////最大程度的减小差距 每次都如此直到第n次循环
addtob-〉union[2]       }////


因为每次循环以后数组a[n]， b[n]，差距最小，最后一次亦是如此

如是此题得解；；；；

lovai

回复 431# vbs100

类似如下解法的：首先随机划分出两个子集，然后交换能使得和差降低(最多)的两个元素，直到找不到能降低的。
这是典型的爬山法，需要考虑有没有可能极值不是最值的情况。

当a和b长度不一样时，极值可能不是最值，如极值局面{1, 101, 50}和{70, 80}，这时需要一次性选择并交换两对元素才能达到最优解delta=0。
当a和b长度一样时[本题]，极值仍可能不是最值，不过得由于存在对称解，这种情况只可能出现在N>3的情况，如{2 , 3, 101, 50}和{0 , 4, 80, 70}，这时也需要一次性选择并交换两对元素才能达到最优解delta=0(sum(a)=155)。而上述算法的输出是sum(A)=156 sum(B)=154 sum(A)-sum(B)=2，显然是陷入局部极小值了。

下面给出“低效”但正确的DP解法：
抽象为问题：集合S划分为大小为n和n-|S|的两个子集，使得子集和之差最小。
DP：f(w, i)：到i为止，和为w的所有子集的长度的列表，
Ans = minw{abs(sum(S)/2 – w) | n in f(w, |S|)}
最坏复杂度O(W*|S|*|S|)

vbs100

回复 443# lovai


    你说的错误我看懂了，这样看来我那个确实是错误的解法。你说的算法没看懂，回去我研究下，谢谢指正，学习了

grassofsky

回复 442# zhaofusun


    没看明白，希望能把回复的内容整理下，谢谢。


    原谅我的低俗～～～～～～～～～～～

zhangtongjian

同求  这个题有意思

好吃的terry

8分钟解出来，纠结了8年还没答案，哎..

caihanwu8888

这是背包问题啊


   

路上风声

同意楼上的，这是背包问题的一种。八分钟能想到思路，但是我本人很难写出代码。
不过背包解法的思路不是很清晰，写另外一个思路供参考。
1.将a,b数组中的元素合并，按从大到小的顺序存储在一个线性链表c中;
2.设置标志变量flag,初始值为0;
3.在链表中从前往后每相邻两个元素做差值运算，找出差值最小的两个元素（当只有两个元素时，就取两个元素）.当flag==0的时候，比较的较大值放a,较小值放b,flag置1;当flag==1的时候,比较的较小值放a,较大值放b，flag置0.并在线性链表c中删除这两个元素.
4.重复步骤三直至链表所有元素取完，链表为空.
主要原因就是我每一步插入都保证了插入到a和b的两个元素差值最小，然后交叉的话，正好可以最大程度上的相互抵消，也算是背包思想了。

dnd371

难度大， 不过不考虑效率， 可以先整体排序， 然后再平均分到两个数组。   然后根据0-n对等比较，再排！