Python程序員面試分類模擬10

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

給定任意一個正整數(shù)，求比這個數(shù)大且最小的“不重復數(shù)”，“不重復數(shù)”的含義是相鄰兩位不相同，例如1101是重復數(shù)，而1201是不重復數(shù)。正確答案：方法一（江南博哥）：蠻力法

最容易想到的方法就是對這個給定的數(shù)加1，然后判斷這個數(shù)是不是“不重復數(shù)”，如果不是，那么繼續(xù)加1，直到找到“不重復數(shù)”為止。顯然這種方法的效率非常低下。

方法二：從右到左的貪心法

例如給定數(shù)字11099，首先對這個數(shù)字加1，變?yōu)?1000，接著從右向左找出第一對重復的數(shù)字00，對這個數(shù)字加1，變?yōu)?1001，繼續(xù)從右向左找出下一對重復的數(shù)00，將其加1，同時把這一位往后的數(shù)字變?yōu)?101…串(當某個數(shù)字自增后，只有把后面的數(shù)字變成0101…，才是最小的不重復數(shù)字)，這個數(shù)字變?yōu)?1010，接著采用同樣的方法，11010-＞12010就可以得到滿足條件的數(shù)。

需要特別注意的是當對第i個數(shù)進行加1操作后可能會導致第i個數(shù)與第i+1個數(shù)相等，因此，需要處理這種特殊情況，下圖以99020為例介紹處理方法。

(1)把數(shù)字加1并轉(zhuǎn)換為字符串。

(2)從右到左找到第一組重復的數(shù)99(數(shù)組下標為i=2)，然后把99加1，變?yōu)?00，然后把后面的字符變?yōu)?101…串。得到100010。

(3)由于執(zhí)行步驟(2)后對下標為2的值進行了修改，導致它與下標為i=3的值相同，因此，需要對i自增變?yōu)閕=3，接著從i=3開始從右向左找出下一組重復的數(shù)字00，對00加1變?yōu)?1，后面的字符變?yōu)?101…串，得到100101。

(4)由于下標為i=3與i+1=4的值不同，因此，可以從i-1=2的位置開始從右向左找出下一組重復的數(shù)字00，對其加1就可以得到滿足條件的最小的“不重復數(shù)”。

根據(jù)這個思路給出實現(xiàn)方法如下：

1)對給定的數(shù)加1。

2)循環(huán)執(zhí)行如下操作：對給定的數(shù)從右向左找出第一對重復的數(shù)(下標為i)，對這個數(shù)字加1，然后把這個數(shù)字后面的數(shù)變?yōu)?101…得到新的數(shù)。如果操作結(jié)束后下標為i的值等于下標為i+1的值，那么對i進行自增，否則對i進行自減；然后從下標為i開始從右向左重復執(zhí)行步驟2)，直到這個數(shù)是“不重復數(shù)”為止。

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

"""

方法功能:處理數(shù)字相加的進位

輸入?yún)?shù):num為字符數(shù)組,pos為進行加1操作對應的下標位置

"""

defcarry(num,pos):

whilepos＞0:

ifint(num[pos])＞9:

num[pos]='0'

num[pos-1]=str(int(num[pos-1])+1)

pos-=1

"""

方法功能:獲取大于n的最小不重復數(shù)

輸入?yún)?shù):n為正整數(shù)

返回值:大于n的最小不重復數(shù)

"""

deffindMinNonDupNum(n):

count=0#用來記錄循環(huán)次數(shù)

nChar=list(str(n+1))

ch=[None]*(len(nChar)+2)

ch[0]='0'

ch[len(ch)-1]='0'

i=0

whilei＜len(nChar):

ch[i+1]=nChar[i]

i+=1

lens=len(ch)

i=lens-2#從右向左遍歷

whilei＞0:

count+=1

ifch[i-1]==ch[i]:

ch[i]=str(int(ch[i])+1)#末尾數(shù)字加1

carry(ch,i)#處理進位

#把下標為i后面的字符串變?yōu)?101…串

j=i+1

whilej＜lens:

if(j-i)%2==1:

ch[j]=0'

else:

ch[j]='1'

j+=1

