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

songjun54cm

回復(fù) 3# broader


    +1

http80

感覺好難的樣子

Hadron74

回復(fù) 3# broader

這個算法有問題，每兩個絕對值最小，不一定是總和最小。正確解法見我從《編程之美》學(xué)的算法。見帖子：
    http://72891.cn/thread-3770708-1-1.html

Hadron74

回復(fù) 70# new_ray

如果不遍歷所有交換是不可能到最優(yōu)的。看我上一個帖子。

但是處理所有的交換，原則上解決了，問題是你如何遍歷所有的交換，其算法復(fù)雜程度如何？請給出程序。

這個一個典型的最優(yōu)化問題，必須遍歷所有解空間。
如果不考慮問題的整數(shù)性，其算法復(fù)雜度最好的可能是按我寫的0-1背包程序，請參考我的程序。
當(dāng)然如果有更快的算法，我也希望向你學(xué)習(xí)。

如果是整數(shù)，動態(tài)規(guī)劃算法的復(fù)雜性好得多。


   

Hadron74

回復(fù) 71# songjun54cm

那是錯誤的方法。
   

webdna

就華為兩個字，引無數(shù)人看這個帖

kangxuechao

本人新建了一個500 的python QQ 群， 群號：　 248814126，　 歡迎加入�。�！

dylan_yiu

xxxxxxxxxxxxx

nheddd113

def changelist(aList,bList):
        cList=[]
        cList=aList + bList
        del aList,bList
        aList=[]
        bList=[]
        cList.sort()
        count=0
        for i in cList:
                count+=1
                if count % 2 ==0:
                        bList.append(i)
                        count+=1
                        if len(bList)-len(aList)>=1:
                                count+=1
                else:
                        aList.append(i)
        return(aList,bList)

這樣不知道算不算是

Hadron74

回復(fù) 79# nheddd113

你這個程序的算法有問題。不能保證最優(yōu)化條件。詳細(xì)請看我以前的帖子。