Python程序員面試分類模擬6

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

設(shè)計一個程序，當(dāng)輸入一個字符串時，要求輸出這個字符串的所有排列。例如輸入字符串a(chǎn)bc，要求輸出由字符a、b、c所能排列出來的所有字符串：abc，acb，bac，（江南博哥）bca，cba，cab。正確答案：這道題主要考察對遞歸的理解，可以采用遞歸的方法來實現(xiàn)。當(dāng)然也可以使用非遞歸的方法來實現(xiàn)，但是與遞歸法相比，非遞歸法難度增加了很多。下面分別介紹這兩種方法。

方法一：遞歸法

下面以字符串a(chǎn)bc為例介紹對字符串進行全排列的方法。具體步驟如下：

(1)首先固定第一個字符a，然后對后面的兩個字符b與c進行全排列；

(2)交換第一個字符與其后面的字符，即交換a與b，然后固定第一個字符b，接著對后面的兩個字符a與c進行全排列；

(3)由于第(2)步交換了a和b破壞了字符串原來的順序，因此，需要再次交換a和b使其恢復(fù)到原來的順序，然后交換第一個字符與第三個字符(交換a和c)，接著固定第一個字符c，對后面的兩個字符a與b求全排列。

在對字符串求全排列的時候就可以采用遞歸的方式來求解，實現(xiàn)方法如下圖所示：

在使用遞歸方法求解的時候，需要注意以下兩個問題：(1)逐漸縮小問題的規(guī)模，并且可以用同樣的方法來求解子問題；(2)遞歸一定要有結(jié)束條件，否則會導(dǎo)致程序陷入死循環(huán)。本題目遞歸方法實現(xiàn)代碼如下：

#交換字符數(shù)組下標(biāo)為i和j對應(yīng)的字符

defswap(str,i,j):

tmp=str[i]

str[i]=str[j]

str[j]=tmp

"""

方法功能:對字符串中的字符進行全排列

輸入?yún)?shù):str為待排序的字符串,start為待排序的子字符串的首字符下標(biāo)

"""

defPermutation(str,start):

ifstr==Noneorstart＜0:

return

#完成全排列后輸出當(dāng)前排列的字符串

ifstart==len(str)-1:

print".join(str),

else:

i=start

whilei＜len(str):

#交換start與i所在位置的字符

swap(str,start,i)

#固定第一個字符,對剩余的字符進行全排列

Permutation(str,start+1)

#還原start與i所在位置的字符

swap(str,start,i)

i+=1

defPermutation_transe(s):

str=list(s)

Permutation(str,0)

if__name__=="__main__":

s="abc"

Permutation_transe(s)

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

abcacbbacbcacbacab

算法性能分析：

假設(shè)這種方法需要的基本操作數(shù)為f(n)，那么f(n)=n*f(n-1)=n*(n-1)*f(n-2)…=n!。所以，算法的時間復(fù)雜度為O(n!)。算法在對字符進行交換的時候用到了常量個指針變量，因此，算法的空間復(fù)雜度為O(1)。

方法二：非遞歸法

遞歸法比較符合人的思維，因此，算法的思路以及算法實現(xiàn)都比較容易。下面介紹另外一種非遞歸的方法。算法的主要思想為：從當(dāng)前字符串出發(fā)找出下一個排列(下一個排列為大于當(dāng)前字符串的最小字符串)。

通過引入一個例子來介紹非遞歸算法的基本思想：假設(shè)要對字符串“12345”進行排序。第一個排列一定是“12345”，依此獲取下一個排列："12345"-＞"12354"-＞"12435"-＞"12453"-＞"12534"＞"12543"-＞"13245"-＞…。從“12543”->“13245”可以看出找下一個排列的主要思路為：(1)從右到左找到兩個相鄰遞增(從左向右看是遞增的)的字符串，例如“12543”，從右到左找出第一個相鄰遞增的子串為“25”；記錄這個小的字符的下標(biāo)為pmin；(2)找出pmin后面的比它大的最小的字符進行交換，在本例中‘2’后面的子串中比它大的最小的字符為‘3’，因此，交換‘2’和‘3’得到字符串“13542”；(3)為了保證下一個排列為大于當(dāng)前字符串的最小字符串，在第(2)步中完成交換后需要對pmin后的子串重新組合，使其值最小，只需對pmin后面的字符進行逆序即可(因為此時pmin后面的子字符串中的字符必定是按照降序排列，逆序后字符就按照升序排列了)，逆序后就能保證當(dāng)前的組合是新的最小的字符串。在這個例子中，上一步得到的字符串為“13542”，pmin指向字符‘3’，對其后面的子串“542”逆序后得到字符串“13245”；(4)當(dāng)找不到相鄰遞增的子串時，說明找到了所有的組合。

