Python程序員面試分類真題9

Python程序員面試分類真題9(總分：100.00，做題時間：90分鐘)面試題(總題數(shù)：5，分數(shù)：100.00)1.

一個數(shù)組里，除了三個數(shù)是唯一出現(xiàn)的，其余的數(shù)都出現(xiàn)偶數(shù)次，找出這三個數(shù)中的任意一個。比如數(shù)組序列為[1,2,4,5,6,4,2]，只有1，5，6這三個數(shù)字是唯一出現(xiàn)的，數(shù)字2與4均出現(xiàn)了偶數(shù)次(2次)，只需要輸出數(shù)字1，5，6中的任意一個就行。

（分數(shù)：20.00）__________________________________________________________________________________________

正確答案：(根據(jù)題目描述可以得到如下幾個有用的信息：

(1)數(shù)組中元素個數(shù)一定是奇數(shù)個；

(2)由于只有三個數(shù)字出現(xiàn)過一次，顯然這三個數(shù)字不相同，因此，這三個數(shù)對應(yīng)的二進制數(shù)也不可能完全相同。

由此可知，必定能找到二進制數(shù)中的某一個bit來區(qū)分這三個數(shù)(這一個bit的取值或者為0，或者為1)，當通過這一個bit的值對數(shù)組進行分組的時候，這三個數(shù)一定可以被分到兩個子數(shù)組中，并且其中一個子數(shù)組中分配了兩個數(shù)字，而另一個子數(shù)組分配了一個數(shù)字，而其他出現(xiàn)兩次的數(shù)字肯定是成對出現(xiàn)在子數(shù)組中的。此時我們只需要重點關(guān)注哪個子數(shù)組中分配了這三個數(shù)中的其中一個，就可以很容易地找出這個數(shù)字了。當數(shù)組被分成兩個子數(shù)組時，這一個bit的值為1的數(shù)被分到一個子數(shù)組subArray1，這一個bit的值為0的數(shù)被分到另外一個子數(shù)組subArray0。

(1)如果subArray1中元素個數(shù)為奇數(shù)個，那么對subArray1中的所有數(shù)字進行異或操作；由于a^a=0，a^0=a，出現(xiàn)兩次的數(shù)字通過異或操作得到的結(jié)果為0，然后再與只出現(xiàn)一次的數(shù)字執(zhí)行異或操作，得到的結(jié)果就是只出現(xiàn)一次的數(shù)字。

(2)如果subArray0中元素個數(shù)為奇數(shù)個，那么對subArray0中所有元素進行異或操作得到的結(jié)果就是其中一個只出現(xiàn)一次的數(shù)字。

為了實現(xiàn)上面的思路，必須先找到能區(qū)分這三個數(shù)字的bit位，根據(jù)以上的分析給出本算法的實現(xiàn)思路：

以32位平臺為例，一個int類型的數(shù)字占用32位空間，從右向左使用每一位對數(shù)組進行分組，分組的過程中，計算這個bit值為0的數(shù)字異或的結(jié)果result0，出現(xiàn)的次數(shù)count0；這個bit值為1的所有數(shù)字異或的結(jié)果result1，出現(xiàn)的次數(shù)count1。

如果count0是奇數(shù)且result1!=0，那么說明這三個數(shù)中的其中一個被分配到這一bit為0的子數(shù)組中了，因此，這個子數(shù)組中所有數(shù)字異或的值result0一定是出現(xiàn)一次的數(shù)字。(如果result1==0，說明這一個bit不能用來區(qū)分這三個數(shù)字，此時這三個數(shù)字都被分配到子數(shù)組subArray0中了，因此，result1!=0就可以確定這一個bit可以被用來區(qū)分這三個數(shù)字的)。

同理，如果count1是奇數(shù)且result0!=0，那么result1就是其中一個出現(xiàn)1次的數(shù)。

以[6,3,4,5,9,4,3]為例，出現(xiàn)1次的數(shù)字為6(110)，5(101)，9(1001)，從右向左第一位就可以區(qū)分這三個數(shù)字，用這個bit位可以把數(shù)字分成兩個子數(shù)組subArray0=(6,4,4)和subArray1=(3,5,9,3)。subArray1中所有元素異或的值不等于0，說明出現(xiàn)1次的數(shù)字一定在subArray1中出現(xiàn)了，而subArray0中元素個數(shù)為奇數(shù)個，說明出現(xiàn)1次的數(shù)字，其中只有一個被分配到subArray0中了，所以，subArray0中所有元素異或的結(jié)果一定就是這個出現(xiàn)1次的數(shù)字6。實現(xiàn)代碼如下：

#判斷數(shù)字n的二進制數(shù)從右往左數(shù)第i位是否為1

defisOne(n,i):

return(n&(1＜＜i))==1

deffindSingle(arr):

size=len(arr)

i=0

whilei＜32:

result1=result0=count1=count0=0

j=0

whilej＜size:

ifisOne(arr[j],i):

result1^=arr[j]#第i位為1的值異或操作

count1+=1#第i位為1的數(shù)字個數(shù)

else:

result0^=arr[j]#第i位為0的值異或操作

count0+=1#第i位為0的值的個數(shù)

j+=1

i+=1

"""

bit值為1的予數(shù)組元素個數(shù)為奇數(shù),且出現(xiàn)1次的數(shù)字被分配到bit值為0的子數(shù)組,說明只有一個出現(xiàn)1次的數(shù)字被分配到bit值為1的予數(shù)組中,異或記過就是這個出現(xiàn)一次的數(shù)字

"""

ifcount1%2==1andresult0!=0:

returnresult1

#只有一個出現(xiàn)一次的數(shù)字被分配到bit值為0的子數(shù)組中

ifcount0%2=1andresult1!=0:

returnresult0

return-1

if__name__=="__main__":

arr=[6,3,4,5,9,4,3]

result=findSingle(arr)

ifresult!=-1:

printresult

else:

print"沒找到"

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

6

算法性能分析：

這種方法使用了兩層循環(huán)，總共循環(huán)執(zhí)行的次數(shù)為32*N(N為數(shù)組的長度)，因此，算法的時間復(fù)雜度為O(N)。)解析：[考點]如何找出數(shù)組中出現(xiàn)1次的數(shù)2.

