Python程序員面試分類真題111.

給定一個大小為N×N的迷宮，一只老鼠需要從迷宮的左上角(對應(yīng)矩陣的[0][0])走到迷宮的右下角(對應(yīng)矩陣的[N-1][N-1])，老鼠只能向兩方向移動：向右或向下。（江南博哥）在迷宮中，0表示沒有路(是死胡同)，1表示有路。例如：給定下面的迷宮：

圖中標粗的路徑就是一條合理的路徑。請給出算法來找到這么一條合理路徑。正確答案：最容易想到的方法就是嘗試所有可能的路徑，找出可達的一條路。顯然這種方法效率非常低下，這里重點介紹一種效率更高的回溯法。主要思路為：當(dāng)碰到死胡同的時候，回溯到前一步，然后從前一步出發(fā)繼續(xù)尋找可達的路徑。算法的主要框架為：申請一個結(jié)果矩陣來標記移動的路徑if到達了目的地打印解決方案矩陣else(1)在結(jié)果矩陣中標記當(dāng)前為1(1表示移動的路徑)。(2)向右前進一步，然后遞歸地檢查，走完這一步后，判斷是否存在到終點的可達的路線。(3)如果步驟(2)中的移動方法導(dǎo)致沒有通往終點的路徑，那么選擇向下移動一步，然后檢查使用這種移動方法后，是否存在到終點的可達的路線。(4)如果上面的移動方法都會導(dǎo)致沒有可達的路徑，那么標記當(dāng)前單元格在結(jié)果矩陣中為0，返回false，并回溯到前一步中。

根據(jù)以上框架很容易進行代碼實現(xiàn)。示例代碼如下：

classMaze:

def__init__(self):

self.N=4

#打印從起點到終點的路線

defprintSolution(self,sol):

i=0

whilei＜self.N:

j=0

whilej＜self.N:

printsol[i][j],

j+=1

print'\n'

i+=1

#判斷x和y是否是一個合理的單元

defisSafe(self,maze,x,y):

returnx＞=0andx＜self.Nandy＞=0and\

y＜self.Nandmaze[x][y]==1

"""

使用回溯的方法找到一條從左上角到右下角的路徑

maze表示迷宮,x、y表示起點,sol存儲結(jié)果

"""

defgetPath(self,maze,x,y,sol):

#到達目的地

ifx==self.N-1andy==self.N-1:

sol[x][y]=1

returnTrue

#判斷maze[x][y]是否是一個可走的單元

ifself.isSafe(maze,x,y):

#標記當(dāng)前單元為1

sol[x][y]=1

#向右走一步

ifself.getPath(maze,x+1,y,sol):

returnTrue

#向下走一步

ifself.getPath(maze,x,y+1,sol):

returnTrue

#標記當(dāng)前單元為0用來表示這條路不可行,然后回溯

sol[x][y]=0

returnFalse

returnFalse

if__name__=="__main__":

rat=Maze()

maze=[[1,0,0,0],

[1,1,0,1],

[0,1,0,0],

[1,1,1,1]]

sol=[[0,0,0,0],

[0,0,0,0],

[0,0,0,0],

[0,0,0,0]]

ifnotrat.getPath(maze,0,0,sol):

print"不存在可達的路徑"

else:

rat.printSolution(sol)

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

1000

1100

0100

0111[考點]如何求解迷宮問題

2.

給定以非遞減順序排序的三個數(shù)組，找出這三個數(shù)組中的所有公共元素。例如，給出下面三個數(shù)組：ar1=[2,5,12,20,45,85],ar2=[16,19,20,85,200],ar3=[3,4,15,20,39,72,85,190]。那么這三個數(shù)組的公共元素為[20,85]。正確答案：最容易想到的方法是首先找出兩個數(shù)組的交集，然后再把這個交集存儲在一個臨時數(shù)組中，最后再找出這個臨時數(shù)組與第三個數(shù)組的交集。這種方法的時間復(fù)雜度為O(N1+N2+N3)，其中N1、N2和N3分別為三個數(shù)組的大小。這種方法不僅需要額外的存儲空間，而且還需要額外的兩次循環(huán)遍歷。下面介紹另外一種只需要一次循環(huán)遍歷、而且不需要額外存儲空間的方法，主要思路為：

