Python程序員面試分類(lèi)真題3

Python程序員面試分類(lèi)真題31.

實(shí)現(xiàn)一個(gè)棧的數(shù)據(jù)結(jié)構(gòu)，使其具有以下方法：壓棧、彈棧、取棧頂元素、判斷棧是否為空以及獲取棧中元素個(gè)數(shù)。正確答案：棧的實(shí)現(xiàn)有兩種方法，分別為采用數(shù)組來(lái)實(shí)現(xiàn)和采用鏈表（江南博哥）來(lái)實(shí)現(xiàn)。下面分別詳細(xì)介紹這兩種方法。

方法一：數(shù)組實(shí)現(xiàn)

在采用數(shù)組來(lái)實(shí)現(xiàn)棧的時(shí)候，?？臻g是一段連續(xù)的空間。實(shí)現(xiàn)思路如下圖所示。

從上圖中可以看出，可以把數(shù)組的首元素當(dāng)做棧底，同時(shí)記錄棧中元素的個(gè)數(shù)size，假設(shè)數(shù)組首地址為arr，從上圖可以看出，壓棧的操作其實(shí)是把待壓棧的元素放到數(shù)組arr[size]中，然后執(zhí)行size+操作；同理，彈棧操作其實(shí)是取數(shù)組arr[size-1]元素，然后執(zhí)行size-操作。根據(jù)這個(gè)原理可以非常容易實(shí)現(xiàn)棧，示例代碼如下：

classMyStack:

#模擬棧

def__init__(self):

self.items=[]

#撐判斷棧是否為空

defisEmpty(self):

returnlen(self.items)==0

#返回棧的大小

defsize(self):

returnlen(self.items)

#返回棧頂元素

deftop(self):

ifnotself.isEmpty():

returnelf.items[len(self.items)-1]

else:

returnNone

#彈棧

defpop(self):

iflen(self.items)＞0:

returnself.items.pop()

else:

print"棧已經(jīng)為空"

returnNone

#壓棧

defpush(self,item):

self.items.append(item)

if__name__=="__main__":

s=MyStack()

s.push(4)

print"棧頂元素為:"+str(s.top())

print"棧大小為:"+str(s.size())

s.pop()

prmt"彈棧成功"

s.pop()

方法二：鏈表實(shí)現(xiàn)

在創(chuàng)建鏈表的時(shí)候經(jīng)常采用一種從頭結(jié)點(diǎn)插入新結(jié)點(diǎn)的方法，可以采用這種方法來(lái)實(shí)現(xiàn)棧，最好使用帶頭結(jié)點(diǎn)的鏈表，這樣可以保證對(duì)每個(gè)結(jié)點(diǎn)的操作都是相同的，實(shí)現(xiàn)思路如下圖所示。

在上圖中，在進(jìn)行壓棧操作的時(shí)候，首先需要?jiǎng)?chuàng)建新的結(jié)點(diǎn)，把待壓棧的元素放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后只需要(1)和(2)兩步就實(shí)現(xiàn)了壓棧操作(把新結(jié)點(diǎn)加到了鏈表首部)。同理，在彈棧的時(shí)候，只需要進(jìn)行(3)的操作就可以刪除鏈表的第一個(gè)元素，從而實(shí)現(xiàn)彈棧操作。實(shí)現(xiàn)代碼如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

classMyStack:

def__init__(self):

#pHead=LNode()

self.data=None

self.nexFNone

#判斷stack是否為空,如果為空返回true,否則返回false

defempty(self):

ifself.next==None:

returnTrue

else:

returnFalse

#獲取棧中元素的個(gè)數(shù)

defsize(self):

size=0

p=self.next

whilep!=None:

p=p.next

size+=1

returnsize

#入棧:把e放到棧頂

defpush(self,e):

p=LNode

p.data=e

p.next=self.next

self.next=p

#出棧,同時(shí)返回棧頂元素

defpop(self):

tmp=self.next

iftmp!=None:

self.next=tmp.next

returntmp.data

print"棧已經(jīng)為空"

returnNone