#第i位加1后,可能會與第i+1位相等

i+=1

else:

i-=1

print"循環(huán)次數(shù)為:"+str(count)

returnint(".join(ch))

if__name__=="__main__":

printfindMinNonDupNum(23345)

printfindMinNonDupNum(1101010)

printfindMinNonDupNum(99010)

printfindMinNonDupNum(8989)

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

循環(huán)次數(shù)為：7

23401

循環(huán)次數(shù)為：11

1201010

循環(huán)次數(shù)為：13

101010

循環(huán)次數(shù)為：10

9010

方法三：從左到右的貪心法

與方法二類似，只不過是從左到右開始遍歷，如果碰到重復的數(shù)字，那么把其加1，后面的數(shù)字變成0101…串。實現(xiàn)代碼如下：

"""

方法功能:處理數(shù)字相加的進位

輸入?yún)?shù):num為字符數(shù)組,pos為進行加1操作對應的下標位置

"""

defcarry(num,pos):

whilepos＞0:

ifint(num[pos])＞9:

num[pos]='0'

num[pos-1]=str(int(num[pos-1])+1)

pos-=1

"""

方法功能:獲取大于n的最小不重復數(shù)

輸入?yún)?shù):n為正整數(shù)

返回值:大于n的最小不重復數(shù)

"""

deffindMinNonDupNum(n):

count=0#用來記錄循環(huán)次數(shù)

nChar=list(str(n+1))

ch=[None]*(len(nChar)+1)

ch[0]='0'

i=0

whilei＜len(nChar):

ch[i+1]=nChar[i]

i+=1

lens=len(ch)

i=2#從左向右遍歷

whilei＜lens:

count+=1

ifch[i-1]==ch[i]:

ch[i]=str(int(ch[i])+1)#末尾數(shù)字加1

carry(ch,i)#處理進位

#把下標為i后面的字符串變?yōu)?101...串

j=i+1

whilej＜lens:

if(j-i)%2==1:

ch[j]='0'

else:

ch[j]='1'

j+=1

else:

i+=1

print"循環(huán)次數(shù)為:"+str(count)

returnint(".join(ch))

if__name__=="__main__":

printfindMinNonDupNum(23345)

printfindMinNonDupNum(1101010)

printfindMinNonDupNum(99010)

printfindMinNonDupNum(8989)

顯然，方法三循環(huán)的次數(shù)少于方法二，因此，方法三的性能要優(yōu)于方法二。[考點]如何找最小的不重復數(shù)

2.

給定一個帶頭結(jié)點的單鏈表，請將其逆序。即如果單鏈表原來為head-＞1-＞2-＞3-＞4-＞5-＞6-＞7，那么逆序后變?yōu)閔ead-＞7-＞6-＞5-＞4-＞3-＞2-＞1。正確答案：由于單鏈表與數(shù)組不同，單鏈表中每個結(jié)點的地址都存儲在其前驅(qū)結(jié)點的指針域中，因此，對單鏈表中任何一個結(jié)點的訪問只能從鏈表的頭指針開始進行遍歷。在對鏈表的操作過程中，需要特別注意在修改結(jié)點指針域的時候，記錄下后繼結(jié)點的地址，否則會丟失后繼結(jié)點。

方法一：就地逆序

主要思路為：在遍歷鏈表的時候，修改當前結(jié)點的指針域的指向，讓其指向它的前驅(qū)結(jié)點。為此需要用一個指針變量來保存前驅(qū)結(jié)點的地址。此外，為了在調(diào)整當前結(jié)點指針域的指向后還能找到后繼結(jié)點，還需要另外一個指針變量來保存后繼結(jié)點的地址，在所有的結(jié)點都被保存好以后就可以直接完成指針的逆序了。除此之外，還需要特別注意對鏈表首尾結(jié)點的特殊處理。具體實現(xiàn)方式如下圖所示。

在上圖中，假設當前已經(jīng)遍歷到cur結(jié)點，由于它所有的前驅(qū)結(jié)點都已經(jīng)完成了逆序操作，因此，只需要使cur.next=pre即可完成逆序操作，在此之前，為了能夠記錄當前結(jié)點的后繼結(jié)點的地址，需要用一個額外的指針next來保存后繼結(jié)點的信息，通過上圖(1)～(4)四步把實線的指針調(diào)整為虛線的指針就可以完成當前結(jié)點的逆序。當前結(jié)點完成逆序后，通過向后移動指針來對后續(xù)的結(jié)點用同樣的方法進行逆序操作。算法實現(xiàn)如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

#方法功能:對單鏈表進行逆序輸入?yún)?shù):head:鏈表頭結(jié)點

defReverse(head):

#判斷鏈表是否為空

ifhead==Noneorhead.next==None:

return

pre=None#前驅(qū)結(jié)點

cur=None#當前結(jié)點

next=None#后繼結(jié)點

#把鏈表首結(jié)點變?yōu)槲步Y(jié)點

cur=head.next

next=cur.next

cur.next=None

pre=cur

cur=next

#使當前遍歷到的結(jié)點cur指向其前驅(qū)結(jié)點

whilecur.next!=Node:

next=cur.next

cur.next=pre

pre=cur

cur=cur.next

cur=next

#鏈表最后一個結(jié)點指向倒數(shù)第二個結(jié)點

cur.next=pre

#鏈表的頭結(jié)點指向原來鏈表的尾結(jié)點

head.next=cur

if__name__=="__main__".

i=1

#鏈表頭結(jié)點

head=LNode()

head.next=None

tmp=None

cur=head

#構(gòu)造單鏈表

whilei＜8:

tmp=LNode()

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

i+=1

print"逆序前:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

print"\n逆序后:",

Reverse(head)

cur=head.next

whilecur!=None:

printcur.data,

Cur=cur.next

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

逆序前：1234567

逆序后：7654321

算法性能分析：

以上這種方法只需要對鏈表進行一次遍歷，因此，時間復雜度為O(N)，其中，N為鏈表的長度。但是需要常數(shù)個額外的變量來保存當前結(jié)點的前驅(qū)結(jié)點與后繼結(jié)點，因此，空間復雜度為O(1)。

方法二：遞歸法

假定原鏈表為1-＞2-＞3-＞4-＞5-＞6-＞7，遞歸法的主要思路為：先逆序除第一個結(jié)點以外的子鏈表(將1-＞2-＞3-＞4-＞5-＞6-＞7變?yōu)?-＞7-＞6-＞5-＞4-＞3-＞2)，接著把結(jié)點1添加到逆序的子鏈表的后面(1-＞7-＞6-＞5-＞4-＞3-＞2變?yōu)?-＞6-＞5-＞4-＞3-＞2-＞1)。同理，在逆序鏈表2-＞3-＞4-＞5-＞6-＞7時，也是先逆序子鏈表3-＞4-＞5-＞6-＞7(逆序為2-＞7-＞6-＞5-＞4-＞3)，接著實現(xiàn)鏈表的整體逆序(2-＞7-＞6-＞5-＞4-＞3轉(zhuǎn)換為7-＞6-＞5-＞4-＞3-＞2)。實現(xiàn)代碼如下：

