Python程序員面試分類模擬8

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

假設(shè)L=＜a1,a2...,an＞是n個不同的實數(shù)的序列，L的遞增子序列是這樣一個子序列Lin=＜ak1,ak2,...,akm＞，其中，k1＜k2＜...＜k（江南博哥）m且ak1＜ak2＜...＜akm。求最大的m值。正確答案：方法一：最長公共子串法

對序列L=＜a1,a2,...,an＞按遞增進行排序得到序列LO=＜b1,b2,...,bn＞。顯然，L與LO的最長公共子序列就是L的最長遞增子序列。因此，可以使用求公共子序列的方法來求解。

方法二：動態(tài)規(guī)劃法

由于以第i個元素為結(jié)尾的最長遞增子序列只與以第i-1個元素為結(jié)尾的最長遞增子序列有關(guān)，因此，本題可以采用動態(tài)規(guī)劃的方法來解決。下面首先介紹動態(tài)規(guī)劃方法中的核心內(nèi)容遞歸表達式的求解。

以第i個元素為結(jié)尾的最長遞增子序列的取值有兩種可能：

(1)1，第i個元素單獨作為一個子串(L[i]＜=L[i-1])；

(2)以第i-1個元素為結(jié)尾的最長遞增子序列加1(L[i]＞L[i-1])。

由此可以得到如下的遞歸表達式：假設(shè)maxLen[i]表示以第i個元素為結(jié)尾的最長遞增子序列，那么

(1)maxLen[i]=max[1,maxLen[j]+1],j＜iandL[j]＜L[i]

(2)maxLen[0]=1

根據(jù)這個遞歸表達式可以非常容易地寫出實現(xiàn)的代碼：

#函數(shù)功能:求字符串L的最長遞增子串的長度

defgetMaxAscendingLen(strs):

lens=len(strs)

maxLen=[None]*lens

maxLen[0]=1

maxAscendingLen=1

i=1

whilei＜lens:

maxLen[i]=1#maxLen[i]的最小值為1;

j=0

whilej＜i:

iflist(strs)[j]＜list(strs)[i]andmaxLen[j]＞maxLen[i]-1:

maxLen[i]=maxLen[j]+1

maxAscendingLen=maxLen[i]

j+=1

i+=1

returnmaxAscendingLen

if__name__=="__main__":

s="xbcdza"

print"最長遞增子序列的長度為:"+str(getMaxAscendingLen(s))

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

xbcdza最長遞增予序列的長度為：4

算法性能分析：

由于這種方法用雙重循環(huán)來實現(xiàn)，因此，這種方法的時間復(fù)雜度為O(N2)，此外由于這種方法還使用了N個額外的存儲空間，因此，空間復(fù)雜度為O(N)。[考點]如何求最長遞增子序列的長度

2.

給定由字母組成的字符串s1和s2，其中，s2中字母的個數(shù)少于s1，如何判斷s1是否包含s2?即出現(xiàn)在s2中的字符在s1中都存在。例如s1=“abcdef"，s2=“acf”，那么s1就包含s2；如果s1=“abcdef”，s2=“acg”，那么s1就不包含s2，因為s2中有“g”，但是s1中沒有“g”。正確答案：方法一：直接法

最直接的方法就是對于s2中的每個字符，通過遍歷字符串s1查看是否包含該字符。實現(xiàn)代碼如下：

defisContain(str1,str2):

len1=len(str1)

len2=len(str2)

#字符串ch1比ch2短

iflen1＜len2:

i=0

whilei＜len1:

j=0

whilej＜len2:

iflist(str1)[i]==list(str2)[j]:

break

j+=1

if(j＞=len2):

returnFalse

i+=1

else:

#字符串ch1比ch2長

i=0

whilei＜len2:

j=0

whilej＜len1:

if(list(str1)[j]==list(str2)[i]):

break

j+=1

ifj＞=len1:

returnFalse

i+=1

returnTrue

if__name__=="__main__":

str1="abcdef'

str2="acf"

isContain=isContain(str1,str2)

priritstr1+"與"+str2,

if(isContain):

print"有包含關(guān)系"

else:

print"沒有包含關(guān)系"

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

abcdef與acf有包含關(guān)系

算法性能分析：

這種方法的時間復(fù)雜度為O(m*n)，其中，m與n分別表示兩個字符串的長度。

方法二：空間換時間法

首先，定義一個flag數(shù)組來記錄較短的字符串中字符出現(xiàn)的情況，如果出現(xiàn)，那么標記為1，否則標記為0，同時記錄flag數(shù)組中1的個數(shù)count；接著遍歷較長的字符串，對于字符a，若原來flag[a]==1，則修改flag[a]=0，并將count減1；若flag[a]==0，則不做處理。最后判斷count的值，如果count==0，那么說明這兩個字符有包含關(guān)系。實現(xiàn)代碼如下：