#取得棧頂元素

deftop(self):

ifself.next!=None:

returnself.next.data

print"棧已經(jīng)為空"

returnNone

if__name__=="__main__":

stack=MyStack()

stack.push(1)

print"棧頂元素為:"+str(stack.top())

print"棧大小為:"+str(stack.size())

stack.pop()

print"彈棧成功"

stack.pop()

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

棧頂元素為：1

棧大小為：1

彈棧成功

棧已經(jīng)為空

兩種方法的對(duì)比：

采用數(shù)組實(shí)現(xiàn)棧的優(yōu)點(diǎn)是：一個(gè)元素值占用一個(gè)存儲(chǔ)空間；它的缺點(diǎn)為：如果初始化申請(qǐng)的存儲(chǔ)空間太大，會(huì)造成空間的浪費(fèi)，如果申請(qǐng)的存儲(chǔ)空間太小，后期會(huì)經(jīng)常需要擴(kuò)充存儲(chǔ)空間，擴(kuò)充存儲(chǔ)空間是個(gè)費(fèi)時(shí)的操作，這樣會(huì)造成性能的下降。

采用鏈表實(shí)現(xiàn)棧的優(yōu)點(diǎn)是：使用靈活方便，只有在需要的時(shí)候才會(huì)申請(qǐng)空間。它的缺點(diǎn)為：除了要存儲(chǔ)元素外，還需要額外的存儲(chǔ)空間存儲(chǔ)指針信息。

算法性能分析：

這兩種方法壓棧與彈棧的時(shí)間復(fù)雜度都為O(1)。[考點(diǎn)]如何實(shí)現(xiàn)棧

2.

實(shí)現(xiàn)一個(gè)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，使其具有入隊(duì)列、出隊(duì)列、查看隊(duì)列首尾元素、查看隊(duì)列大小等功能。正確答案：與實(shí)現(xiàn)棧的方法類(lèi)似，隊(duì)列的實(shí)現(xiàn)也有兩種方法，分別為采用數(shù)組來(lái)實(shí)現(xiàn)和采用鏈表來(lái)實(shí)現(xiàn)。下面分別詳細(xì)介紹這兩種方法。

方法一：數(shù)組實(shí)現(xiàn)

下圖給出了一種最簡(jiǎn)單的實(shí)現(xiàn)方式，用front來(lái)記錄隊(duì)列首元素的位置，用rear來(lái)記錄隊(duì)列尾元素往后一個(gè)位置。入隊(duì)列的時(shí)候只需要將待入隊(duì)列的元素放到數(shù)組下標(biāo)為rear的位置，同時(shí)執(zhí)行rear+，出隊(duì)列的時(shí)候只需要執(zhí)行front+即可。

示例代碼如下：

classMyQueue:

def__init__(self):

self.arr=[]

self.front=0#隊(duì)列頭

self.rear=0#隊(duì)列尾

#判斷隊(duì)列是否為空

defisEmpty(self):

returnself.front==self.rear

#返回隊(duì)列的大小

defsize(self):

returnself.rear-self.front

#返回隊(duì)列首元素

defgetFront(self):

ifself.isEmpty():

returnNone

returnself.arr[self.front]

#返回隊(duì)列尾元素

defgetBack(self):

ifself.isEmpty():

returnNone

returnself.arr[self.rear-1]

#刪除隊(duì)列頭元素

defdeQueue(self):

ifself.rear＞self.front:

self.front+=1

else:

print"隊(duì)列已經(jīng)為空"

#把新元素加入隊(duì)列尾

defenQueue(self,item):

self.arr.append(item)

self.rear+=1

if__name__=="__main__":

queue=MyQueue()

queue.enQueue(1)

queue.enQueue(2)

print"隊(duì)列頭元素為:"+str(queue.getFront())

print"隊(duì)列尾元素為:"+str(queue.getBack())

print"隊(duì)列大小為:"+str(queue.size())

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

隊(duì)列頭元素為：1

隊(duì)列尾元素為：2

隊(duì)列大小為：2