"""

方法功能:對不帶頭結(jié)點的單鏈表進行逆序

輸入?yún)?shù):firstRef:鏈表頭結(jié)點

"""

defRecursiveReverse(head):

#如果鏈表為空或者鏈表中只有一個元素

ifheadisNoneorhead.nextisNone:

returnhead

else:

#反轉(zhuǎn)后面的結(jié)點

newhead=RecursiveReverse(head.next)

#把當前遍歷的結(jié)點加到后面結(jié)點逆序后鏈表的尾部

head.next.next=head

head.next=None

returnnewhead

"""

方法功能:對帶頭結(jié)點的單鏈表進行逆序

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

"""

defReverse(head):

ifheadisNone:

return

#獲取鏈表第一個結(jié)點

firstNode=head.next

#對鏈表進行逆序

newhead=RecursiveReverse(firstNode)

#頭結(jié)點指向逆序后鏈表的第一個結(jié)點

head.next=newhead

returnnewhead

算法性能分析：

由于遞歸法也只需要對鏈表進行一次遍歷，因此，算法的時間復雜度也為O(N)，其中，N為鏈表的長度。遞歸法的主要優(yōu)點是：思路比較直觀，容易理解，而且也不需要保存前驅(qū)結(jié)點的地址。缺點是：算法實現(xiàn)的難度較大，此外，由于遞歸法需要不斷地調(diào)用自己，需要額外的壓棧與彈棧操作，因此，與方法一相比性能會有所下降。

