Python程序員面試分類模擬3

Python程序員面試分類模擬3簡答題1.

有20個數(shù)組，每個數(shù)組有500個元素，并且是有序排列好的，現(xiàn)在如何在這20*500個數(shù)中找出排名前500的數(shù)?正確答案：對于求topk的問題，最常用的（江南博哥）方法為堆排序方法。對于本題而言，假設數(shù)組降序排列，可以采用如下方法：

(1)首先建立大頂堆，堆的大小為數(shù)組的個數(shù)，即20，把每個數(shù)組最大的值(數(shù)組第一個值)存放到堆中。Python中heapq是小頂堆，通過對輸入和輸出的元素分別取相反數(shù)來實現(xiàn)大頂堆的功能。

(2)接著刪除堆頂元素，保存到另外一個大小為500的數(shù)組中，然后向大頂堆插入刪除的元素所在數(shù)組的下一個元素。

(3)重復第(1)、(2)個步驟，直到刪除個數(shù)為最大的k個數(shù)，這里為500。

為了在堆中取出一個數(shù)據(jù)后，能知道它是從哪個數(shù)組中取出的，從而可以從這個數(shù)組中取下一個值，可以設置一個數(shù)組，數(shù)組中帶入每個元素在原數(shù)組中的位置。為了便于理解，把題目進行簡化：三個數(shù)組，每個數(shù)組有5個元素且有序，找出排名前5的數(shù)。

importheapq

defgetTop(data):

rowSize=len(data)

columnSize=len(data[0])

result3=[None]*columnSize

#保持一個最小堆,這個堆存放來自20個數(shù)組的最小數(shù)

heap=[]

i=0

whilei＜rowSize:

arr=(None,None,None)#數(shù)組設置三個變量,分別為數(shù)值,數(shù)值來源的數(shù)組,數(shù)值在數(shù)組中的次序index

arr=(-data[i][0],i,0)

heapq.heappush(heap,arr)

i+=1

num=0

whilenum＜columnSize:

#刪除頂點元素

d=heapq.heappop(heap)

result3[num]=-d[0]

num+=1

if(num＞=columnSize):

break

#將value置為該數(shù)原數(shù)組里的下一個數(shù)

arr=(--data[d[1]][d[2]+1],d[1],d[2]+1)

heapq.heappush(heap,arr)

returnresult3

if__name__=="__main__":

data=[[29,17,14,2,1],[19,17,16,15,6],[30,25,20,14,5]]

printgetTop(data)

程序的運行結(jié)果為：

3029252019

通過把ROWS改成20，COLS改成50，并構(gòu)造相應的數(shù)組，就能實現(xiàn)題目的要求。對于升序排列的數(shù)組，實現(xiàn)方式類似，只不過是從數(shù)組的最后一個元素開始遍歷。[考點]如何找出排名前500的數(shù)

2.

給定一個數(shù)組，已知這個數(shù)組中有大量的重復的數(shù)字，如何對這個數(shù)組進行高效地排序?正確答案：如果使用常規(guī)的排序方法，雖然最好的排序算法的時間復雜度為O(NlOg2N)，但是使用常規(guī)排序算法顯然沒有用到數(shù)組中有大量重復數(shù)字這個特性。如何能使用這個特性呢?下面介紹兩種更加高效的算法。

方法一：AVL樹

這種方法的主要思路為：根據(jù)數(shù)組中的數(shù)構(gòu)建一個AVL樹，這里需要對AVL樹做適當?shù)臄U展，在結(jié)點中增加一個額外的數(shù)據(jù)域來記錄這個數(shù)字出現(xiàn)的次數(shù)，在AVL樹構(gòu)建完成后，可以對AVL樹進行中序遍歷，根據(jù)每個結(jié)點對應數(shù)字出現(xiàn)的次數(shù)，把遍歷結(jié)果放回到數(shù)組中就完成了排序，實現(xiàn)代碼如下：

#AVL樹的結(jié)點

classNode:

def__init__(self,data):

self.data=data

self.left=self.right=None

self.height=self.count=1

classSort:

#中序遍歷AVL樹,把遍歷結(jié)果放入到數(shù)組中

definorder(self,arr,root,index):

ifroot!=None:

#中序遍歷左子樹

index=self.inorder(arr,root.left,index)

#把root結(jié)點對應的數(shù)字根據(jù)出現(xiàn)的次數(shù)放入到數(shù)組中

i=0

whilei＜root.count:

arr[index]=root.data

index+=1

i+=1

#中序遍歷右子樹

index=self.inorder(arr,root.right,index)

returnindex

#得到樹的高度

defgetHeight(self,node):

ifnode==None:

