【華為公司Python面試題】，要求10分鐘寫出代碼。。。

天魔封神霸

有兩個序列a,b，大小都為n,序列元素的值任意整形數(shù)，無序；
要求：通過交換a,b中的元素，使[序列a元素的和]與[序列b元素的和]之間的差最小。


附帶一下我們的組織：
游戲開發(fā)-2群：Python（78676826）,主要討論:
桌面：WxWidget、TK、GTK、QT
游戲：pyOGRE、pyGame、"python.h"
Web：Zope、Django
網(wǎng)絡(luò):Twisted
只要心中有夢就可以與我們?yōu)槲椋�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 發(fā)表
有兩個序列a,b，大小都為n,序列元素的值任意整形數(shù)，無序；
要求：通過交換a,b中的元素，使[序列a元素的和]與[序列b元素的和]之間的差最小。

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

題面描述中：“整形數(shù)”是什么數(shù)？正整數(shù)、整數(shù)還是什么其它的數(shù)？
如果是正整數(shù)，想到的一個算法描述如下：
1 將a、b序列中的元素合并到一個長度為2n的list中并排序，假定此list名稱為c；
3 創(chuàng)建兩個空list分別命名為x，y
2 構(gòu)建一個函數(shù)假設(shè)名稱為add2list，該函數(shù)的作用是將兩個正整數(shù)添加到x，y中，保證這x，y的元素之和的差值的絕對值最��；
3 對c中的元素依次兩兩分組遞歸調(diào)用前面的函數(shù)add2list
4 最后得到的x，y即為所求之結(jié)果

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

天魔封神霸

整形數(shù)，我沒說清楚，就是指 整數(shù)

ruiqingzheng

比如 [1..100]  這樣的一個list
切成兩個LIST 并讓兩個list的和之間的差的絕對值最小
不就是[1..25] [100..76] 組成一個list
另外的[26..75] 組成一個list
這兩個LIST的元素和的差為0 當(dāng)然是絕對值最小的了

所以  只用把兩個LIST 排序成一個LIST后切片    就可以得到這樣的兩個LIST ， 對吧？

iamkey9

最小怎么定義，這個是問題，0不是最小。

guijia8427

10分鐘？ 有難度哦

weizhe86

ruiqingzheng

發(fā)表于 2009-6-28 17:20             比如 [1..100]  這樣的一個list 切成兩個LIST 并讓兩個list的和之間的差的絕對值最小 不就是[1..25] [100..76] 組成一個list 另外的[26..75] 組成一個list 這兩個LIST的元素和的差為0 當(dāng)然是絕對值最小的了 所以  只用把兩個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
您的方案顯然是前者。