需要注意的是，這種方法適用于字符串中的字符是按照升序排列的情況。因此，非遞歸方法的主要思路為：(1)首先對字符串進行排序(按字符進行升序排列)；(2)依次獲取當(dāng)前字符串的下一個組合直到找不到相鄰遞增的子串為止。實現(xiàn)代碼如下：

#交換字符數(shù)組下標(biāo)為i和j對應(yīng)的字符

defswap(str,i,j):

tmp=str[i]

str[i]=str[j]

str[j]=tmp

"""

方法功能:翻轉(zhuǎn)字符串

輸入?yún)?shù):begin與end分別為字符串的第一個字符與最后一個字符的下標(biāo)

"""

defReverse(str,begin,end):

i=begin

j=end

whilei＜j:

swap(str,i,j)

i+=1

j-=1

"""

方法功能:根據(jù)當(dāng)前字符串的組合

輸入?yún)?shù):str:字符數(shù)組

返回值:還有下一個組合返回True,否則返回False

"""

defgetNextPermutation(str):

end=len(str)-1#字符串最后一個字符的下標(biāo)

cur=end#用來從后向前遍歷字符串

suc=0#cur的后繼

tmp=0

whilecur!=0:

#從后向前開始遍歷字符串

suc=cur

cur-=1

ifstr[cur]＜str[suc]:

#相鄰遞增的字符,cur指向較小的字符

#找出cur后面最小的字符tmp

tmp=end

whilestr[tmp]＜str[cur]:

tmp-=1

#交換cur與tmp

swap(str,cur,tmp)

#把cur后面的子字符串進行翻轉(zhuǎn)

Reverse(str,suc,end)

returnTrue

returnFalse

"""

方法功能:獲取字符串中字符的所有組合

輸入?yún)?shù):str:字符數(shù)組

"""

defPermutation(s):

ifs==Noneorlen(s)＜1:

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

return

str=list(s)

str.sort()#升序排列字符數(shù)組

printstr

print".join(str),

whilegetNextPermutation(str):

print".join(str),

if__name__=="__main__":

s="abc"

Permutation(s)

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

abcacbbacbcacabcba

算法性能分析：

首先對字符串進行排序的時間復(fù)雜度為O(n2)，接著求字符串的全排列，由于長度為n的字符串全排列個數(shù)為n!，因此Permutation函數(shù)中的循環(huán)執(zhí)行的次數(shù)為n!，循環(huán)內(nèi)部調(diào)用函數(shù)getNextPermutation，getNextPermutation內(nèi)部用到了雙重循環(huán)，因此它的時間復(fù)雜度為O(n2)。所以求全排列算法的時間復(fù)雜度為O(n!*n2)。[考點]如何求一個字符串的所有排列

2.

給定一個整數(shù)，輸出這個整數(shù)的二進制表示中1的個數(shù)。例如：給定整數(shù)7，其二進制表示為111，因此輸出結(jié)果為3。正確答案：方法一：移位法

可以采用位操作來完成。具體思路如下：首先，判斷這個數(shù)的最后一位是否為1，如果為1，那么計數(shù)器加1，然后，通過右移丟棄掉最后一位，循環(huán)執(zhí)行該操作直到這個數(shù)等于0為止。在判斷二進制表示的最后一位是否為1時，可以采用與運算來達到這個目的。具體實現(xiàn)代碼如下：

#判斷n二進制碼中1的個數(shù)

defcountOne(n):

count=0#用來計數(shù)

whilen＞0:

if(n&1)==1:#判斷最后一位是否為1

count+=1

n＞＞1#移位丟掉最后一位

returncount

if__name__=="__main__":

printcountOne(7)

printcountOne(8)

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

3

1

算法性能分析：

這種方法的時間復(fù)雜度為O(N)，其中N代表二進制數(shù)的位數(shù)。

方法二：與操作法

給定一個數(shù)n，每進行一次n&(n-1)計算，其結(jié)果中都會少了一位1，而且是最后一位。例如，n=6，其對應(yīng)的二進制表示為110，n-1=5，對應(yīng)的二進制表示為101，n&(n-1)運算后的二進制表示為100，其效果就是去掉了110中最后一位1?？梢酝ㄟ^不斷地用n&(n-1)操作去掉n中最后一位1的方法求出n中1的個數(shù)，實現(xiàn)代碼如下：

defcountOne(n):

count=0#用來計數(shù)

whilen＞0:

ifn!=0:#判斷最后一位是否為1

n=n&(n-1)

count+=1

returncount

if__name__=="__main__":

printcountOne(7)

printcountOne(8)

算法性能分析：

這種方法的時間復(fù)雜度為O(m)，其中m為二進制數(shù)中1的個數(shù)，顯然當(dāng)二進制數(shù)中1的個數(shù)比較少的時候，這種方法有更高的效率。[考點]如何求二進制數(shù)中1的個數(shù)

3.