return0

else:

returnnode.height

#把以y為根的子樹向右旋轉(zhuǎn)

defrightRotate(self,y):

x=y.left

T2=x.right

#旋轉(zhuǎn)

x.right=y

y.left=T2

y.height=max(self.getHeight(y.left),self.getHeight(y.right))+1

x.height=max(self.getHeight(x.left),self.getHeight(x.right))+1

#返回新的根結(jié)點

returnx

#把以x為根的子樹向右旋轉(zhuǎn)

defleftRotate(self,x):

y=x.right

T2=y.left

y.left=x

x.right=T2

x.height=max(self.getHeight(x.left),self.getHeight(x.right))+1

y.height=max(self.getHeight(y.left),self.getHeight(y.right))+1

#Returnnewroot

returny

#獲取樹的平衡因子

defgetBalance(self,N):

if(N==None):

return0

returnself.getHeight(N.left)-self.getHeight(N.right)

"""

如果data在AVL樹中不存在,則把data插入到AVL樹中,否則把這個結(jié)點對應的count加1即可

"""

definsert(self,root,data):

ifroot==None:

return(Node(data))

#data在樹中存在,把對應的結(jié)點的count加1

ifdata==root.data:

root.count+=1

returnroot

#在左子樹中繼續(xù)查找data是否存在

ifdata＜root.data:

root.left=self.insert(root.left,data)

#在右子樹中繼續(xù)查找data是否存在

else:

root.right=self.insert(root.right,data)

#插入新的結(jié)點后更新root結(jié)點的高度

root.height=max(self.getHeight(root.left),self.getHeight(root.right))+1

#獲取樹的平衡因子

balance=self.getBalance(root)

#如果樹不平衡,根據(jù)數(shù)據(jù)結(jié)構(gòu)中學過的四種情況進行調(diào)整

#LL型

ifbalance＞1anddata＜root.left.data:

returnself.rightRotate(root)

#RR型

elifbalance＜-1anddata>root.right.data:

returnself.leftRotate(root)

#LR型

elifbalance＞1anddata>root.left.data:

root.left=self.leftRotate(root.left)

returnself.rightRotate(root)

#RL型

elifbalance＜-1anddata＜root.right.data:

root.right=self.rightRotate(root.right)

returnself.leftRotate(root)

returnroot

#使用AVL樹實現(xiàn)排序

defsort(self,arr):

root=None#根結(jié)點

n=len(arr)

i=0

whilei＜n:

root=self.insert(root,arr[i])

i+=1

index=0

self.inorder(arr,root,index)

if__name__="__main__":

arr=[15,12,15,2,2,12,2,3,12,100,3,3]

s=Sort()

s.sort(arr)

whilei＜len(arr):

printarr[i],

i+=1

代碼運行結(jié)果為：

2223331212121515100

算法性能分析：

這種方法的時間復雜度為O(NLog2M)，其中，N為數(shù)組的大小，M為數(shù)組中不同數(shù)字的個數(shù)，空間復雜度為O(N)。

方法二：哈希法

這種方法的主要思路為創(chuàng)建一個哈希表，然后遍歷數(shù)組，把數(shù)組中的數(shù)字放入哈希表中，在遍歷的過程中，如果這個數(shù)在哈希表中存在，則直接把哈希表中這個key對應的value加1；如果這個數(shù)在哈希表中不存在，則直接把這個數(shù)添加到哈希表中，并且初始化這個key對應的value為1。實現(xiàn)代碼如下：

defsort(arr):

data_count=dict()

n=len(arr)

#把數(shù)組中的數(shù)放入map中

i=0

whilei＜n:

ifstr(arr[i])indata_count:

data_count[str(arr[i])]=data_count.get(str(arr[i]))+1

else:

data_count[str(arr[i])]=1

i+=1

index=0

forkey,valueindata_count.items():

i=value

whilei>0:

arr[index]=key

index+=1

i-=1

if__name__="__main__":

arr=[15,12,15,2,2,12,2,3,12,100,3,3]

sort(arr)

i=0

whilei＜len(arr):

printarr[i],

i+=1

算法性能分析：

這種方法的時間復雜度為O(N+MLog2M)，空間復雜度為O(M)。[考點]如何對有大量重復的數(shù)字的數(shù)組排序

3.

求出用1，2，5這三個數(shù)不同個數(shù)組合的和為100的組合個數(shù)。為了更好地理解題目的意思，下面給出幾組可能的組合：100個1，0個2和0個5，它們的和為100；50個1，25個2，0個5的和也是100；50個1，20個2，2個5的和也為100。正確答案：方法一：蠻力法