方法三：插入法

插入法的主要思路為：從鏈表的第二個結(jié)點開始，把遍歷到的結(jié)點插入到頭結(jié)點的后面，直到遍歷結(jié)束。假定原鏈表為head-＞1＞2-＞3-＞4-＞5-＞6-＞7，在遍歷到2的時候，將其插入到頭結(jié)點后，鏈表變?yōu)閔ead-＞2-＞1＞3-＞4-＞5-＞6-＞7，同理將后序遍歷到的所有結(jié)點都插入到頭結(jié)點head后，就可以實現(xiàn)鏈表的逆序。實現(xiàn)代碼如下：

defReverse(head):

#判斷鏈表是否為空

ifheadisNoneorhead.nextisNone:

return

cur=None#當前結(jié)點

next=None#后繼結(jié)點

cur=head.next.next

#設置鏈表第一個結(jié)點為尾結(jié)點

head.next.next=None

#把遍歷到結(jié)點插入到頭結(jié)點的后面

whilecurisnotNone:

next=cur.next

cur.next=head.next

head.next=cur

cur=next

算法性能分析：

以上這種方法也只需要對單鏈表進行一次遍歷，因此，時間復雜度為O(N)，其中，N為鏈表的長度。與方法一相比，這種方法不需要保存前驅(qū)結(jié)點的地址，與方法二相比，這種方法不需要遞歸地調(diào)用，效率更高。[考點]如何實現(xiàn)鏈表的逆序

3.

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

fromcollectionsimportdeque

classUser:

def__init__(self,id,name):

self.id=id#唯一標識一個用戶

=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):#進入隊列尾部

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

self.q.append(u)

#隊頭出隊列

defdeQueue(self):

self.q.popleft()

self.updateSeq()

#隊列中的人隨機離開

defdeQueuemove(self,u):

self.q.remove(u)

self.updateSeq()

#出隊列后更新隊列中每個人的序列

defupdateSeq(self):

i=1

foruinself.q:

u.setSeq(i)

i+=1

#打印隊列的信息

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()#隊首元素u1出隊列

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

queue.printList()

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

id:2name:user2seq:1

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

4.

有N個磁盤，每個磁盤大小為D[i](i=0...N-1)，現(xiàn)在要在這N個磁盤上”順序分配”M個分區(qū)，每個分區(qū)大小為P[j](j=0…M-1)，順序分配的意思是：分配一個分區(qū)P[j]時，如果當前磁盤剩余空間足夠，則在當前磁盤分配；如果不夠，則嘗試下一個磁盤，直到找到一個磁盤D[i+k]可以容納該分區(qū)，分配下一個分區(qū)P[j+1]時，則從當前磁盤D[i+k]的剩余空間開始分配，不在使用D[i+k]之前磁盤末分配的空間，如果這M個分區(qū)不能在這N個磁盤完全分配，則認為分配失敗，請實現(xiàn)函數(shù)，isallocable判斷給定N個磁盤(數(shù)組D)和M個分區(qū)(數(shù)組P)，是否會出現(xiàn)分配失敗的情況?舉例：磁盤為[120,120,120]，分區(qū)為[60,60,80,20,80]可分配，如果為[60,80,80,20,80]，則分配失敗。正確答案：本題的主要思路如下：對所有的分區(qū)進行遍歷，同時用一個變量dIndex記錄上次分配磁盤的下標，初始化為0；對于每個分區(qū)，從上次分配的磁盤開始繼續(xù)分配，如果沒有足夠的空間，則順序找其他的磁盤，直到找到合適的磁盤為止，進行分配；如果找不到合適的磁盤，則分配失敗，實現(xiàn)代碼如下：

defis_allocable(d,p):

dIndex=0#磁盤分區(qū)下標

i=0

whilei＜len(p):

#找到符合條件的磁盤