defisContain(s1,s2):

k=0#字母對應(yīng)數(shù)組的下標

#用來記錄52個字母的出現(xiàn)情況

flag=[None]*52

i=0

whilei＜52:

flag[i]=0

i+=1

count=0#記錄段字符串中不同字符出現(xiàn)的個數(shù)

len1=len(s1)

len2=len(s2)

#shortStr,longStr分別用來記錄較短和較長的字符串

#maxLen,minLen分別用來記錄較長和較短字符的長度

iflen1＜len2:

shortStr=s1

minLen=len1

longStr=s2

maxLen=len2

else:

shortStr=s2

minLen=len2

longStr=s1

maxLen=len1

#遍歷短字符串

i=0

whilei＜minLen:

#把字符轉(zhuǎn)換成數(shù)組對應(yīng)的下標(大寫字母0～25,小寫字母26～51)

iford(list(shortStr)[i])＞=ord('A')andord(list(shortStr)[i])＜=ord('Z'):

k=ord(list(short,Str)[i])-ord('A')

else:

k=ord(list(shortStr)[i])-ord('a')+26

ifflag[k]==0:

flag[k]=1

count+=1

i+=1

#遍歷長字符串

j=0

whilej＜maxLen:

iford(list(longStr)[j])＞=ord('A')andord(list(longStr)[j])＜=ord('Z'):

k=ord(list(longStr)[j])-ord('A')

else:

k=ord(list(longStr)[j])-ord('a')+26

ifflag[k]==1:

flag[k]=0

count-=1

ifcount==0:

returnTrue

j+=1

returnFalse

if__name__=="__main__":

str1="abcdef"

str2="acf"

isContain=isContain(str1,str2)

priitstr1+"與"+str2,

ifisContain:

print"有包含關(guān)系"

else:

print"沒有包含關(guān)系"

算法性能分析：

這種方法只需要對兩個數(shù)組分別遍歷一遍，因此，時間復(fù)雜度為O(m+n)(其中m、n分別為兩個字符串的長度)，與方法一比，本方法的效率有了明顯的提升，但是其缺點是申請了52個額外的存儲空間。[考點]如何判斷兩個字符串的包含關(guān)系

3.

給定一個有序鏈表，其中每個結(jié)點也表示一個有序鏈表，結(jié)點包含兩個類型的指針：

(1)指向主鏈表中下一個結(jié)點的指針(在下面的代碼中稱為“正確”指針)

(2)指向此結(jié)點頭的鏈表(在下面的代碼中稱之為“down”指針)。

所有鏈表都被排序。請參見以下示例：

實現(xiàn)一個函數(shù)flatten()，該函數(shù)用來將鏈表扁平化成單個鏈表，扁平化的鏈表也應(yīng)該被排序。例如，對于上述輸入鏈表，輸出鏈表應(yīng)為3-＞6-＞8-＞11-＞15-＞21-＞22-＞30-＞31-＞39-＞40-＞45-＞50。正確答案：本題的主要思路為使用歸并排序中的合并操作，使用歸并的方法把這些鏈表來逐個歸并。具體而言，可以使用遞歸的方法，遞歸地合并已經(jīng)扁平化的鏈表與當前的鏈表。在實現(xiàn)的過程可以使用down指針來存儲扁平化處理后的鏈表。實現(xiàn)代碼如下：

classNode:

def__init__(self,data):

self.data=data

#self.next=None

self.right=None

self.down=None

#self.head=None

classMergeList:

def__init__(self):

self.head=None

#用來合并兩個有序的鏈表*

defmerge(self,a,b):

#如果有其中一個鏈表為空,直接返回另外一個鏈表

ifa==None:

returnb

ifb==None:

returna

#把兩個鏈表頭中較小的結(jié)點賦值給result

ifa.data＜b.data:

result=a

result.down=self.merge(a.down,b)

else:

result=b

result.down=self.merge(a,b.down)

returnresult

#把鏈表扁平化處理

defflatten(self,root):

ifroot==Noneorroot.right==None:

returnroot

#遞歸處理root.right鏈表

root.right=self.flatten(root.right)

#把root結(jié)點對應(yīng)的鏈表與右邊的鏈表合并

root=self.merge(root,root.right)

returnroot

#把data插入到鏈表頭

definsert(self,head_ref,data):

new_node=Node(data)

new_node.down=head_ref

head_ref=new_node

#返回新的表頭結(jié)點

returnhead_ref

defprintList(self):

temp=self.head

whiletemp!=None:

printtemp.data,

temp=temp.down

print'\n'

if__name__=="__main__":

L=MergeList()

#構(gòu)造鏈表

L.head=L.insert(L.head,31)

L.head=L.insert(L.head,8)

L.head=L.insert(L.head,6)

L.head=L.insert(L.head,3)

L.head.right=L.insert(L.head.right,21)

