【华为公司Python面试题】，要求10分钟写出代码。。。

天魔封神霸

有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。


附带一下我们的组织：
游戏开发-2群：Python（78676826）,主要讨论:
桌面：WxWidget、TK、GTK、QT
游戏：pyOGRE、pyGame、"python.h"
Web：Zope、Django
网络:Twisted
只要心中有梦就可以与我们为伍！Game Developer欢迎志同道合的朋友加入。

[ 本帖最后由 天魔封神霸 于 2009-6-26 14:41 编辑 ]

bawbaw

def look(a, max = 0): &nbsp;&nbsp;&nbsp;&nbsp;a.sort() &nbsp;&nbsp;&nbsp;&nbsp;while 1: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if len(a) == 0:return None &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;val = a.pop() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if val <= max:return val def ab(a , b): &nbsp;&nbsp;&nbsp;&nbsp;a.extend(b) &nbsp;&nbsp;&nbsp;&nbsp;sum = reduce(lambda x,y:x+y, a) &nbsp;&nbsp;&nbsp;&nbsp;arvg = sum / 2.0 &nbsp;&nbsp;&nbsp;&nbsp;rs1 = [] &nbsp;&nbsp;&nbsp;&nbsp;def qq(arvg, pick = None): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if pick is None: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pick = a.pop() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a.remove(pick) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rs1.append(pick) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arvg -= pick &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pick = look(a[:], max = arvg) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if pick is not None:qq(arvg, pick) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;qq(arvg) &nbsp;&nbsp;&nbsp;&nbsp;print rs1, a ab([1,2,5,3],[6,7,8,9,10])

[ 本帖最后由 bawbaw 于 2009-6-27 10:44 编辑 ]

broader

原帖由 天魔封神霸 于 2009-6-26 14:13 发表
有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。

http://wiki.services.openoffice.org/w/images/7/7e/Python_po ...

题面描述中：“整形数”是什么数？正整数、整数还是什么其它的数？
如果是正整数，想到的一个算法描述如下：
1 将a、b序列中的元素合并到一个长度为2n的list中并排序，假定此list名称为c；
3 创建两个空list分别命名为x，y
2 构建一个函数假设名称为add2list，该函数的作用是将两个正整数添加到x，y中，保证这x，y的元素之和的差值的绝对值最小；
3 对c中的元素依次两两分组递归调用前面的函数add2list
4 最后得到的x，y即为所求之结果

[ 本帖最后由 broader 于 2009-6-28 11:32 编辑 ]

天魔封神霸

整形数，我没说清楚，就是指 整数

ruiqingzheng

比如 [1..100]  这样的一个list
切成两个LIST 并让两个list的和之间的差的绝对值最小
不就是[1..25] [100..76] 组成一个list
另外的[26..75] 组成一个list
这两个LIST的元素和的差为0 当然是绝对值最小的了

所以  只用把两个LIST 排序成一个LIST后切片    就可以得到这样的两个LIST ， 对吧？

iamkey9

最小怎么定义，这个是问题，0不是最小。

guijia8427

10分钟？ 有难度哦

weizhe86

ruiqingzheng

发表于 2009-6-28 17:20             比如 [1..100]  这样的一个list 切成两个LIST 并让两个list的和之间的差的绝对值最小 不就是[1..25] [100..76] 组成一个list 另外的[26..75] 组成一个list 这两个LIST的元素和的差为0 当然是绝对值最小的了 所以  只用把两个LIST 排序成一个LIST后切片    就可以得到这样的两个LIST ， 对吧？

肯定不对喽[1,2,3,4,5,6,700,800],如何

weizhe86

也不对
S=[10001,10000,100,90,50,1]
如何
是a=[10001,90,50]
   b=[10000,100,1]
差为40
还是a=[10001,100,1]
      b=[10000,90,50]
差为38
您的方案显然是前者。