假設(shè)給定鏈表1-＞2-＞3-＞4-＞5-＞6-＞7中指向第5個元素的指針，要求把結(jié)點5刪掉，刪除后鏈表變?yōu)?-＞2-＞3-＞4-＞6-＞7。正確答案：一般而言，要刪除單鏈表中的一個結(jié)點p，首先需要找到結(jié)點p的前驅(qū)結(jié)點pre，然后通過pre.next=p.next來實現(xiàn)對結(jié)點p的刪除。對于本題而言，由于無法獲取到結(jié)點p的前驅(qū)結(jié)點，因此，不能采用這種傳統(tǒng)的方法。

那么如何解決這個問題呢?可以分如下兩種情況來分析：

(1)如果這個結(jié)點是鏈表的最后一個結(jié)點，那么無法刪除這個結(jié)點。

(2)如果這個結(jié)點不是鏈表的最后一個結(jié)點，可以通過把其后繼結(jié)點的數(shù)據(jù)復(fù)制到當(dāng)前結(jié)點中，然后刪除后繼結(jié)點的方法來實現(xiàn)。實現(xiàn)方法如下圖所示：

在上圖中，首先把結(jié)點p的后繼結(jié)點的數(shù)據(jù)復(fù)制到結(jié)點p的數(shù)據(jù)域中；接著把結(jié)點p的后繼結(jié)點刪除。實現(xiàn)代碼如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

defprintList(head):

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

"""

方法功能:給定單鏈表中某個結(jié)點,刪除該結(jié)點

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

返回值:true:刪除成功;false:刪除失敗

"""

defRemoveNode(p):

#如果結(jié)點為空,或結(jié)點p無后繼結(jié)點則無法刪除

ifp==Noneorp.next==None:

returnFalse

p.data=p.next.data

tmp=p.next

p.next=tmp.next

returnTrue

if__name__=="__main__":

i=1

head=LNode()#鏈表頭結(jié)點

head.next=None

tmp=None

cur=head

p=None

#構(gòu)造鏈表

whilei＜8:

tmp=LNode()

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

ifi=5:

p=tmp

i+=1

print"刪除結(jié)點"+str(p.data)+"前鏈表:",

printList(head)

result=RemoveNode(p)

ifresult:

print"\n刪除該結(jié)點后鏈表:",

printList(head)

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

刪除結(jié)點5前鏈表：1234567

刪除該結(jié)點后鏈表：123467

算法性能分析：

由于這種方法不需要遍歷鏈表，只需要完成一個數(shù)據(jù)復(fù)制與結(jié)點刪除的操作，因此，時間復(fù)雜度為O(1)。由于這種方法只用了常數(shù)個額外指針變量，因此，空間復(fù)雜度也為O(1)。[考點]如何在只給定單鏈表中某個結(jié)點的指針的情況下刪除該結(jié)點

4.

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

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

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

示例代碼如下：

classMyQueue:

def__init__(self):

self.arr=[]

self.front=0#隊列頭

self.rear=0#隊列尾

#判斷隊列是否為空

defisEmpty(self):

returnself.front==self.rear

#返回隊列的大小

defsize(self):

returnself.rear-self.front

#返回隊列首元素

defgetFront(self):

ifself.isEmpty():

returnNone

returnself.arr[self.front]

#返回隊列尾元素

defgetBack(self):

ifself.isEmpty():

returnNone

returnself.arr[self.rear-1]

#刪除隊列頭元素

defdeQueue(self):

ifself.rear＞self.front:

self.front+=1

else:

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

#把新元素加入隊列尾

defenQueue(self,item):

self.arr.append(item)

self.rear+=1

if__name__=="__main__":

queue=MyQueue()

queue.enQueue(1)

queue.enQueue(2)

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

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

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

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

隊列頭元素為：1

隊列尾元素為：2

隊列大小為：2

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

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

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

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

classLNode:

def__new__(self,x):

self.data=x

self.next=None

classMyQueue:

#分配頭結(jié)點

def__init__(self):

self.pHead=None

self.pEnd=None

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

defempty(self):

ifself.pHead=None:

returnTrue

else:

returnFalse

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

defsize(self):

size=()

p=self.pHead

whilep!=None:

p=p.next

size+=1

returnsize

#入隊列:把元素e加到隊列尾

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

#出隊列,刪除隊列首元素

defdeQueue(self):

ifself.pHead==None:

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

self.pHead=self.pHead.next

ifself.pHead==None:

self.pEnd=None

#取得隊列首元素

defgetFront(self):

ifself.pHead==None:

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

returnNone

returnself.pHead.data

#取得隊列尾元素

defgetBack(self):

ifself.pEnd==None:

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

returnNone

returnself.pEnd.data

if__name__="__main__":

queue=MyQueue()

queue.enQueue(1)

queue.enQueue(2)

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

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

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

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

隊列頭元素為：1

隊列尾元素為：2

隊列大小為：2

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

5.

如何判斷一個數(shù)是否為2的n次方?正確答案：方法一：構(gòu)造法

2的