以上這種實(shí)現(xiàn)方法最大的缺點(diǎn)為：出隊(duì)列后數(shù)組前半部分的空間不能被充分地利用，解決這個(gè)問(wèn)題的方法為把數(shù)組看成一個(gè)環(huán)狀的空間(循環(huán)隊(duì)列)。當(dāng)數(shù)組最后一個(gè)位置被占用后，可以從數(shù)組首位置開(kāi)始循環(huán)利用，具體實(shí)現(xiàn)方法可以參考數(shù)據(jù)結(jié)構(gòu)的課本。

方法二：鏈表實(shí)現(xiàn)

采用鏈表實(shí)現(xiàn)隊(duì)列的方法與實(shí)現(xiàn)棧的方法類(lèi)似，分別用兩個(gè)指針指向隊(duì)列的首元素與尾元素，如下圖所示。用pHead來(lái)指向隊(duì)列的首元素，用pEnd來(lái)指向隊(duì)列的尾元素。

在上圖中，剛開(kāi)始隊(duì)列中只有元素1、2和3，當(dāng)新元素4要進(jìn)隊(duì)列的時(shí)候，只需要上圖中(1)和(2)兩步，就可以把新結(jié)點(diǎn)連接到鏈表的尾部，同時(shí)修改pEnd指針指向新增加的結(jié)點(diǎn)。出隊(duì)列的時(shí)候只需要步驟(3)，改變pHead指針使其指向pHead.next，此外也需要考慮結(jié)點(diǎn)所占空間釋放的問(wèn)題。在入隊(duì)列與出隊(duì)列的操作中也需要考慮隊(duì)列尾空的時(shí)候的特殊操作，實(shí)現(xiàn)代碼如下所示：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

classMyQueue:

#分配頭結(jié)點(diǎn)

def__init__(self):

self.pHead=None

self.pEnd=None

#判斷隊(duì)列是否為空,如果為空返回true,否則返回false

defempty(self):

ifself.pHead=None:

returnTrue

else:

returnFalse

#獲取棧中元素的個(gè)數(shù)

defsize(self):

size=()

p=self.pHead

whilep!=None:

p=p.next

size+=1

returnsize

#入隊(duì)列:把元素e加到隊(duì)列尾

defenQueue(self,e):

p=LNode()

p.data=e

p.next=None

ifself.pHead==None:

self.pHead=self.pEnd=p

else:

self.pEnd.next=p

selfpEnd=p

#出隊(duì)列,刪除隊(duì)列首元素

defdeQueue(self):

ifself.pHead==None:

print"出隊(duì)列失敗,隊(duì)列已經(jīng)為空"

self.pHead=self.pHead.next

ifself.pHead==None:

self.pEnd=None

#取得隊(duì)列首元素

defgetFront(self):

ifself.pHead==None:

print"獲取隊(duì)列首元素失敗,隊(duì)列已經(jīng)為空"

returnNone

returnself.pHead.data

#取得隊(duì)列尾元素

defgetBack(self):

ifself.pEnd==None:

print"獲取隊(duì)列尾元素失敗,隊(duì)列已經(jīng)為空"

returnNone

returnself.pEnd.data

if__name__="__main__":

queue=MyQueue()

queue.enQueue(1)

queue.enQueue(2)

print"隊(duì)列頭元素為:"+str(queue.getFront())

print"隊(duì)列尾元素為:"+str(queue.getBack())

print"隊(duì)列大小為:"+str(queue.size())

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

隊(duì)列頭元素為：1

隊(duì)列尾元素為：2

隊(duì)列大小為：2

顯然用鏈表來(lái)實(shí)現(xiàn)隊(duì)列有更好的靈活性，與數(shù)組的實(shí)現(xiàn)方法相比，它多了用來(lái)存儲(chǔ)結(jié)點(diǎn)關(guān)系的指針空間。此外，也可以用循環(huán)鏈表來(lái)實(shí)現(xiàn)隊(duì)列，這樣只需要一個(gè)指向鏈表最后一個(gè)元素的指針即可，因?yàn)橥ㄟ^(guò)指向鏈表尾元素可以非常容易地找到鏈表的首結(jié)點(diǎn)。[考點(diǎn)]如何實(shí)現(xiàn)隊(duì)列