最簡單的方法就是對所有的組合進行嘗試，然后判斷組合的結(jié)果是否滿足和為100，這些組合有如下限制：1的個數(shù)最多為100個，2的個數(shù)最多為50個，5的個數(shù)最多為20個。實現(xiàn)思路為：遍歷所有可能的組合l的個數(shù)x(0＜=x＜=100)，2的個數(shù)y(0=＜y＜=50)，5的個數(shù)z(0＜=z＜=20)，判斷x+2y+5z是否等于100，如果相等，那么滿足條件，實現(xiàn)代碼如下：

defcombinationCount(n):

count=0

num1=n#1最多的個數(shù)

num2=n/2#2最多的個數(shù)

num5=n/5#5最多的個數(shù)

x=0

whilex＜==num1:

y=0

whiley＜=num2:

z=0

whilez＜=num5:

ifx+2*y+5*z==n:#滿足條件

count+=1

z+=1

y+=1

x+=1

returncount

if__name__=="__main__":

printcombinationCount(100)

程序的運行結(jié)果為：

541

算法性能分析：

這種方法循環(huán)的次數(shù)為101*51*21。

方法二：數(shù)字規(guī)律法

針對這種數(shù)學公式的運算，一般都可以通過找出運算的規(guī)律進而簡化運算的過程，對于本題而言，對x+2y+5z=100進行變換可以得到x+5z=100-2y。從這個表達式可以看出，x+5z是偶數(shù)且x+5z＜=100。因此，求滿足x+2y+5z=100組合的個數(shù)就可以轉(zhuǎn)換為求滿足“x+5z是偶數(shù)且x+5z＜=100”的個數(shù)?？梢酝ㄟ^對z的所有可能的取值(0＜=z＜=20)進行遍歷從而計算滿足條件的x的值。

當z=0時，x的取值為0，2，4，…，100(100以內(nèi)所有的偶數(shù))，個數(shù)為(100+2)/2

當z=1時，x的取值為1，3，5，…，95(95以內(nèi)所有的奇數(shù))，個數(shù)為(95+2)/2

當z=2時，x的取值為0，2，4，…，90(90以內(nèi)所有的偶數(shù))，個數(shù)為(90+2)/2

當z=3時，x的取值為1，3，5，…，85(85以內(nèi)所有的奇數(shù))，個數(shù)為(85+2)/2

當z-19時，x的取值為5，3，1(5以內(nèi)所有的奇數(shù))，個數(shù)為(5+2)/2

當z=20時，x的取值為0(0以內(nèi)所有的偶數(shù))，個數(shù)為(0+2)/2

根據(jù)這個思路，實現(xiàn)代碼如下：

defcombinationCount(n):

count=0

m=0

whilem＜=n:

count+=(m+2)/2

m+=5

returncount

算法性能分析：

這種方法循環(huán)的次數(shù)為21。[考點]如何組合1，2，5這三個數(shù)使其和為100

4.

給定一個數(shù)組a[N]，希望構(gòu)造一個新的數(shù)組b[N]，其中，b[i]=a[0]*a[1]*…*a[N-1]/a[i]。在構(gòu)造數(shù)組的過程中，有如下幾點要求：

(a)不允許使用除法；

(b)要求O(1)空間復雜度和O(N)時間復雜度；

(c)除遍歷計數(shù)器與a[N]、b[N]外，不可以使用新的變量(包括棧臨時變量、堆空間和全局靜態(tài)變量等)；

(d)請用程序?qū)崿F(xiàn)并簡單描述。正確答案：如果沒有時間復雜度與空間復雜度的要求，算法將非常簡單，首先遍歷一遍數(shù)組a，計算數(shù)組a中所有元素的乘積，并保存到一個臨時變量tmp中，然后再遍歷一遍數(shù)組a并給數(shù)組賦值：b[i]=tmp/a[i]，但是這種方法使用了一個臨時變量，因此，不滿足題目的要求，下面介紹另外一種方法。

在計算b[i]的時候，只要將數(shù)組a中除了a[i]以外的所有值相乘即可。這種方法的主要思路為：首先遍歷一遍數(shù)組a，在遍歷的過程中對數(shù)組b進行賦值：b[i]=a[i-1]*b[i-1]，這樣經(jīng)過一次遍歷后，數(shù)組b的值為b[i]=a[0]*a[1]*…*a[i-1]。此時只需要將數(shù)組中的值b[i]再乘以a[i+1]*a[i+2]*…a[N-1]，實現(xiàn)方法為逆向遍歷數(shù)組a，把數(shù)組后半段值的乘積記錄到b[0]中，通過b[i]與b[0]的乘積就可以得到滿足題目要求的b[i]，具體而言，執(zhí)行b[i]=b[i]*b[0](首先執(zhí)行的目的是為了保證在執(zhí)行下面一個計算的時候，b[0]中不包含與b[i]的乘積)，接著記錄數(shù)組后半段的乘積到b[0]中：b[0]*=b[0]*a[i]。