假設(shè)當(dāng)前遍歷的三個數(shù)組的元素分別為ar1[i]、ar2[j]、ar3[k]，則存在以下幾種可能性：

(1)如果ar1[i]、ar2[j]和ar3[k]相等，則說明當(dāng)前遍歷的元素是三個數(shù)組的公共元素，可以直接打印出來，然后通過執(zhí)行i+，j+，k+，使三個數(shù)組同時向后移動，此時繼續(xù)遍歷各數(shù)組后面的元素。

(2)如果ar1[i]＜ar2[j]，則執(zhí)行i+來繼續(xù)遍歷ar1中后面的元素，因為ar1[i]不可能是三個數(shù)組公共的元素。

(3)如果ar2[j]＜ar3[k]，同理可以通過j+來繼續(xù)遍歷ar2后面的元素。

(4)如果前面的條件都不滿足，說明ar1[i]＞ar2[j]而且ar2[j]＞ar3[k]，此時可以通過k+來繼續(xù)遍歷ar3后面的元素。

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

deffindCommon(ar1,ar2,ar3):

i=0

j=0

k=0

n1=len(ar1)

n2=len(ar2)

n3=len(ar3)

#遍歷三個數(shù)組

whilei＜n1andj＜n2andk＜n3:

#找到了公共元素

ifar1[i]==ar2[j]andar2[j]==ar3[k]:

printar1[i],

i+=1

j+=1

k+=1

#ar[i]不可能是公共元素

elifar1[i]＜ar2[j]:

i+=1

#ar2[j]不可能是公共元素

elifar2[j]＜ar3[k]:

j+=1

#ar3[k]不可能是公共元素

else:

k+=1

if__name__=="__main__":

ar1=[2,5,12,20,45,85]

ar2=[16,19,20,85,200]

ar3=[3,4,15,20,39,72,85,190]

fidCommon(ar1,ar2,ar3)

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

2085

算法性能分析：

這種方法的時間復(fù)雜度為O(N1+N2+N3)。[考點]如何從三個有序數(shù)組中找出它們的公共元素

3.

有兩個有序的集合，集合中的每個元素都是一段范圍，求其交集，例如集合{[4,8],[9,13]}和{[6,12]}的交集為{[6,8],[9,12]}。正確答案：方法一：蠻力法

最簡單的方法就是遍歷兩個集合，針對集合中的每個元素判斷是否有交集，如果有，則求出它們的交集，實現(xiàn)代碼如下：

classMySet:

def__init__(self,mins,maxs):

self.mins=mins

self.maxs=maxs

defgetMin(self):

returnself.mins

defsetMin(self,mins):

self.mins=mins

defgetMax(self):

returnself.maxs

defsetMax(self,maxs):

self.maxs=maxs

defgetlntersection(s1,s2):

ifs1.getMin()＜s2.getMin():

ifs1.getMax()＜s2.getMin():

returnNone

elifs1.getMax()＜=s2.getMax():

returnMySet(s2.getMin(),s1.getMax())

else:

returnMySet(s2.getMin(),s2.getMax())

elifs1.getMin()＜=s2.getMax():

ifs1.getMax()＜=s2.getMax():

returnMySet(s1.getMin(),s1.getMax())

else:

returnMySet(s1.getMinO,s2.getMax())

else:

returnNone

defgetlntersection2(11,12):

result=[]

i=0

whilei＜len(11):

j=0

whilej＜len(12):