3.

翻轉(zhuǎn)(也叫顛倒)棧的所有元素，例如輸入棧{1，2，3，4，5}，其中，1處在棧頂，翻轉(zhuǎn)之后的棧為{5，4，3，2，1}，其中，5處在棧頂。正確答案：最容易想到的辦法是申請(qǐng)一個(gè)額外的隊(duì)列，先把棧中的元素依次出棧放到隊(duì)列里，然后把隊(duì)列里的元素按照出隊(duì)列順序入棧，這樣就可以實(shí)現(xiàn)棧的翻轉(zhuǎn)，這種方法的缺點(diǎn)是需要申請(qǐng)額外的空間存儲(chǔ)隊(duì)列，因此，空間復(fù)雜度較高。下面介紹一種空間復(fù)雜度較低的遞歸的方法。

遞歸程序有兩個(gè)關(guān)鍵因素需要注意：遞歸定義和遞歸終止條件。經(jīng)過(guò)分析后，很容易得到該問(wèn)題的遞歸定義和遞歸終止條件。遞歸定義：將當(dāng)前棧的最底元素移到棧頂，其他元素順次下移一位，然后對(duì)不包含棧頂元素的子棧進(jìn)行同樣的操作。終止條件：遞歸下去，直到棧為空。遞歸的調(diào)用過(guò)程如下圖所示：

在上圖中，對(duì)于棧{1，2，3，4，5}，進(jìn)行翻轉(zhuǎn)的操作為：首先把棧底元素移動(dòng)到棧頂?shù)玫綏5，1，2，3，4}，然后對(duì)不包含棧頂元素的子棧進(jìn)行遞歸調(diào)用(對(duì)子棧元素進(jìn)行翻轉(zhuǎn))，子棧{1，2，3，4}翻轉(zhuǎn)的結(jié)果為{4，3，2，l}，因此，最終得到翻轉(zhuǎn)后的棧為{5，4，3，2，1}。

此外，由于棧的后進(jìn)先出的特點(diǎn)，使得只能取棧頂?shù)脑?，因此，要把棧底的元素移?dòng)到棧頂也需要遞歸調(diào)用才能完成，主要思路為：把不包含該棧頂元素的子棧的棧底的元素移動(dòng)到子棧的棧頂，然后把棧頂?shù)脑嘏c子棧棧頂?shù)脑?其實(shí)就是與棧頂相鄰的元素)進(jìn)行交換。

為了更容易理解遞歸調(diào)用，可以認(rèn)為在進(jìn)行遞歸調(diào)用的時(shí)候，子棧已經(jīng)把棧底元素移動(dòng)到了棧頂，在上圖中，為了把棧{1，2，3，4，5}的棧底元素5移動(dòng)到棧頂，首先對(duì)子棧{2，3，4，5}，進(jìn)行遞歸調(diào)用，調(diào)用的結(jié)果為{5，2，3，4}，然后對(duì)子棧頂元素5，與棧頂元素1進(jìn)行交換得到棧{5，1，2，3，4)，實(shí)現(xiàn)了把棧底元素移動(dòng)到棧頂。

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

#Python中沒(méi)有棧的模塊,所以先新建一個(gè)棧類(lèi)

classStack:

#模擬棧

def__init__(self):

self.items=[]

#判斷棧是否為空

defempty(self):

returnlen(self.items)==0

#返回棧的大小

defsize(self):

returnlen(self.items)

#返回棧頂元素

defpeek(self):

ifnotself.empty():

returnself.items[len(self.items)-1]

else:

returnNone

#彈棧

defpop(self):

iflen(self.items)＞0:

returnself.items.pop()

else:

priiit"棧已經(jīng)為空"

returnNone

#壓棧

defpush(self,item):

self.items.append(item)

"""

方法功能:把棧底元素移動(dòng)到棧頂

參數(shù):s棧的引用

"""

defmoveBottomToTop(s):

