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

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,])