s=getIntersection(11[i,12[j])

ifs!=None:

result.append(s)

j+=1

i+=1

returnresult

if__name__="__main__":

11=[]

12=[]

11.append(MySet(4,8))

11.append(MySet(9,13))

12.append(MySet(6,12))

result=getIntersection2(11,12)

i=0

whilei＜len(result):

print"["+str(result[i].getMin())+","+str(result[i].getMax())+"]"

i+=1

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

[6,8]

[9,12]

算法性能分析：

這種方法的時間復(fù)雜度為O(n2)。

方法二：特征法

上述這種方法顯然沒有用到集合有序的特點，因此，它不是最佳的方法。假設(shè)兩個集合為s1，s2。當(dāng)前比較的集合為s1[i]和s2[j]，其中，i與j分別表示的是集合s1與s2的下標。可以分為如下幾種情況：

1)s1集合的下界小于s2的上界，如下圖所示：

在這種情況下，s1[i]和s2[j]顯然沒有交集，那么接下來只有s1[i+1]與s2[j]才有可能會有交集。

2)s1的上界介于s2的下界與上界之間，如下圖所示：

在這種情況下，s1[i]和s2[j]有交集(s2[j]的下界和s1[i]的上界)，那么接下來只有s1[i+1]與s2[j]才有可能會有交集。

3)s1包含s2，如下圖所示：

在這種情況下，s1[i]和s2[j]有交集(交集為s2[j])，那么接下來只有s1[i]與s2[j+1]才有可能會有交集。

4)s2包含s1，如下圖所示：

在這種情況下，s1[i]和s2[j]有交集(交集為s1[i])，那么接下來只有s1[i+1]與s2[j]才有可能會有交集。

5)s1的下界介于s2的下界與上界之間，如下圖所示：

在這種情況下，s1[i]和s2[j]有交集(交集為s1[i]的下界和s2[j]的上界)，那么接下來只有s1[i]與s2[j+1]才有可能會有交集。

6)s2的上界小于s1的下界，如下圖所示：

在這種情況下，s1[i]和s2[j]顯然沒有交集，那么接下來只有s1[i]與s2[j+1]才有可能會有交集。

根據(jù)以上分析給出實現(xiàn)代碼如下：

classMySet:

def__init__(self,mins,maxs):

self.mins=mins

self.maxs=maxs

defgetMin(self):

returnself.mins

defsetMin(self,mins):

self.mins=mins

defgetMax(self):

returnself.maxs

defsetMax(self,maxs):

self.maxs=maxs

defgetlntersection(11,12):

result=[]

i=0

j=0

whilei＜len(11)andj＜len(12):

s1=11[i]

s2=12[j]

ifs1.getMin()＜s2.getMin():

ifs1.getMax()＜s2.getMin():

i+=1

elifs1.getMax()＜=s2.getMax():

result.append(MySet(s2.getMin(),s1.getMax(()))

i+=1

else:

result.append(MySet(s2.getMin(),s2.getMax()))

j+=1

elifs1.getMin()＜=s2.getMax():

ifs1.getMax()＜=s2.getMax():

result.append(MySet(s1.getMin(),s1.getMax()))

i+=1

else:

result.append(MySet(s1.getMin(),s2.getMax()))

j+=1

else:

j+=1

returnresult

if__name__="__main__":

11=[]

12=[]

11.append(MySet(4,8))

11.append(MySet(9,13))

12.append(MySet(6,12))

result=getIntersection(11,12)

i=0

whilei＜len(result):

print"["+str(result[i].getMin())+","+str(result[i].getMax())+"]"

i+=1

算法性能分析：

這種方法的時間復(fù)雜度為O(N1+N2)，其中N1、N2分別為兩個集合的大小。[考點]如何求兩個有序集合的交集

4.

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

方法一：AVL樹

這種方法的主要思路為：根據(jù)數(shù)組中的數(shù)構(gòu)建一個AVL樹，這里需要對AVL樹做適當(dāng)?shù)臄U展，在結(jié)點中增加一個額外的數(shù)據(jù)域來記錄這個數(shù)字出現(xiàn)的次數(shù)，在AVL樹構(gòu)建完成后，可以對AVL樹進行中序遍歷，根據(jù)每個結(jié)點對應(yīng)數(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é)點對應(yīng)的數(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é)點對應(yīng)的count加1即可