ifs.empty():

return

top1=s.peek()

s.pop()#彈出棧項(xiàng)元素

ifnots.empty():

#遞歸處理不包含棧頂元素的子棧

moveBottomToTop(s)

top2=s.peek()

s.pop()

#交換棧頂元素與予棧棧頂元素

s.push(top1)

s.push(top2)

else:

s.push(top1)

defreverse_stack(s):

ifs.empty():

return

#把棧底元素移動(dòng)到棧頂

moveBottomToTop(s)

top=s.peek()

s.pop()

#遞歸處理子棧

reverse_stack(s)

s.push(top)

if__name__=="__main__":

s=Stack()

s.push(5)

s.push(4)

s.push(3)

s.push(2)

s.push(1)

reverse_stack(s)

print"翻轉(zhuǎn)后出棧順序?yàn)?",

whilenots.empty():

prints.peek(),

s.pop()

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

翻轉(zhuǎn)后出棧順序?yàn)椋?4321

算法性能分析：

把棧底元素移動(dòng)到棧頂操作的時(shí)間復(fù)雜度為O(N)，在翻轉(zhuǎn)操作中對(duì)每個(gè)子棧都進(jìn)行了把棧底元素移動(dòng)到棧頂?shù)牟僮鳎虼?，翻轉(zhuǎn)算法的時(shí)間復(fù)雜度為O(N2)。[考點(diǎn)]如何翻轉(zhuǎn)棧的所有元素

4.

輸入兩個(gè)整數(shù)序列，其中一個(gè)序列表示棧的push(入)順序，判斷另一個(gè)序列有沒(méi)有可能是對(duì)應(yīng)的pop(出)順序。正確答案：假如輸入的push序列是1、2、3、4、5，那么3、2、5、4、1就有可能是一個(gè)pop序列，但5、3、4、1、2就不可能是它的一個(gè)pop序列。

主要思路是使用一個(gè)棧來(lái)模擬入棧順序，具體步驟如下：

(1)把push序列依次入棧，直到棧頂元素等于pop序列的第一個(gè)元素，然后棧頂元素出棧，pop序列移動(dòng)到第二個(gè)元素；

(2)如果棧頂繼續(xù)等于pop序列現(xiàn)在的元素，則繼續(xù)出棧并pop后移；否則對(duì)push序列繼續(xù)入棧。

(3)如果push序列已經(jīng)全部入棧，但是pop序列未全部遍歷，而且棧頂元素不等于當(dāng)前pop元素，那么這個(gè)序列不是一個(gè)可能的出棧序列。如果棧為空，而且pop序列也全部被遍歷過(guò)，則說(shuō)明這是一個(gè)可能的pop序列。下圖給出一個(gè)合理的pop序列的判斷過(guò)程。

在上圖中，(1)～(3)三步，由于棧頂元素不等于pop序列第一個(gè)元素3，因此，1，2，3依次入棧，當(dāng)3入棧后，棧頂元素等于pop序列的第一個(gè)元素3，因此，第(4)步執(zhí)行3出棧，接下來(lái)指向第二個(gè)pop序列2，且棧頂元素等于pop序列的當(dāng)前元素，因此，第(5)步執(zhí)行2出棧；接著由于棧頂元素4不等于當(dāng)前pop序列5，因此，接下來(lái)(6)和(7)兩步分別執(zhí)行4和5入棧；接著由于棧頂元素5等于pop序列的當(dāng)前值，因此，第(8)步執(zhí)行5出棧，接下來(lái)(9)和(10)兩步棧項(xiàng)元素都等于當(dāng)前pop序列的元素，因此，都執(zhí)行出棧操作。最后由于棧為空，同時(shí)pop序列都完成了遍歷，因此，{3，2，5，4，1}是一個(gè)合理的出棧序列。

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

classStack:

#模擬棧

def__init__(self):

selfitems=[]

#判斷棧是否為空

defempty(self):

returnlen(self.items)==0

#返回棧的大小

defsize(self):

returnlen(self.items)

#返回棧頂元素

defpeek(self):