請實現(xiàn)方法：print_rotate_matrix(intmatrix,intn)，該方法用于將一個n*n的二維數(shù)組逆時針旋轉(zhuǎn)45°后打印，例如，下圖顯示一個3*3的二維數(shù)組及其旋轉(zhuǎn)后屏幕輸出的效果。

（分數(shù)：20.00）__________________________________________________________________________________________

正確答案：(本題的思路為：從右上角開始對數(shù)組中的元素進行輸出，實現(xiàn)代碼如下：

defrotateArr(arr):

lens=len(arr)

#打印二維數(shù)組右上半部分

i=lens-1

whilei＞0:

row=0

col=i

whilecol＜lens:

printarr[row][col],

row+=1

col+=1

print'\n'

i-=1

#打印二維數(shù)組左下半部分(包括對角線)

i=0

whilei＜lens:

row=i

col=0

whilerow＜lens:

printarr[row][col],

row+=1

col+=1

print'\n'

i+=1

if__name__="__main__":

arr=[[1,2,3l,[4,5,6l,[7,8,9]]

rotateArr(arr)

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

3

26

159

48

7

算法性能分析：

這種方法對數(shù)組中的每個元素都遍歷了一次，因此，算法的時間復(fù)雜度為O(n2)。)解析：[考點]如何對數(shù)組旋轉(zhuǎn)3.

所謂中位數(shù)就是一組數(shù)據(jù)從小到大排列后中間的那個數(shù)字。如果數(shù)組長度為偶數(shù)，那么中位數(shù)的值就是中間兩個數(shù)字相加除以2，如果數(shù)組長度為奇數(shù)，那么中位數(shù)的值就是中間那個數(shù)字。

（分數(shù)：20.00）__________________________________________________________________________________________

正確答案：(根據(jù)定義，如果數(shù)組是一個已經(jīng)排序好的數(shù)組，那么直接通過索引即可獲取到所需的中位數(shù)。如果題目允許排序的話，那么本題的關(guān)鍵在于選取一個合適的排序算法對數(shù)組進行排序。一般而言，快速排序的平均時間復(fù)雜度較低，為O(NlOg2N)，所以，如果采用排序方法的話，算法的平均時間復(fù)雜度為O(Nlog2N)。

可是，題目要求，不許使用排序算法。那么前一種方法顯然走不通。此時，可以換一種思路：分治的思想?？焖倥判蛩惴ㄔ诿恳淮尉植窟f歸后都保證某個元素左側(cè)的元素的值都比它小，右側(cè)的元素的值都比它大，因此，可以利用這個思路快速地找到第N大元素，而與快速排序算法不同的是，這種方法關(guān)注的并不是元素的左右兩邊，而僅僅是某一邊。

根據(jù)快速排序的方法，可以采用一種類似快速排序的方法，找出這個中位數(shù)。具體而言，首先把問題轉(zhuǎn)化為求一列數(shù)中第i小的數(shù)的問題，求中位數(shù)就是求一列數(shù)的第(length/2+1)小的數(shù)的問題(其中l(wèi)ength表示的是數(shù)組序列的長度)。

當使用一次類快速排序算法后，分割元素的下標為pos：

(1)當pos＞length/2時，說明中位數(shù)在數(shù)組左半部分，那么繼續(xù)在左半部分查找。

(2)當pos=lengh/2時，說明找到該中位數(shù)，返回A[pos]即可。

(3)當pos＜length/2時，說明中位數(shù)在數(shù)組右半部分，那么繼續(xù)在數(shù)組右半部分查找。

以上默認此數(shù)組序列長度為奇數(shù)，如果為偶數(shù)就是調(diào)用上述方法兩次找到中間的兩個數(shù)求平均值。示例代碼如下：

classTest:

def__new__(self):

self.pos=0

#以arr[low]為基準把數(shù)組分成兩部分

defpartition(self,arr,low,high):

key=arr[low]

whilelow＜high:

whilelow＜highandarr[high]＞key:

high-=1

arr[low]=arr[high]

whilelow＜highandarr[low]＜key:

low+=1

arr[high]=arr[low]

arr[low]=key

self.pos=low

defgetMid(self,arr):

low=0

n=len(arr)

high=n-1

mid=(low+high)/2

whileTrue:

#以arr[low]為基準把數(shù)組分成兩部分

self.partition(arr,low,high)

ifself.pos==mid:#找到中位數(shù)

break

elifself.pos＞mid:#繼續(xù)在右半部分查找

high=self.pos-1

else:#繼續(xù)在左半部分查找

low-self.pos+1

#如果數(shù)組長度是奇數(shù),中位數(shù)為中間的元素,否則就是中間兩個數(shù)的平均值

returnarr[mid]if(n%2)!=0else(arr[mid]+arr[mid+1])/2

if__name__="__main__":

arr=[7,5,3,1,11,9]

printTest().getMid(arr)

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

6

算法性能分析：

這種方法在平均情況下的時間復(fù)雜度為O(N)。)解析：[考點]如何在不排序的情況下求數(shù)組中的中位數(shù)4.

有一個集合，求其全部子集(包含集合自身)。給定一個集合s，它包含兩個元素＜a,b＞，則其全部的子集為＜a,ab,b＞。

（分數(shù)：20.00）__________________________________________________________________________________________

正確答案：(根據(jù)數(shù)學(xué)性質(zhì)分析，不難得知，子集個數(shù)Sn與原集合元素個數(shù)n之間的關(guān)系滿足如下等式：Sn=2^n-1。

方法一：位圖法

具體步驟如下所示。

(1)構(gòu)造一個和集合一樣大小的數(shù)組A，分別與集合中的某個元素對應(yīng)，數(shù)組A中的元素只有兩種狀態(tài)：“1”和“0”，分別代表每次子集輸出中集合中對應(yīng)元素是否要輸出，這樣數(shù)組A可以看作是原集合的一個標記位圖。

(2)數(shù)組A模擬整數(shù)“加1”的操作，每執(zhí)行“加1”操作之后，就將原集合中所有與數(shù)組A中值為“1”的相對應(yīng)的元素輸出。

設(shè)原集合為＜a,b,c,d＞，數(shù)組A的某次“加1”后的狀態(tài)為[1,0,1,1]，則本次輸出的子集為＜a,c,d＞。使用非遞歸的思想，如果有一個數(shù)組，大小為n，那么就使用n位的二進制，如果對應(yīng)的位為1，那么就輸出這個位，如果對應(yīng)的位為0，那么就不輸出這個位。

例如集合{a,b,c}的所有子集可表示如下：集合二進制表示{}(空集)000{a}001010{c}100{a,b}011{a,c}101{b,c}110{a,b,c}111

算法的重點是模擬數(shù)組加1的操作。數(shù)組可以一直加1，直到數(shù)組內(nèi)所有元素都是1。實現(xiàn)代碼如下：

defgetAllSubset(array,mask,c):

length=len(array)

iflength==c:

print"{",

i=0

whilei＜length:

ifmask[i]==1:

printarray[i],

i+=1

print"}"

else:

mask[c]=1

getAllSubset(array,mask,c+1)

mask[c]=0

getAllSubset(array,mask,c+1)

if__name__="__main__":

array=['a,'b','c']

mask=[0,0.0]

getAllSubset(array,mask,0)

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

{abc}

{ab}

{ac}

{a}

{bc}

{c}

該方法的缺點在于如果數(shù)組中有重復(fù)數(shù)時，這種方法將會得到重復(fù)的子集。

算法性能分析：

這種方法的時間復(fù)雜度為O(N*2N)，空間復(fù)雜度O(N)。

方法二、迭代法

采用迭代算法的具體過程如下：

假設(shè)原始集合s=＜a,b,c,d＞，子集結(jié)果為r：

第一次迭代：

r=＜a＞

第二次迭代：

r=＜aabb＞

第三次迭代：

r=＜aabbacabcbcc＞

第四次迭代：

r=＜aabbacabcbccadabdbdacdabcdbcdcdd＞

每次迭代，都是上一次迭代的結(jié)果+上次迭代結(jié)果中每個元素都加上當前迭代的元素+當前迭代的元素。

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

defgetAllSubset(str):

ifstr==Noneorlen(str)＜1:

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

returnNone

arr=[]

arr.append(str[0:1])

i=1

whilei＜len(str):

lens=len(arr)

j=0

whilej＜lens:

arr.append(arr[j]+str[i])

j+=1

arr.append(str[i:i+1])

i+=1

returnarr

if__name__=="__main__":

result=getAllSubset("abc")

i=0

whilei＜len(result):

printresult[i]

i+=1

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

a

ab

b

ac

abc

bc

c

根據(jù)上述過程可知，第k次迭代的迭代次數(shù)為：2k-1。需要注意的是，n≥k≥1，迭代n次，總的遍歷次數(shù)為：2n+1-(2+n)，n≥1，所以，本方法的時間復(fù)雜度為O(2n)。

由于在該算法中，下一次迭代過程都需要上一次迭代的結(jié)果，而最后一次迭代之后就沒有下一次了。因此，假設(shè)原始集合有n個元素，則在迭代過程中，總共需要保存的子集個數(shù)為2n-1-1，n≥1。但需要注意的是，這里只考慮了子集的個數(shù)，每個子集元素的長度都被視為1。

其實，比較上述兩種方法，不難發(fā)現(xiàn)，第一種方法可以看作是用時間換空間，而第二種方法可以看作是用空間換時間。)解析：[考點]如何求集合的所有子集5.

把一個含有N個元素的數(shù)組循環(huán)右移K(K是正數(shù))位，要求時間復(fù)雜度為O(N)，且只允許使用兩個附加變量。

（分數(shù)：20.00）__________________________________________________________________________________________

正確答案：(由于有空間復(fù)雜度的要求，因此，只能在原數(shù)組中就地進行右移。

方法一：蠻力法

蠻力法也是最簡單的方法，題目中需要將數(shù)組元素循環(huán)右移K位，只需要每次將數(shù)組中的元素右移一位，循環(huán)K次即可。例如，假設(shè)原數(shù)組為abcd1234，那么，按照此種方式，具體移動過程如下所示：abcd1234→4abcd123→34abcd12→234abcd1→1234abcd。

此種方法也很容易寫出代碼。示例代碼如下：

defrightShift(arr,k):

ifarr==None:

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

return

lens=len(arr)

whilek!=0:

tmp=arr[lens-1]

i=lens-1

whilei＞0:

arr[i]=arr[i-1]

i-=1

arr[0]=tmp

k-=1

if__name__="__main__":

k=4

arr=[1,2,3,4,5,6,7,8]

rightShift(arr,k)

i=0

whilei＜len(arr):

printarr[i],

i+=1

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

56781234

以上方法雖然可以實現(xiàn)數(shù)組的循環(huán)右移，但是由于每移動一次，其時間復(fù)雜度就為O(N)，所以，移動K次，其總的時間復(fù)雜度為0(K*N)，O＜K＜N，與題目要求的O(N)不符合，需要繼續(xù)往下探索。

對于上述代碼，需要考慮到，K不一定小于N，有可能等于N，也有可能大于N。當K＞N時，右移K-N之后的數(shù)組序列跟右移K位的結(jié)果一樣，所以，當K＞N時，右移K位與右移K'(其中K'=K%N)位等價，根據(jù)以上分析，相對完備的代碼如下：

defrightshift(arr,k):

ifarr==None:

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

return

lens=len(arr)

k%=lens

whilek!=0:

t=rr[lens-1];

i=lens-1

whilei＞0:

arr[i]=arr[i-1]

i-=1

arr[0]=t

k-=1

if__name__=="__main__":

k=4;

arr=[1,2,3,4,5,6,7,8]

rightShift(arr,k)

i=0

whilei＜len(arr):

priritarr[i],

i+=1

算法性能分析：

上例中，算法的時間復(fù)雜度為O(N2)，與K值無關(guān)，但時間復(fù)雜度仍然太高，是否還有其他更好的方法呢?

仔細分析上面的方法，不難發(fā)現(xiàn)，上述方法的移動采取的是一步一步移動的方式，可是問題是，題目中已經(jīng)告知了需要移動的位數(shù)為K，為什么不能一步到位呢?

方法二、空間換時間法

通常情況下，以空間換時間往往能夠降低時間復(fù)雜度，本題也不例外。

首先定義一個輔助數(shù)組T，把數(shù)組A的第N-K+1到N位數(shù)組中的元素存儲到輔助數(shù)組T中，然后再把數(shù)組A中的第1到N-K位數(shù)組元素存儲到輔助數(shù)組T中，然后將數(shù)組T中的元素復(fù)制回數(shù)組A，這樣就完成了數(shù)組的循環(huán)右移，此時的時間復(fù)雜度O(N)。

雖然時間復(fù)雜度滿足要求，但是空間復(fù)雜度卻提高了，由于需要創(chuàng)建一個新的數(shù)組，所以，此時的空間復(fù)雜度O(N)，鑒于此，還可以對此方法繼續(xù)優(yōu)化。

方法三：翻轉(zhuǎn)法

把數(shù)組看成由兩段組成的，記為XY。左旋轉(zhuǎn)相當于要把數(shù)組XY變成YX。先在數(shù)組上定義一種翻轉(zhuǎn)的操作，就是翻轉(zhuǎn)數(shù)組中數(shù)字的先后順序。把