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

如何用兩個棧模擬隊(duì)列操作正確答案：題目要求用兩個棧來模擬隊(duì)列，假設(shè)使用棧A與棧B模擬隊(duì)列Q，A為插入棧，B為彈出棧，以實(shí)現(xiàn)隊(duì)列Q。

再假設(shè)A和B都為空，可（江南博哥）以認(rèn)為棧A提供入隊(duì)列的功能，棧B提供出隊(duì)列的功能。

要入隊(duì)列，入棧A即可，而出隊(duì)列則需要分兩種情況考慮：

(1)如果棧B不為空，則直接彈出棧B的數(shù)據(jù)。

(2)如果棧B為空，則依次彈出棧A的數(shù)據(jù)，放入棧B中，再彈出棧B的數(shù)據(jù)。

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

classStack:

#模擬棧

def__init__(self):

self.items=[]

#判斷棧是否為空

defempty(self):

returnlen(self.items)==0

#返回棧的大小

defsize(self):

returnlen(self.items)

#返回棧項(xiàng)元素

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)

classMyStack:

def__init__(self):

self.A=Stack()#用來存儲棧中元素

self.B=Stack()#用來存儲當(dāng)前棧中最小的元素

defpush(self,data):

self.A.push(data)

defpop(self):

ifself,B.empty():

whilenotself.A.empty():

self.B.push(self.A.peek())

self.A.pop()

first=self.B.peek()

self.B.pop()

returnfirst

if__name__=="__main__":

stack=MyStack()

stack.push(1)

stack.push(2)

print"隊(duì)列首元素為:"+str(stack.pop())

print"隊(duì)列首元素為:"+str(stack.pop())

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

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

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

算法性能分析：

這種方法入隊(duì)列操作的時間復(fù)雜度為O(1)，出隊(duì)列操作的時間復(fù)雜度則依賴于入隊(duì)列與出隊(duì)列執(zhí)行的頻率?？傮w來講，出隊(duì)列操作的時間復(fù)雜度為O(1)，當(dāng)然會有個別操作需要耗費(fèi)更多的時間(因?yàn)樾枰獜膬蓚€棧之間傳輸數(shù)據(jù))。[考點(diǎn)]如何用兩個棧模擬隊(duì)列操作

2.

請設(shè)計一個排隊(duì)系統(tǒng)，能夠讓每個進(jìn)入隊(duì)伍的用戶都能看到自己在隊(duì)列中所處的位置和變化，隊(duì)伍可能隨時有人加入和退出；當(dāng)有人退出影響到用戶的位置排名時需要及時反饋到用戶。正確答案：本題不僅要實(shí)現(xiàn)隊(duì)列常見的入隊(duì)列與出隊(duì)列的功能，而且還需要實(shí)現(xiàn)隊(duì)列中任意一個元素都可以隨時出隊(duì)列，且出隊(duì)列后需要更新隊(duì)列用戶位置的變化。實(shí)現(xiàn)代碼如下：

fromcollectionsimportdeque

classUser:

def__init__(self,id,name):

self.id=id#唯一標(biāo)識一個用戶

=name

self.seq=0

defgetName(self):

return

defsetName(self,name):

=name

defgetSeq(self):

returnself.seq

defsetSeq(self,seq):

self.seq=seq

defgetId(self):

returnself.id

defequals(self,arg0):

o=arg0

returnself.id=o.getId()

deftoString(self):

return"id:"+str(self.id)+"name:"++"seq:"+str(self.seq)

classMyQueue:

def__init__(self):

self.q=deque()

defenQueue(self,u):#進(jìn)入隊(duì)列尾部

u.setSeq(len(self.q)+1)

self.q.append(u)

#隊(duì)頭出隊(duì)列

defdeQueue(self):

self.q.popleft()

self.updateSeq()

#隊(duì)列中的人隨機(jī)離開

defdeQueuemove(self,u):

self.q.remove(u)

self.updateSeq()

#出隊(duì)列后更新隊(duì)列中每個人的序列

defupdateSeq(self):

i=1

foruinself.q:

u.setSeq(i)

i+=1

#打印隊(duì)列的信息

defprintList(self):

foruinself.q:

printu.toString()

if__name__=="__main__":

u1=User(1,"user1")

u2=User(2,"user2")

u3=User(3,"user3")

u4=User(4,"user4")

queue=MyQueue()

queue.enQueue(u1)

queue.enQueue(u2)

queue.enQueue(u3)

queue.enQueue(u4)

queue.deQueue()#隊(duì)首元素u1出隊(duì)列

queue.deQueuemove(u3)#隊(duì)列中間的元素u3出隊(duì)列

queue.printList()

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

id:2name:user2seq:1

id:4name:user4seq:2[考點(diǎn)]如何設(shè)計一個排序系統(tǒng)

3.

LRU是LeastRecentlyUsed的縮寫，它的意思是“最近最少使用”，LRU緩存就是使用這種原理實(shí)現(xiàn)，簡單的說就是緩存一定量的數(shù)據(jù)，當(dāng)超過設(shè)定的閾值時就把一些過期的數(shù)據(jù)刪除掉。常用于頁面置換算法，是虛擬頁式存儲管理中常用的算法。如何實(shí)現(xiàn)LRU緩存方案?正確答案：我們可以使用兩個數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)一個LRU緩存。

(1)使用雙向鏈表實(shí)現(xiàn)的隊(duì)列，隊(duì)列的最大容量為緩存的大小。在使用過程中，把最近使用的頁面移動到隊(duì)列頭，最近沒有使用的頁面將被放在隊(duì)列尾的位置。