實現(xiàn)代碼如下：

defcalculate(a,b):

b[0]=1

N=len(a)

i=1

whilei＜N:

b[i]=b[i-1]*a[i-1]#正向計算乘積

i+=1

b[0]=a[N-1]

i=N-2

whilei＞=1:

b[i]*=b[0]

b[0]*=a[i]#逆向計算乘積

i-=1

if__name__=="__main__":

a=[1,2,3,4,5,6,7,8,9,10]

b=[None]*len(a)

calculate(a,b)

i=0

whilei＜len(b):

printb[i],

i+=1

程序的運行結(jié)果為：

362880018144001209600907200725760604800518400453600403200362880[考點]如何按要求構(gòu)造新的數(shù)組

5.

數(shù)組中有N+2個數(shù)，其中，N個數(shù)出現(xiàn)了偶數(shù)次，2個數(shù)出現(xiàn)了奇數(shù)次(這兩個數(shù)不相等)，請用O(1)的空間復雜度，找出這兩個數(shù)。注意：不需要知道具體位置，只需要找出這兩個數(shù)。正確答案：方法一：字典法

對于本題而言，定義一個字典，把數(shù)組元素的值作為key，遍歷整個數(shù)組，如果key值不存在，則將value設為1，如果key值已經(jīng)存在，則翻轉(zhuǎn)該值(如果為0，則翻轉(zhuǎn)為1；如果為1，則翻轉(zhuǎn)為0)，在完成數(shù)組遍歷后，字典中value為1的就是出現(xiàn)奇數(shù)次的數(shù)。

例如：給定數(shù)組=[3,5,6,6,5,7,2,2]；

首先遍歷3，字典中的元素為：{3:1}；

遍歷5，字典中的元素為：{3:1,5:1}；

遍歷6，字典中的元素為：{3:1,5:1,6:1}；

遍歷6，字典中的元素為：{3:1,5:1,6:0}；

遍歷5，字典中的元素為：{3:1,5:0,6:0}；

遍歷7，字典中的元素為：{3:1,5:0,6:0,7:1}；

遍歷2，字典中的元素為：{3:1,5:0,6:0,7:1,2:1}；

遍歷2，字典中的元素為：{3:1,5:0,6:0,7:1,2:0}；

顯然，出現(xiàn)1次的數(shù)組元素為3和7。

實現(xiàn)代碼如下：

defget2Num(arr):

ifarr==Noneorlen(arr)＜1:

print"參數(shù)不合理"

return

dic=dict()

i=0

whilei＜len(arr):

#dic中沒有這個數(shù)字,說明第一次出現(xiàn),value賦值為1

ifarr[i]notindic:

dic[arr[i]]=1

#當前遍歷的值在dic中存在,說明前面出現(xiàn)過,value賦值為0

else:

dic[arr[i]]=0

i+=1

fork,vindic.items():

ifv==1:

printint(k)

if__name__=="__main__":

arr=[3,5,6,6,5,7,2,2]

get2Num(arr)

程序輸出為：

3

7

性能分析：

這種方法對數(shù)組進行了一次遍歷，時間復雜度為O(n)。但是申請了額外的存儲過程來記錄數(shù)據(jù)出現(xiàn)的情況，因此，空間復雜度為O(n)。

方法二：異或法

根據(jù)異或運算的性質(zhì)不難發(fā)現(xiàn)，任何一個數(shù)字異或它自己其結(jié)果都等于0。所以，對于本題中的數(shù)組元素而言，如果從頭到尾依次異或每一個元素，那么異或運算的結(jié)果自然也就是那個只出現(xiàn)奇數(shù)次的數(shù)字，因為出現(xiàn)偶數(shù)次的數(shù)字會通過異或運算全部消掉。

但是通過異或運算，也僅僅只是消除掉了所有出現(xiàn)偶數(shù)次數(shù)的數(shù)字，最后異或運算的結(jié)果肯定是那兩個出現(xiàn)了奇數(shù)次的數(shù)異或運算的結(jié)果。假設這兩個出現(xiàn)奇數(shù)次的數(shù)分別為a與b，根據(jù)異或運算的性質(zhì)，將二者異或運算的結(jié)果記為c，由于a與b不相等，所以，c的值自然也不會為0，此時只需知道c對應的二進制數(shù)中某一個位為1的位數(shù)N，例如，十進制數(shù)44可以由二