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

d_bsky

按照我的思想，就是先合并两个序列a跟b，得到c，然后排序c，再分割c，左右端同时取值，一次放d，一次放e，最后得到de两个list，这个应该就是差值最小的了吧

qinscx

按照我的思想，就是先合并两个序列a跟b，得到c，然后排序c，再分割c，左右端同时取值，一次放d，一次放e，最后得到de两个list，这个应该就是差值最小的了吧

楼上的思路和我的一样，另一种等同的做法是：合并之后排序，按奇偶分割成两个序列即为所求。
理由：合并排序后，针对第一个元素，试想序列里元素，谁和他的差距最小？当然是第二个。这样，一二元素分离。再来考虑第三个元素，同样的道理，三四元素分开。这样，最后的结果是：元素最小差距1 + 元素最小差距2 + 。。。 = 两个序列的最小差距。

dknlnl

每个序列之和越靠近总和的1/2,那么是两个序列这差越小.
考虑反贪心算法.
将两个序列合并,排序,记为sortList.
设x,y为结果序列.
x依次从sortList中取数,从最小的开始取.直到sum(x)>=sum(sortList)/2.

假设x从sortList取出一个数k反,sum(x)从小于sum(sortList)/2变为大于或等于sum(sortList)/2,根据以下条件判断k是否放入x:
如果将k加入x后,x的和与y(y就是sortList减于x啦)之差小于将k不放入x,那么k放入x.
以上是不要求结果序列等长的.

CMAX

python的，纯实现，没考虑其他的

1. #! /usr/bin/env python
   
2. 
   
3. import input
   
4. a = input.a
   
5. b = input.b
   
6. 
   
7. l = len(a)
   
8. 
   
9. ar = list()
   
10. br = list()
    
11. 
    
12. sl = sorted(a + b, reverse = True)
    
13. 
    
14. diff = 0
    
15. 
    
16. sign = True
    
17. 
    
18. for i in xrange(0, l):
    
19.     for j in range(2*l-1, i+1, -1):
    
20.         d1 = sl[i] - sl[j-1]
    
21.         d2 = sl[i] - sl[j]
    
22.         if diff - d1 >= 0 and diff - d2 < 0:
    
23.             r1, r2 = i, j
    
24.             break
    
25.     else:
    
26.         r1, r2 = i, i+1
    
27. 
    
28.     if sign:
    
29.         ar.append(sl[r1])
    
30.         br.append(sl[r2])
    
31.     else:
    
32.         ar.append(sl[r2])
    
33.         br.append(sl[r1])
    
34.     sign = not sign
    
35. 
    
36. print ar, sum(ar)
    
37. print br, sum(br)

复制代码

bskay

伪动态规划的，

#动态规划问题
#从M个数里面找出N个，让他们的和尽量接近 P
class NumList:
        def __init__(self):
                self.reset()
                pass
        def reset(self):
                self.vA = []
                self.vB = []
                self.nSumA = reduce(lambda x, y: x+y, self.vA, 0)
                self.nSumB = reduce(lambda x, y: x+y, self.vB, 0)
                pass
        #开始规划
        def addonce(self,nA,nB):
                #
                if self.nSumA > self.nSumB:
                        self.vA.append(nA)
                        self.nSumA += nA
                        self.vB.append(nB)
                        self.nSumB += nB
                        pass
                else:
                        self.vA.append(nB)
                        self.nSumA += nB
                        self.vB.append(nA)
                        self.nSumB += nA
                        pass
                #try
                while self.ajduest():pass
                return
        def ajduest(self):
                if self.nSumA>self.nSumB:
                        nA,nB = self.findd(self.vA,self.vB,(self.nSumA-self.nSumB)/2)
                        if nA is None or nB is None:
                                return False
                        pass
                elif self.nSumA<self.nSumB:
                        nB,nA = self.findd(self.vB,self.vA,(self.nSumB-self.nSumA)/2)
                        if nA is None or nB is None:
                                return False
                        pass
                else:
                        return False
                self.nSumA += self.vB[nB] - self.vA[nA]
                self.nSumB += self.vA[nA] - self.vB[nB]
                print 'r1(vA,vB) =',self.vA,self.vB
                self.vA[nA],self.vB[nB] = self.vB[nB],self.vA[nA]
                self.vA.sort()
                self.vB.sort()
                print 'r2(vA,vB) =',self.vA,self.vB
                return True
        #
        '''
        输入:
                I1. A中所有元素的和大于B中所有元素的和
                I2. A,B中的元素从小到大排列
                I3. 最大期望的调整值
        输出:
                O1. 在A,B中分别找出一个位置(a,b)
                O2. 交换调整A,B中对应的元素后，依然满足I1
                O3. 没有找到满足条件一个位置，返回None
        '''
        def findd(self,vA,vB,nDlt):
                print 'findd',vA,vB,nDlt
                nA,nB = None,None
                nXXX = nDlt
                for a in xrange(len(vA)-1,-1,-1):
                        for b in xrange(len(vB)):
                                if vB >= vA[a]:
                                        break
                                nDiff = vA[a]-vB #调整的差值
                                if nDiff > nDlt:
                                        continue
                                if nDlt-nDiff >= nXXX:
                                        continue
                                if nDiff == nDlt:
                                        print 'haha findd at ... ',a,b
                                        return a,b
                                #print '(vB,vA[a]) =',(vB,vA[a]),'(a,b)',(a,b), 'r =',nDiff
                                nXXX = nDlt-nDiff
                                nA,nB = a,b
                                continue
                        continue
                print 'findd at ... ',nA,nB
                return nA,nB
        def main(self,vA,vB):
                self.reset()
                vX = vA+vB
                vX.sort()
                while len(vX):
                        self.addonce(vX[0],vX[1])
                        del vX[:2]
                        continue
                print 'vA =>',self.vA
                print 'vB =>',self.vB
                return
        pass


