Python程序員面試分類模擬5

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

給定一棵二叉樹，它的每個結點都是正整數(shù)或負整數(shù)，如何找到一棵子樹，使得它所有結點的和最大?正確答案：要求一棵二叉樹的最大子樹和，最容易想到的辦法就是針對（江南博哥）每棵子樹，求出這棵子樹中所有結點的和，然后從中找出最大值。恰好二叉樹的后序遍歷就能做到這一點。在對二叉樹進行后序遍歷的過程中，如果當前遍歷的結點的值與其左右子樹和的值相加的結果大于最大值，則更新最大值。如下圖所示：

在上面這個圖中，首先遍歷結點-1，這個子樹的最大值為-1，同理，當遍歷到結點9時，子樹的最大值為9，當遍歷到結點3的時候，這個結點與其左右孩子結點值的和(3-1+9=11)大于最大值(9)。因此，此時最大的子樹為以3為根結點的子樹，依此類推，直到遍歷完整棵樹為止。實現(xiàn)代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

classTest:

def__init__(self):

self.maxSum=-2**31

"""

方法功能:求最大子樹

輸入?yún)?shù):root:根結點;

maxRoot最大子樹的根結點

返回值:以root為根結點子樹所有結點的和

"""

deffindMaxSubTree(self,root,maxRoot):

ifroot==None:

return0

#求root左子樹所有結點的和

1max=self.findMaxSubTree(root.lchild,maxRoot)

#求root右子樹所有結點的和

rmax=self.findMaxSubTree(root.rchild,maxRoot)

sums=1max+rmax+root.data

#以root為根的子樹的和大于前面求出的最大值

ifsums＞self.maxSum:

self.maxSum=sums

maxRoot.data=root.data

#返回以root為根結點的予樹的所有結點的和

returnsums

"""

方法功能:構造二叉樹

返回值:返回新構造的二叉樹的根結點

"""

defconstructTree(self):

root=BiTNode()

node1=BiTNode()

node2=BiTNode()

node3=BiTNode()

node4=BiTNode()

root.data=6

node1.data=3

node2.data=-7

node3.data=-1

node4.data=9

root.lchild=node1

root.rchild=node2

node1.lchild=node3

node1.rchild=node4

node2.lchild=node2.rchild=node3.lchild=node3.rchild=\

node4.lchild=node4.rchild=None

returnroot

if__name__=="__main__":

#構造二叉樹

test=Test()

root=test.constructTree()

maxRoot=BiTNode()#最大子樹的根結點

test.findMaxSubTree(root,maxRoot)

print"最大子樹和為:"+str(test.maxSum)

print"對應子捌的根結點為:"+str(maxRoot.data)

程序的運行結果為：

最大子樹和為：11

對應子樹的根結點為：3

算法性能分析：

這種方法與二叉樹的后序遍歷有相同的時間復雜度，即為O(N)，其中，N為二叉樹的結點個數(shù)。[考點]如何求一棵二叉樹的最大子樹和

2.

在2.5億個整數(shù)中找出不重復的整數(shù)，注意，內(nèi)存不足以容納這2.5億個整數(shù)。正確答案：由于這道題目與前面的題目類似，也是無法一次性把所有數(shù)據(jù)加載到內(nèi)存中，因此也可以采用類似的方法求解。

方法一：分治法

采用hash的方法，把這2.5億個數(shù)劃分到更小的文件中，從而保證每個文件的大小不超過可用的內(nèi)存的大小。然后對于每個小文件而言，所有的數(shù)據(jù)可以一次性被加載到內(nèi)存中，因此可以使用子典或set來找到每個小文件中不重復的數(shù)。當處理完所有的文件后就可以找出這2.5億個整數(shù)中所有的不重復的數(shù)。

方法二：位圖法