L.head.right=L.insert(L.head.right,11)

L.head.right.right=L.insert(L.head.right.right,50)

L.head.right.right=L.insert(L.head.right.right,22)

L.head.right.right=L.insert(L.head.right.right,15)

L.head.right.right.right=L.insert(L.head.right.right.right,55)

L.head.right.right.right=L.insert(L.head.right.right.right,40)

L.head.right.right.right=L.insert(L.head.right.right.right,39)

L.head.right.right.right=L.insert(L.head.right.right.right,30)

#扇平化鏈表

L.head=L.flatten(L.head)

L.printList()

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

36811152122303139405055[考點]如何展開鏈接列表

4.

二叉樹的鏡像就是二叉樹對稱的二叉樹，就是交換每一個非葉子結(jié)點的左子樹指針和右子樹指針，如下圖所示，請寫出能實現(xiàn)該功能的代碼。注意：請勿對該樹做任何假設(shè)，它不一定是平衡樹，也不一定有序。

正確答案：從上圖可以看出，要實現(xiàn)二叉樹的鏡像反轉(zhuǎn)，只需交換二叉樹中所有結(jié)點的左右孩子即可。由于對所有的結(jié)點都做了同樣的操作，因此，可以用遞歸的方法來實現(xiàn)，由于需要調(diào)用printTreeLayer層序打印二叉樹，這種方法中使用了隊列來實現(xiàn)，實現(xiàn)代碼如下：

fromcollectionsimportdeque

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

#對二叉樹進行鏡像反轉(zhuǎn)

defreverseTree(root):

ifroot==None:

return

reverseTree(root.lchild)

reverseTree(root.rchild)

tmp=root.lchild

root.lchild=root.rchild

root.rchild=tmp

defarraytotree(arr,start,end):

root=None

ifend＞=start:

root=BiTNode()

mid=(start+end+1)/2

#樹的根結(jié)點為數(shù)組中間的元素

root.data=arr[mid]

#遞歸的用左半部分數(shù)組構(gòu)造root的左子樹

root.lchild=arraytotree(arr,start,mid-1)

#遞歸的用右半部分數(shù)組構(gòu)造root的右子樹

root.rchild=arraytotree(arr,mid+1,end)

else:

root=None

returnroot

defprintTreeLayer(root):

ifroot==None:

return

queue=deque()

#樹根結(jié)點進隊列

queue.append(root)

whilelen(queue)＞0:

p=queue.popleft()

#訪問當前結(jié)點

printp.data,

#如果這個結(jié)點的左孩子不為空則入隊列

ifp.lchild!=None:

queue.append(p.lchild)

#如果這個結(jié)點的右孩子不為空則入隊列

ifp.rchild!=None:

queue.append(p.rchild)

if__name__=="__main__":

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

root=arraytotree(arr,0,len(arr)-1)

print"二叉樹層序遍歷結(jié)果為:",

printTreeLayer(root)

print'\n'

reverseTree(root)

print"反轉(zhuǎn)后的二叉樹層序遍歷結(jié)果為:",

printTreeLayer(root)

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

二叉樹層序遍歷結(jié)果為：4261357

反轉(zhuǎn)后的二叉樹層序遍歷結(jié)果為：4627531

算法性能分析：

由于對給定的二叉樹進行了一次遍歷，因此，時間復(fù)雜度為O(N)。[考點]如何對二叉樹進行鏡像反轉(zhuǎn)

5.

給定一趟旅途旅程中所有的車票信息，根據(jù)這個車票信息找出這趟旅程的路線。例如：給定下面的車票：(“西安”到“成都”)，(“北京”到“上?！?，(“大連”到“西安”)，(“上?！钡健按筮B”)。那么可以得到旅程路線為：北京-＞上海，上海-＞大連，大連-＞西安，西安-＞成都。假定給定的車票不會有環(huán)，也就是說有一個城市只作為終點而不會作為起點。正確答案：對于這種題目，一般而言可以使用拓撲排序進行解答。根據(jù)車票信息構(gòu)建一個圖，然后找出這張圖的拓撲排序序列，這個序列就是旅程的路線。但這種方法的效率不高，它的時間復(fù)雜度為O(N)。這里重點介紹另外一種更加簡單的方法：hash法(python中可以使用字典實現(xiàn))。主要的思路為根據(jù)車票信息構(gòu)建一個字典，然后從這個字典中找到整個旅程的起點，接著就可以從起點出發(fā)依次找到下一站，進而知道終點。具體的實現(xiàn)思路為：

(1)根據(jù)車票的出發(fā)地與目的地構(gòu)建字典。

Tickets={("西安"到"成都"),("北京"到"上海"),("大連"到"西安"),("上海"到"大連")}

(2)構(gòu)建Tickets的逆向字典如下(將旅程的起始點反向)：

ReverseTickets={("成都"到"西安"),("上