self = NumList()
self.main([1,1,1,1],[2,2,2,2])
assert(self.vA == [1,1,2,2] and self.vA==self.vB)

self.main([1,1,1,1],[1,1,1,1])
assert(self.vA == [1,1,1,1] == self.vB)

self.main([1,1,2,3,5,10,], [20,30,30,50,50,100,])

Hadron74

看了前人的解法，怎么把问题搞得那么复杂。这个题目是十分钟的题目，肯定没有那么多代码的。

我的思路是用穷举法，把所有的a+b的total的序列的排列穷举，得到所有可能的划分，对其差值计算最小值。

下面是程序，

1. def minus(total):
   
2.         n = len(total)/2
   
3.         a = total[:n]
   
4.         b = total[n:]
   
5.         return abs(sum(a)-sum(b)),a,b
   
6. 
   
7. def func(total,k):
   
8.         mi,am,bm = minus(total)
   
9.         global minusN,an,bn
   
10.         if mi < minusN:
    
11.                 minusN = mi
    
12.                 an,bn = am,bm
    
13. 
    
14.         for i in range(k,len(total)):
    
15.                 total[k],total[i] = total[i],total[k]
    
16.                 func(total,k+1)
    
17.                 total[k],total[i] = total[i],total[k]
    
18. 
    
19. a=[1,2,3,4]
    
20. b=[6,7,8,9]
    
21. an,bn = a[:],b[:]
    
22. total = a+b
    
23. minusN,am,bm=minus(total)
    
24. func(total,0)
    
25. print "a:",an
    
26. print "b:",bn
    
27. print "minus:",minusN
    
28. 
    

复制代码

这里的算法用到了穷举一个序列的全排列的算法，见
http://www.cnblogs.com/height/archive/2012/08/14/2638802.html

这个算法的复杂性太过要O((2n)!),我的写法中也有冗余的部分，有时间来改正。
这里抛砖引玉，也许有更短小的写法。肯定有更快的算法，我正在寻找中。

Hadron74

回复 66# Hadron74


    现在我有了一个更好的方法，用0-1背包问题来解决这个问题。思路是，给一个总和长的select数组，记录a/b的状态，True表示在a中，False表示在b中。
用递归遍历所有选取n个元素在a中的可能，就遍历了所有可能的交换。这个算法的复杂度小于O（2^(2n)).

其算法可以参考http://www.cnblogs.com/Myhsg/archive/2009/08/29/1556460.html

下面是代码

1. def  minus():
   
2.     global total,select,number
   
3.     a = [ total[i] for i in range(number) if select[i] ]
   
4.     b = [ total[i] for i in range(number) if not select[i] ]
   
5.     return abs(sum(a) - sum(b)),a,b
   
6. 
   
7. def func(sumN,k):
   
8.     global select,number,halfnumber,minSN,an,bn
   
9.     if k==number:
   
10.         return
    
11.     if sumN == halfnumber:
    
12.         mi,am,bm = minus()
    
13.         if mi< minSN:
    
14.             minSN = mi
    
15.             an,bn = am,bm
    
16.         return
    
17.     select[k] = True
    
18.     func(sumN+1,k+1)
    
19.     select[k] = False
    
20.     func(sumN,k+1)
    
21.    
    
22. if __name__ == '__main__':
    
23.     a = [1,2,3,4]
    
24.     b = [6,7,8,9]
    
25.     total = a + b
    
26.     an, bn = a[:], b[:]
    
27.     minSN = abs(sum(a)-sum(b))
    
28.     number = len(total)
    
29.     halfnumber = number/2
    
30. 
    
31.     select = map(lambda x: False,total)
    
32. 
    
33.     func(0,0)
    
34. 
    
35.     print minSN
    
36.     print an
    
37.     print bn
    

复制代码

结果：

1. 0
   
2. [1, 4, 7, 8]
   
3. [2, 3, 6, 9]

复制代码

new_ray

我觉得就是一个排序问题吧。
比如：序列a1,a2,a3,...an
         序列b1,b2,b3,...bn
         假设存在一个序列c,c的元素为a1,a2,a3...an,b1,b2,b3...bn.对序列c排序后得到新的顺序,c1,c2,c3..c2n.则得到序列a结果为c1,c3,c5...c2n-1,序列b为c2,c4,c6...c2n.
而排序可以只比较就可以了。

Hadron74

回复 68# new_ray

这个问题没有那么简单，详细请看我们最新的帖子。《编程之美》给出了正整数的动态规划算法。我写了代码。

http://bbs.chinaunix.net/forum.p ... age%3D1#pid22286448

   

new_ray

呵呵，写完后就发现自己写错了，后来又有了一种想法。仍然是先排序，得到c1,c2,c3..c2n。然后将cn+1,cn+2...c2n数据与前面的进行交换。每次选取的值都是要是差值最小(>0)的数对。
1.若使得cn+1,cn+2...c2n与c1,c2...cn的差值变大时就结束。
2.若cn+1,cn+2...c2n与c1,c2...cn的差值为负数时，如果负数的绝对值变小时仍然交换。
3.再将c1,c2...cn与与后面的进行交换。每次选取的值都是要是也差值最小(>0)的数对。
4.处理与1,2步骤类似。

呵呵，这样应该是可以了。