whiledIndex＜len(d)andp[i]＞d[dIndex]:

dIndex+=1

#沒有可用的磁盤

ifdIndex＞=len(d):

returnFalse

#給分區(qū)分配磁盤

d[dIndex]-=p[i]

i+=1

returnTrue

if__name__=="__main__":

d=[120,120,120]#磁盤

p=[60,60,80,20,80]#分區(qū)

ifis_allocable(d,p):

print"分配成功"

else:

print"分配失敗"

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

分配成功

算法性能分析：

這種方法使用了雙重循環(huán)，因此，時間復雜度為O(MN)。[考點]如何對磁盤分區(qū)

5.

把一個有序數(shù)組最開始的若干個元素搬到數(shù)組的末尾，稱之為數(shù)組的旋轉(zhuǎn)。輸入一個排好序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組[3,4,5,1,2]為數(shù)組[1,2,3,4,5]的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。正確答案：Python中可以使用列表來表示有序數(shù)組，因此示例中都用列表來表示有序數(shù)組。

其實這是一個非?；竞统Ｓ玫臄?shù)組操作，它的描述如下：

有一個數(shù)組X[0...n-1]，現(xiàn)在把它分為兩個子數(shù)組：x1[0...m]和x2[m+1...n-1]，交換這兩個子數(shù)組，使數(shù)組x由x1x2變成x2x1，例如x=[1,2,3,4,5,6,7,8,9]，x1=[1,2,3,4,5],x2=[6,7,8,9]，交換后，x=[6,7,8,9,1,2,3,4,5]。

對于本題的解決方案，最容易想到的，也是最簡單的方法就是直接遍歷法。但是這種方法顯然沒有用到題目中旋轉(zhuǎn)數(shù)組的特性，因此，它的效率比較低下，下面介紹一種比較高效的二分查找法。

通過數(shù)組的特性可以發(fā)現(xiàn)，數(shù)組元素首先是遞增的，然后突然下降到最小值，然后再遞增。雖然如此，但是還有下面三種特殊情況需要注意：

(1)數(shù)組本身是沒有發(fā)生過旋轉(zhuǎn)的，是一個有序的數(shù)組，例如序列[1,2,3,4,5,6]。

(2)數(shù)組中元素值全部相等，例如序列[1,1,1,1,1,1]。

(3)數(shù)組中元素值大部分都相等，例如序列[1,0,1,1,1,1]。

通過旋轉(zhuǎn)數(shù)組的定義可知，經(jīng)過旋轉(zhuǎn)之后的數(shù)組實際上可以劃分為兩個有序的子數(shù)組，前面的子數(shù)組的元素值都大于或者等于后面子數(shù)組的元素值?？梢愿鶕?jù)數(shù)組元素的這個特點，采用二分查找的思想不斷縮小查找范圍，最終找出問題的解決方案，具體實現(xiàn)思路如下所示：

按照二分查找的思想，給定數(shù)組arr，首先定義兩個變量low和high，分別表示數(shù)組的第一個元素和最后一個元素的下標。按照題目中對旋轉(zhuǎn)規(guī)則的定義，第一個元素應該是大于或者等于最后一個元素的(當旋轉(zhuǎn)個數(shù)為0，即沒有旋轉(zhuǎn)的時候，要單獨處理，直接返回數(shù)組第一個元素)。接著遍歷數(shù)組中間的元素arr[mid]，其中mid=(high+low)/2。

(1)如果arr[mid]＜arr[mid-1]，則arr[mid]一定是最小值；

(2)如果arr[mid+1]＜arr[mid]，則arr[mid+1]一定是最小值；

(3)如果arr[high]＞arr[mid]，則最小值一定在數(shù)組左半部分；

(4)如果arr[mid]＞arr[low]，則最小值一定在數(shù)組右半部分；

(5)如果arr[low]==arr[mid]且arr[high]==arr[mid]，則此時無法區(qū)分最小值是在數(shù)組的左半部分還是右半部分(例如：[2,2,2,2,1,2]，[2,1,2,2,2,2,2])。在這種情況下，只能分別在數(shù)組的左右兩部分找最小值minL與minR，最后求出minL與minR的最小值。

示例代碼如下：