對于整數(shù)相關的算法的求解，位圖法是一種非常實用的算法。對于本題而言，如果可用的內(nèi)存空間超過1GB就可以使用這種方法。具體思路為：假設整數(shù)占用4B(如果占用8B，那么求解思路類似，只不過需要占用更大的內(nèi)存)，4B也就是32位，可以表示的整數(shù)的個數(shù)為232。由于本題只查找不重復的數(shù)，而不關心具體數(shù)字出現(xiàn)的次數(shù)，因此可以分別使用2bit來表示各個數(shù)字的狀態(tài)：用00表示這個數(shù)字沒有出現(xiàn)過，01表示出現(xiàn)過1次，10表示出現(xiàn)了多次，11暫不使用。

根據(jù)上面的邏輯，在遍歷這2.5億個整數(shù)的時候，如果這個整數(shù)對應的位圖中的位為00，那么修改成01，如果為01那么修改為10，如果為10那么保持原值不變。這樣當所有數(shù)據(jù)遍歷完成后，可以再遍歷一遍位圖，位圖中為01的對應的數(shù)字就是沒有重復的數(shù)字。[考點]如何在大量的數(shù)據(jù)中找出不重復的整數(shù)

3.

編寫一個函數(shù)，根據(jù)兩個文件的絕對路徑算出其相對路徑。例如a="/qihoo/app/a/b/c/d/new.c",b="/qihoo/app/1/2/test.c"，那么b相對于a的相對路徑是"../../../../1/2/teSt.c"正確答案：首先找到兩個字符串相同的路徑(/aihoo/app)，然后處理不同的目錄結構(a="/a/b/c/d/new.c",b="/1/2/test.c")。處理方法為：對于a中的每一個目錄結構，在b前面加“../”，對于本題而言，除了相同的目錄前綴外，a還有四級目錄a/b/c/d，因此只需要在b="/1/2/test.c"前面增加四個"../"得到的"../../"/../1/2/test.c"就是b相對a的路徑。實現(xiàn)代碼如下：

defgetRelativePath(path1,path2):

ifpath1==Noneorpath2==None:

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

return

relativePath=""

#用來指向兩個路徑中不同目錄的起始路徑

diff1=0

diff2=0

i=0

j=0

len1=len(path1)

len2=len(path2)

whilei＜len1andj＜len2:

#如果目錄相同,那么往后遍歷

iflist(path1)[i]==list(path2)[j]:

iflist(path1)[i]=='/':

diff1=i

diff2=j

i+=1

j+=1

else:

#不同的目錄

#把path1非公共部分的目錄轉(zhuǎn)換為"/

diff1+=1#跳過目錄分隔符/

whilediff1＜len1:

#碰到下一級目錄

iflist(path1)[diff1]=='/':

relativePath+="../"

diff1+=1

#把path2的非公共部分的路徑加到后面

diff2+=1

relativePath+=path2[diff2:]

break

returnrelativePath

if__name__=="__main__":

path1="/qihoo/app/a/b/c/d/new.c"

path2="/qihoo/app/1/2/test.c"

printgetRelativePath(path1,path2)

程序的運行結果為：

../../../../1/2/test.c

算法性能分析：

這種方法的時間復雜度與空間復雜度都為O(max(m,n))(其中，m、n分別為兩個路徑的長度)。[考點]如何求相對路徑

4.

給定一個沒有排序的鏈表，去掉其重復項，并保留原順序，例如鏈表1-＞3-＞1＞5-＞5-＞7,去掉重復項后變?yōu)?-＞3-＞5-＞7。正確答案：方法一：順序刪除

主要思路為：通過雙重循環(huán)直接在鏈表上進行刪除操作。外層循環(huán)用一個指針從第一個結點開始遍歷整個鏈表，然后內(nèi)層循環(huán)用另外一個指針遍歷其余結點，將與外層循環(huán)遍歷到的指針所指結點的數(shù)據(jù)域相同的結點刪除。如下圖所示：

假設外層循環(huán)從outerCur開始遍歷，當內(nèi)層循環(huán)指針innerCur遍歷到上圖實線所示的位置(outerCur.data==innerCur.data)時，需要把innerCur指向的結點刪除。具體步驟如下：

(1)用tmp記錄待刪除的結點的地址。

(2)為了能夠在刪除tmp結點后繼續(xù)遍歷鏈表中其余的結點，使innerCur指向它的后繼結點：innerCUFinnerCur.next。