ifnotself.empty():

returnself.items[len(self.items)-1]

else:

returnNone

#彈棧

defpop(self):

iflen(self.items)＞0:

returnself.items.pop()

else:

print"棧已經(jīng)為空"

returnNone

#壓棧

defpush(self,item):

self.items.append(item)

defisPopSerial(push,pop):

ifpush==Noneorpop==None:

returnFalse

pushLen=len(push)

popLen=len(pop)

ifpushLen!=popLen:

returnFalse

pushIndex=0

popIndex=0

stack=Stack()

whilepushIndex＜pushLen:

#把push序列依次入棧,直到棧頂元素等于pop序列的第一個(gè)元素

stack.push(push[pushIndex])

pushIndex+=1

#棧頂元素出棧,pop序列移動(dòng)到下一個(gè)元素

while(notstack.empty())andstack.peek()==pop[popIndex]:

stack.pop()

popIndex+=1

#棧為空,且pop序列中元素都被遍歷過(guò)

returnstack.empty()andpopIndex==popLen

if__name__=="__main__":

push="12345"

pop="32541"

ifisPopSerial(push,pop):

printpop+"是"+push+"的一個(gè)pop序列"

else:

printpop+"不是"+push+"的一個(gè)pop序列"

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

32541是12345的一個(gè)pop序列

算法性能分析：

這種方法在處理一個(gè)合理的pop序列的時(shí)候需要操作的次數(shù)最多，即把push序列進(jìn)行一次壓棧和出棧操作，操作次數(shù)為2N，因此，時(shí)間復(fù)雜度為O(N)，此外，這種方法使用了額外的?？臻g，因此，空間復(fù)雜度為O(N)。[考點(diǎn)]如何根據(jù)入棧序列判斷可能的出棧序列

5.

如何用O(1)的時(shí)間復(fù)雜度求棧中最小元素正確答案：由于棧具有后進(jìn)先出的特點(diǎn)，因此，push和pop只需要對(duì)棧頂元素進(jìn)行操作。如果使用上述的實(shí)現(xiàn)方式，只能訪(fǎng)問(wèn)到棧頂?shù)脑?，無(wú)法得到棧中最小的元素。當(dāng)然，可以用另外一個(gè)變量來(lái)記錄棧底的位置，通過(guò)遍歷棧中所有的元素找出最小值，但是這種方法的時(shí)間復(fù)雜度為O(N)，那么如何才能用O(1)的時(shí)間復(fù)雜度求出棧中最小的元素呢?

在算法設(shè)計(jì)中，經(jīng)常會(huì)采用空間換取時(shí)間的方式來(lái)提高時(shí)間復(fù)雜度，也就是說(shuō)，采用額外的存儲(chǔ)空間來(lái)降低操作的時(shí)間復(fù)雜度。具體而言，在實(shí)現(xiàn)的時(shí)候使用兩個(gè)棧結(jié)構(gòu)，一個(gè)棧用來(lái)存儲(chǔ)數(shù)據(jù)，另外一個(gè)棧用來(lái)存儲(chǔ)棧的最小元素。實(shí)現(xiàn)思路如下：如果當(dāng)前入棧的元素比原來(lái)?xiàng)Ｖ械淖钚≈颠€小，則把這個(gè)值壓入保存最小元素的棧中；在出棧的時(shí)候，如果當(dāng)前出棧的元素恰好為當(dāng)前棧中的最小值，保存最小值的棧頂元素也出棧，使得當(dāng)前最小值變?yōu)楫?dāng)前最小值入棧之前的那個(gè)最小值。為了簡(jiǎn)單起見(jiàn)，可以在棧中保存int類(lèi)型。

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

#模擬棧

classStack:

def__init__(self):

self.items=[]

#判斷棧是否為空

defempty(self):

returnlen(self.items)==0

#返回棧的大小

defsize(self):

returnlen(setf.items)

#返回棧頂元素

defpeek(self):

ifnotself.empty():

returnself.items[len(self.items)-1]

else:

returnNone

#彈棧

defpop(self):

iflen(self.