"""

definsert(self,root,data):

ifroot==None:

return(Node(data))

#data在樹中存在,把對應(yīng)的結(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)中學(xué)過的四種情況進行調(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

算法性能分析：

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

方法二：哈希法

這種方法的主要思路為創(chuàng)建一個哈希表，然后遍歷數(shù)組，把數(shù)組中的數(shù)字放入哈希表中，在遍歷的過程中，如果這個數(shù)在哈希表中存在，則直接把哈希表中這個key對應(yīng)的value加1；如果這個數(shù)在哈希表中不存在，則直接把這個數(shù)添加到哈希表中，并且初始化這個key對應(yīng)的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

算法性能分析：

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

5.

假設(shè)有一個中央調(diào)度機，有n個相同的任務(wù)需要調(diào)度到m臺服務(wù)器上去執(zhí)行，由于每臺服務(wù)器的配置不一樣，因此，服務(wù)器執(zhí)行一個任務(wù)所花費的時間也不同?，F(xiàn)在假設(shè)第i個服務(wù)器執(zhí)行一個任務(wù)所花費的時間也不同。現(xiàn)在假設(shè)第i個服務(wù)器執(zhí)行一個任務(wù)需要的時間為t[i]。例如：有2個執(zhí)行機a與b，執(zhí)行一個任務(wù)分別需要7min，10min，有6個任務(wù)待調(diào)度。如果平分這6個任務(wù)，即a與b各3個任務(wù)，則最短需要30min執(zhí)行完所有。如果a分4個任務(wù)，b分2個任務(wù)，則最短28min執(zhí)行完。請設(shè)計調(diào)度算法，使得所有任務(wù)完成所需要的時間最短。輸入m臺服務(wù)器，每臺機器處理一個任務(wù)的時間為t[i]，完成n個任務(wù)，輸出n個任務(wù)在m臺服務(wù)器的分布：estimate_process_time(t,m,n)。正確答案：本題可以采用貪心法來解決，具體實現(xiàn)思路如下：

申請一個數(shù)組來記錄每臺機器的執(zhí)行時間，初始化為0，在調(diào)度任務(wù)的時候，對于每個任務(wù)，在選取機器的時候采用如下的貪心策略：對于每臺機器，計算機器已經(jīng)分配任務(wù)的執(zhí)行時間+這個任務(wù)需要的時間，選用最短時間的機器進行處理。實現(xiàn)代碼如下：

"""

paramt每個服務(wù)器處理的時間

paramn任務(wù)的個數(shù)

return各個服務(wù)器執(zhí)行完任務(wù)所需的時間

"""

defcalculate_rocess_time(t,n):

ift==Noneorn＜=0:

returnNone

m=len(t)

proTime=[0]*m

i=0

whilei＜n:

minTime=proTime[0]+t[0]#把任務(wù)給第j個機器上后這個機器的執(zhí)行時間

minIndex=0#把任務(wù)給第minIndex個機器上

j=1

whilej＜m:

#分配到第j臺機器上后執(zhí)行時間更短

ifminTime＞proTime[j]+t[j]:

minTime=proTime[j]+t[j]

minIndex=j

j+=1

proTime[minIndex]+=t[minIndex]

i+=1

returnproTime

if__name__=="__main__":

t=[7,10]

n=6

proTime=calculate_process_time(t,n)

ifproTime==None:

print"分配失敗"

else:

totalTime=proTime[0]

i=0

whilei＜len(proTime):

print"第"+str((i+1))+"臺服務(wù)器有"+str(proTime[i]/t[i])+"個任務(wù),執(zhí)行總時間為:"+str(proTim