(3)從鏈表中刪除tmp結點。

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

classLNode:

def__new__(self,x):

self.data=x

self.next=None

"""

**方法功能:對帶頭結點的無序單鏈表刪除重復的結點

**輸入?yún)?shù):head:鏈表頭結點

"""

defremoveDup(head):

ifhead==Noneorhead.next==None:

return

outerCur=head.next#用于外層循環(huán),指向鏈表第一個結點

innerCur=None#用于內(nèi)層循環(huán)用來遍歷outerCur后面的結點

innerPre=None#innerCur的前驅(qū)結點

whileouterCur!=None:

innerCur=outerCur.next

innerPre=outerCur

whileinnerCur!=None:

#找到重復的結點并刪除

ifouterCur.data==innerCur.data:

innerPre.next=innerCur.next

innerCur=innerCur.next

else:

innerPre=innerCur

innerCur=innerCur.next

outerCur=outerCur.next

if__name__="__main__":

i=1

head=LNode()

head.next=None

tmp=None

cur=head

whilei＜7:

tmp=LNode()

ifi%2=0:

tmp.data=i+1

elifi%3=0:

tmp.data=i-2

else:

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

i+=1

print"刪除重復結點前:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

removeDup(head)

print"\n刪除重復結點后:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

程序的運行結果為：

刪除重復結點前：131557

刪除重復結點后：1357

算法性能分析：

由于這種方法采用雙重循環(huán)對鏈表進行遍歷，因此，時間復雜度為O(N2)，其中，N為鏈表的長度，在遍歷鏈表的過程中，使用了常量個額外的指針變量來保存當前遍歷的結點、前驅(qū)結點和被刪除的結點，因此，空間復雜度為O(1)。

方法二：遞歸法

主要思路為：對于結點cur，首先遞歸地刪除以cur.next為首的子鏈表中重復的結點，接著從以cur.next為首的子鏈表中找出與cur有著相同數(shù)據(jù)域的結點并刪除，實現(xiàn)代碼如下：

defremoveDupRecursion(head):

ifhead.nextisNone:

returnhead

pointer=None

cur=head

#對以head.next為首的予鏈表刪除重復的結點

head.next=removeDupRecursion(head.next)

pointer=head.next

#找出以head.next為首的子鏈表中與head結點相同的結點并刪除

whilepointerisnotNone:

ifhead.data=pointer.data:

cur.next=pointer.next

pointer=cur.next

else:

pointer=pointer.next

cur=cur.next

returnhead

"""

方法功能:對帶頭結點的單鏈刪除重復結點輸入?yún)?shù):head:鏈表頭結點

"""

defremoveDup(head):

if(headisNone):

return

head.next=removeDupRecursion(head.next)

算法性能分析：

這種方法與方法一類似，從本質(zhì)上而言，由于這種方法需要對鏈表進行雙重遍歷，因此，時間復雜度為O(N2)，其中，N為鏈表的長度。由于遞歸法會增加許多額外的函數(shù)調(diào)用，因此，從理論上講，該方法效率比方法一低。

方法三：空間換時間

通常情況下，為了降低時間復雜度，往往在條件允許的情況下，通過使用輔助空間來實現(xiàn)。具體而言，主要思路為：

(1)建立一個HashSet，HashSet中的內(nèi)容為已經(jīng)遍歷過的結點內(nèi)容，并將其初始化為空。

(2)從頭開始遍歷鏈表中的所有結點，存在以下兩種可能性：

1)如果結點內(nèi)容已經(jīng)在HashSet中，那么刪除此結點，繼續(xù)向后遍歷。

2)如果結點內(nèi)容不在HashSet中，那么保留此結點，將此結點內(nèi)容添加到HashSet中，繼續(xù)向后遍歷。[考點]如何從無序鏈表中移除重復項

5.

有一個由大小寫字母組成的字符串，請對它進行重新組合，使得其中的所有小寫字母排在大寫字母的前面(大寫字母或小寫字母之間不要求保持原來次序)。