(2)使用一個哈希表，把頁號作為鍵，把緩存在隊(duì)列中的結(jié)點(diǎn)的地址作為值。

當(dāng)引用一個頁面時，如果所需的頁面在內(nèi)存中，只需要把這個頁對應(yīng)的結(jié)點(diǎn)移動到隊(duì)列的前面。如果所需的頁面不在內(nèi)存中，此時需要把這個頁面加載到內(nèi)存中。簡單地說，就是將一個新結(jié)點(diǎn)添加到隊(duì)列的前面，并在哈希表中更新相應(yīng)的結(jié)點(diǎn)地址。如果隊(duì)列是滿的，那么就從隊(duì)列尾部移除一個結(jié)點(diǎn)，并將新結(jié)點(diǎn)添加到隊(duì)列的前面。實(shí)現(xiàn)代碼如下：

fromcollectionsimportdeque

classLRU:

def__init__(self,cacheSize):

self.cacheSize=cacheSize

self.queue=deque()

self.hashSet=set()

#判斷緩存隊(duì)列是否已滿

defisQueueFull(self):

returnlen(self.queue)==self.cacheSize

#把頁號為pageNum的頁緩存到隊(duì)列中,同時也添加到Hash表中

defenqueue(self,pageNum):

#如果隊(duì)列滿了,需要刪除隊(duì)尾的緩存的頁

ifself.isQueueFull():

self.hashSet.remove(self.queue[-1])

self.queue.pop()

self.queue.appendleft(pageNum)

#把新緩存的結(jié)點(diǎn)同時添加到hash表中

self.hashSet.add(pageNum)

"""

當(dāng)訪問某一個page的時候會調(diào)用這個函數(shù)，對于訪問的page有兩種情況：

1.如果page在緩存隊(duì)列中，直接把這個結(jié)點(diǎn)移動到隊(duì)首

2.如果page不在緩存隊(duì)列中，把這個page緩存到隊(duì)首。

"""

defaccessPage(self,pageNum):

#page不在緩存隊(duì)列中,把它緩存到隊(duì)首

ifpageNumnotinself.hashSet:

self.enqueue(pageNum)

#page已經(jīng)在緩存隊(duì)列中了,移動到隊(duì)首

elifpageNum!=self.queue[0]:

self.queue.remove(pageNum)

self.queue.appendleft(pageNum)

defprintQueue(self):

whilelen(self.queue)＞0:

printself.queue.popleft(),

if__name__="__main__":

#假設(shè)緩存大小為3

1ru=LRU(3)

#訪問page

1ru.accessPage(1)

1ru.accessPage(2)

1ru.accessPage(5)

1ru.accessPage(1)

1ru.accessPage(6)

1ru.accessPage(7)

#通過上面的訪問序列后，緩存的信息為

1ru.printQueue()

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

761[考點(diǎn)]如何實(shí)現(xiàn)LRU緩存方案

4.

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

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

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

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

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

(3)遍歷Tickets，對于遍歷到的key值，判斷這個值是否在ReverseTickets中的key中存在，如果不存在，那么說明遍歷到的Tickets中的key值就是旅途的起點(diǎn)。例如：“北京”在ReverseTickets的key中不存在，因此“北京”就是旅途的起點(diǎn)。

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

defprintResult(inputs):

#用來存儲把input的鍵與值調(diào)換后的信息

reverseInput=dict()

fork,vininputs.items():

reverseInput[v]=k

start=None

#找到起點(diǎn)

fork,vininputs.items():

ifknotinreverseInput:

start=k

break

ifstart==None:

print"輸入不合理"

return

#從起點(diǎn)出發(fā)按照順序遍歷路徑

to=inputs[start]

printstart+"-＞"+to,

stan=to

to=inputs[to]

whileto!=None:

print","+Start+"-＞"+to,

start=to

to=inputs[to]

if__name__=="__main__":

inputs=dict()

inputs["西安"]="成都"

inputs["北京"]="上海"

inputs["大連"]="西安"

inputs["上海"]="大連"

printResult(inputs)

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

北京-＞上海,上海-＞大連,大連-＞西安,西安-＞成都

算法性能分析：

這種方法的時間復(fù)雜度為O(N)，空間復(fù)雜度也為O(N)。[考點(diǎn)]如何從給定的車票中找出旅程

5.

給定一個數(shù)組，找出數(shù)組中是否有兩個數(shù)對(a,b)和(c,d)，使得a+b=c+d，其中，a、b、c和d是不同的元素。如果有多個答案，打印任意一個即可。例如給定數(shù)組：[3,4,7,10,20,9,8]，可以找到兩個數(shù)對(3,8)和(4,7)，使得3+8=4+7。正確答案：最簡單的方法就是使用四重遍歷，對所有可能的數(shù)對，判斷是否滿足題目要求，如果滿足則打印出來，但是這種方法的時間復(fù)雜度為O(N4)，很顯然不滿足要求。下面介紹另外一種方法——字典法，算法的主要思路為：以數(shù)對為單位進(jìn)行遍歷，在遍歷過程中，把數(shù)對和數(shù)對的值存儲在字典中(鍵為數(shù)對的和，值為數(shù)對)，當(dāng)遍歷到一個鍵值對時，如果它的和在字典中已經(jīng)存在，那么就找到了滿足條件的鍵值對。下面使用字典為例給出實(shí)現(xiàn)代碼：

#用來存儲數(shù)對

classpair:

def__init__(self,first,second):

self.first=None

self.second=None