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

初识orcl

顶起来，小伙伴们加油

xiaot7151

数学上的解法是 把两个序列 合并到一起 ，然后任意取N个，这N个的和减去剩下N个和的绝对值存入一个数组。共有 C2N(N) 种取法，所以结果数组长度是 2N!/N!， 然后取这个数组里面最小的正整数··

Python代码如何实现就不太清楚了··

xiaot7151

继续补充 -每一次取都要把相应的取出N个数再次存入一个数组（这样可以在再后计算出最小差值后能返回到对应的N个数）。感觉这程序性能跑起来会比较有问题，如果N比较大的话。。回复 92# xiaot7151


   

freeterman

回复 1# 天魔封神霸


#!/usr/bin/env python
a = [3, 8, 11, 8, 234]
b = [1, 2, 7, -21, 567]
x = y = 0
minSum = abs(sum(a)) - abs(sum(b))
while x < len(a):
    while y < len(b):
        a[x], b[y] = b[y], a[x]
        temp = abs(abs(sum(a)) - abs(sum(b)))
        if minSum < temp:
            a[x], b[y] = b[y], a[x]
        else:
            minSum = temp
        y = y + 1
    x = x + 1
    y = 0
print minSum

freeterman

使[序列a元素的和]与[序列b元素的和]之间的差最小
回复 82# xinxinhao


   

zengbo1019

这样可以么

def exchange(list1, list2):
   
    for i in range(len(list1)):
        for j in range(len(list2)):
            
            dvalue1=abs(sum(list1)-sum(list2))
            
            temp1 = list1[i]
            temp2 = list2[j]
            
            sum1 = sum(list1) + temp2 - temp1
            sum2 = sum(list2) + temp1 - temp2
            
            dvalue2=abs(sum1-sum2)
            if dvalue2 < dvalue1:
                list1[i] = temp2
                list2[j] = temp1

    print list1,sum(list1)
    print list2,sum(list2)
   
if __name__=="__main__":

    list1 = [10001,10000,100]
    list2 = [90,50,1]
    exchange(list1, list2)

[1, 10001, 100] 10102
[10000, 90, 50] 10140

hejekele

1. def change(alist=[], blist=[]):
   
2.     asum = sum(alist)
   
3.     bsum = sum(blist)
   
4. 
   
5.     if asum == bsum:
   
6.         return alist, blist
   
7. 
   
8.     avg = (asum + bsum)/2
   
9. 
   
10.     alist.sort()
    
11.     alist.reverse()
    
12.     blist.sort()
    
13. 
    
14. 
    
15.     alen = len(alist)
    
16.     blen = len(blist)
    
17. 
    
18.     delta = abs(avg - asum)
    
19. 
    
20.     for i in xrange(alen):
    
21.         for j in xrange(blen):
    
22.             tmp = alist[i] - blist[j]
    
23.             if tmp <= 0:
    
24.                 break
    
25.             elif tmp <= delta:
    
26.                 alist[i], blist[j] =  blist[j], alist[i]
    
27.                 return change(alist, blist)
    
28.     return alist, blist
    
29. 
    
30. 
    
31. def call_change(alist=[], blist=[]):
    
32.     asum = sum(alist)
    
33.     bsum = sum(blist)
    
34.     if asum < bsum:
    
35.         a,b = change(blist, alist)
    
36.         return b, a
    
37.     else:
    
38.         return change(alist, blist)

复制代码

inpool

思路：
合并两个列表，排序，然后按顺序从后往前每次取两个元素a, b，则a >= b
将取出来的数按a-b的值b进行分组
将分组按a-b的值排序然后合并，得到一个长为n的列表listab = [(a1,b1), (a2,b2), (a3,b3), ..., (an,bn)]
可证(listab[0] - listab[1]) >= (listab[i-1][0] - listab[i-1][1])  (0<= i < n)
定义两个空序列lista, listb
然后按从后往前的顺序取出listab的值并根据sum(lista)-sum(listb)的值，将ai,bi压入数组lista或listb
压入第一个时，abs(sum(lista) - sum(listb))最大，然后逐渐减小。
这个算法简单，实现也简单，思考5分钟，代码3-5分钟。

1. def min_sub_of_sum(lista, listb):
   
2.     listab = lista + listb
   
3.     listab.sort()
   
4.     tmp = {}
   
5.     while listab:
   
6.         a = listab.pop()
   
7.         b = listab.pop()
   
8.         tmp.setdefault(a-b, []).append((a, b))
   
9.     subs = tmp.keys()
   
10.     subs.sort()
    
11.     for sub in subs:
    
12.         listab.extend(tmp[sub])
    
13.     lista, listb = [], []
    
14.     # sub == sum(lista) - sum(listb)
    
15.     sub = 0
    
16.     while listab:
    
17.         if sub < 0:
    
18.             a, b = listab.pop()
    
19.         else:
    
20.             b, a = listab.pop()
    
21. 
    
22.         lista.append(a)
    
23.         listb.append(b)
    
24.         sub += (a - b)
    
25.     return lista, listb
    
26. 
    
27. 
    
28. if __name__ == '__main__':
    
29.     lista = range(100)
    
30.     listb = [i^11 for i in lista]
    
31.     a, b = min_sub_of_sum(lista, listb)
    
32.     print a
    
33.     print b
    
34.     print sum(a) - sum(b)

复制代码

turtle264

1. 两个列表合成一个大的，并且求所有数的和除以2，假定是M
2.经过第一步，这个问题变成了0-1背包问题，背包容量是M

vity

bskay 发表于 2012-08-29 11:35
伪动态规划的，

#动态规划问题

问题就是在数组a[n]中查找m个数据数据之和为指定数据取整（sum / 2），如果能找到，就结束，如果不能就找  [sum / 2] - 1，逐渐找下去。
至于优化的事情可以慢慢考虑。