Python程序員面試分類模擬5簡(jiǎn)答題1.

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

在上面這個(gè)圖中，首先遍歷結(jié)點(diǎn)-1，這個(gè)子樹的最大值為-1，同理，當(dāng)遍歷到結(jié)點(diǎn)9時(shí)，子樹的最大值為9，當(dāng)遍歷到結(jié)點(diǎn)3的時(shí)候，這個(gè)結(jié)點(diǎn)與其左右孩子結(jié)點(diǎn)值的和(3-1+9=11)大于最大值(9)。因此，此時(shí)最大的子樹為以3為根結(jié)點(diǎn)的子樹，依此類推，直到遍歷完整棵樹為止。實(shí)現(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:根結(jié)點(diǎn);

maxRoot最大子樹的根結(jié)點(diǎn)

返回值:以root為根結(jié)點(diǎn)子樹所有結(jié)點(diǎn)的和

"""

deffindMaxSubTree(self,root,maxRoot):

ifroot==None:

return0

#求root左子樹所有結(jié)點(diǎn)的和

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

#求root右子樹所有結(jié)點(diǎn)的和

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

sums=1max+rmax+root.data

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

ifsums＞self.maxSum:

self.maxSum=sums

maxRoot.data=root.data

#返回以root為根結(jié)點(diǎn)的予樹的所有結(jié)點(diǎn)的和

returnsums

"""

方法功能:構(gòu)造二叉樹

返回值:返回新構(gòu)造的二叉樹的根結(jié)點(diǎn)

"""

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__":

#構(gòu)造二叉樹

test=Test()

root=test.constructTree()

maxRoot=BiTNode()#最大子樹的根結(jié)點(diǎn)

test.findMaxSubTree(root,maxRoot)

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

print"對(duì)應(yīng)子捌的根結(jié)點(diǎn)為:"+str(maxRoot.data)

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

最大子樹和為：11

對(duì)應(yīng)子樹的根結(jié)點(diǎn)為：3

算法性能分析：

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

2.

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

方法一：分治法

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

方法二：位圖法

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

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

3.

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

defgetRelativePath(path1,path2):

ifpath1==Noneorpath2==None:

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

return

relativePath=""

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

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:

#碰到下一級(jí)目錄

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)

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

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

算法性能分析：

這種方法的時(shí)間復(fù)雜度與空間復(fù)雜度都為O(max(m,n))(其中，m、n分別為兩個(gè)路徑的長(zhǎng)度)。[考點(diǎn)]如何求相對(duì)路徑

4.

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

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

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

(1)用tmp記錄待刪除的結(jié)點(diǎn)的地址。

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

(3)從鏈表中刪除tmp結(jié)點(diǎn)。

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

classLNode:

def__new__(self,x):

self.data=x

self.next=None

"""

**方法功能:對(duì)帶頭結(jié)點(diǎn)的無序單鏈表刪除重復(fù)的結(jié)點(diǎn)

**輸入?yún)?shù):head:鏈表頭結(jié)點(diǎn)

"""

defremoveDup(head):

ifhead==Noneorhead.next==None:

return

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

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

innerPre=None#innerCur的前驅(qū)結(jié)點(diǎn)

whileouterCur!=None:

innerCur=outerCur.next

innerPre=outerCur

whileinnerCur!=None:

#找到重復(fù)的結(jié)點(diǎn)并刪除

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"刪除重復(fù)結(jié)點(diǎn)前:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

removeDup(head)

print"\n刪除重復(fù)結(jié)點(diǎn)后:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

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

刪除重復(fù)結(jié)點(diǎn)前：131557

刪除重復(fù)結(jié)點(diǎn)后：1357

算法性能分析：

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

方法二：遞歸法

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

defremoveDupRecursion(head):

ifhead.nextisNone:

returnhead

pointer=None

cur=head

#對(duì)以head.next為首的予鏈表刪除重復(fù)的結(jié)點(diǎn)

head.next=removeDupRecursion(head.next)

pointer=head.next

#找出以head.next為首的子鏈表中與head結(jié)點(diǎn)相同的結(jié)點(diǎn)并刪除

whilepointerisnotNone:

ifhead.data=pointer.data:

cur.next=pointer.next

pointer=cur.next

else:

pointer=pointer.next

cur=cur.next

returnhead

"""

方法功能:對(duì)帶頭結(jié)點(diǎn)的單鏈刪除重復(fù)結(jié)點(diǎn)輸入?yún)?shù):head:鏈表頭結(jié)點(diǎn)

"""

defremoveDup(head):

if(headisNone):

return

head.next=removeDupRecursion(head.next)

算法性能分析：

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

方法三：空間換時(shí)間

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

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

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

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

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

5.

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