Python程序員面試分類真題12

Python程序員面試分類真題12(總分：100.00，做題時間：90分鐘)面試題(總題數(shù)：6，分數(shù)：100.00)1.

設(shè)計一個程序，當輸入一個字符串時，要求輸出這個字符串的所有排列。例如輸入字符串a(chǎn)bc，要求輸出由字符a、b、c所能排列出來的所有字符串：abc，acb，bac，bca，cba，cab。

（分數(shù)：16.50）__________________________________________________________________________________________

正確答案：(這道題主要考察對遞歸的理解，可以采用遞歸的方法來實現(xiàn)。當然也可以使用非遞歸的方法來實現(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ù)組下標為i和j對應(yīng)的字符

defswap(str,i,j):

tmp=str[i]

str[i]=str[j]

str[j]=tmp

"""

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

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

"""

defPermutation(str,start):

ifstr==Noneorstart＜0:

return

#完成全排列后輸出當前排列的字符串

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)都比較容易。下面介紹另外一種非遞歸的方法。算法的主要思想為：從當前字符串出發(fā)找出下一個排列(下一個排列為大于當前字符串的最小字符串)。

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

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

#交換字符數(shù)組下標為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分別為字符串的第一個字符與最后一個字符的下標

"""

defReverse(str,begin,end):

i=begin

j=end

whilei＜j:

swap(str,i,j)

i+=1

j-=1

"""

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

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

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

"""

defgetNextPermutation(str):

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

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.

找出兩個字符串的最長公共子串，例如字符串“abccade”與字符串“dgcadde”的最長公共子串為“cad”。

（分數(shù)：16.50）__________________________________________________________________________________________

正確答案：(對于這道題而言，最容易想到的方法就是采用蠻力法，假設(shè)字符串s1與s2的長度分別為len1和len2(假設(shè)len1＞=len2)，首先可以找出s2的所有可能的子串，然后判斷這些子串是否也是s1的子串，通過這種方法可以非常容易地找出兩個字符串的最長子串。當然，這種方法的效率是非常低下的，主要原因為：s2中的大部分字符需要與s1進行很多次的比較。那么是否有更好的方法來減少比較的次數(shù)呢?下面介紹兩種通過減少比較次數(shù)從而降低時間復(fù)雜度的方法。

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

通過把中間的比較結(jié)果記錄下來，從而可以避免字符的重復(fù)比較。主要思路如下：

首先定義二元函數(shù)f(，j)：表示分別以s1[i]，s2[j]結(jié)尾的公共子串的長度，顯然，f(0，j)=0(j≥0)，f(i，0)=0(i≥0)，那么，對于f(i+1，j+1)而言，則有如下兩種取值：

(1)f(i+1，j+1)=0，當str1[i+1]!=str2[j+1]時；

(2)f(i+1，j+1)=f(i，j)+1，當str1[i+1]==str2[j+1]時；

根據(jù)這個公式可以計算出f(i，j)(0≤i≤len(s1)，0≤j≤len(s2))所有的值，從而可以找出最長的子串，如下圖所示。

通過上圖所示的計算結(jié)果可以求出最長公共子串的長度max與最長子串結(jié)尾字符在字符數(shù)組中的位置maxI，由這兩個值就可以唯一確定一個最長公共子串為“cad”。這個子串在數(shù)組中的起始下標為：maxI-max=3，子串長度為max=3。實現(xiàn)代碼如下：

"""

方法功能:獲取兩個字符串的最長公共字串

輸入?yún)?shù):str1和str2為指向字符的指針

"""

defgetMaxSubStr(str1,str2):

len1=len(str1)

len2=len(str2)

sb="

maxs=0#maxs用來記錄最長公共字串的長度

maxI=0#用來記錄最長公共字串最后一個字符的位置

#申請新的空間來記錄公共字串長度信息

M=[([None]*(len1+1))foriinrange(len2+1)]

i=0

whilei＜len1+1:

M[i][0]=0

i+=1

j=0

whilej＜len2+1:

M[0][j]=0

j+=1

#通過利用遞歸公式填寫新建的二維數(shù)組(公共字串的長度信息)

i=1

whilei＜len1+1:

j=1

whilej＜len2+1:

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

M[i][j]=M[i-1][j-1]+1

ifM[i][j]＞maxs:

maxs=M[i][j]

maxI=i

else:

M[i][j]=0

j+=1

i+=1

#找出公共字串

i=maxI-maxs

whilei＜maxI:

sb=sb+list(str1)[i]

i+=1

returnsb

if__name__=="__main__":

str1="abccade"

str2="dgcadde"

printgetMaxSubStr(str1,str2)

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

cad

算法性能分析：

由于這種方法使用了二重循環(huán)分別遍歷兩個字符數(shù)組，因此時間復(fù)雜度為O(m*n)(其中，m和n分別為兩個字符串的長度)。此外，由于這種方法申請了一個m*n的二維數(shù)組，因此，算法的空間復(fù)雜度也為O(m*n)。很顯然，這種方法的主要缺點為申請了m*n個額外的存儲空間。

方法二：滑動比較法

如下圖所示，這種方法的主要思路為：保持s1的位置不變，然后移動s2，接著比較它們重疊的字符串的公共子串(記錄最大的公共子串的長度maxLen以及最長公共子串在s1中結(jié)束的位置maxLenEnd1)，在移動的過程中，如果當前重疊子串的長度大于maxLen，那么更新maxLen為當前重疊子串的長度。最后通過maxLen和maxLenEnd1就可以找出它們最長的公共子串。實現(xiàn)方法如下圖所示：

如上圖所示，這兩個字符串的最長公共子串為“bc”，實現(xiàn)代碼如下：

defgetMaxSubStr(s1,s2):

len1=len(s1)

len2=len(s2)

maxLen=0

tmpMaxLen=0

maxLenEnd1=0

sb="

i=0

whilei＜len1+len2:

s1begin=s2begin=0

tmpMaxLen=0

ifi＜len1:

slbegin=len1-i

else:

s2begin=i-len1

j=0

while(s1begin+j＜len1)and(s2begin+j＜len2):

iflist(s1)[s1begin+j]==list(s2)[s2begin+j]:

tmpMaxLen+=1

else:

if(tmpMaxLen＞maxLen):

maxLen=tmpMaxLen

maxLenEnd1=s1begin+j

else:

tmpMaxLen=0

j+=1

iftmpMaxLen＞maxLen:

maxLen=tmpMaxLen

maxLenEnd1=s1begin+j

i+=1

i=maxLenEnd1-maxLen

whilei＜maxLenEnd1:

sb=sb+list(s1)[i]

i+=1

returnsb

if__name__=="__main__":

str1="abccade"

str2="dgcadde"

printgetMaxSubStr(str1,str2)

算法性能分析：

這種方法用雙重循環(huán)來實現(xiàn)，外層循環(huán)的次數(shù)為m+n(其中，m和n分別為兩個字符串的長度)，內(nèi)層循環(huán)最多執(zhí)行n次，算法的時間復(fù)雜度為O((m+n)*n)。此外，這種方法只使用了幾個臨時變量，因此算法的空間復(fù)雜度為O(1)。)解析：[考點]如何求兩個字符串的最長公共子串3.

實現(xiàn)字符串的反轉(zhuǎn)，要求不使用任何系統(tǒng)方法，且時間復(fù)雜度最小。

（分數(shù)：16.50）__________________________________________________________________________________________

正確答案：(字符串的反轉(zhuǎn)主要通過字符的交換來實現(xiàn)，需要首先把字符串轉(zhuǎn)換為字符數(shù)組，然后定義兩個索引分別指向數(shù)組的首尾，再交換兩個索引位置的值，同時把兩個索引的值向中間移動，直到兩個索引相遇為止，則完成了字符串的反轉(zhuǎn)。根據(jù)字符交換方法的不同，可以采用如下兩種實現(xiàn)方法。

方法一：臨時變量法

最常用的交換兩個變量的方法為：定義一個中間變量來交換兩個值，主要思路為：假如要交換a與b，通過定義一個中間變量temp來實現(xiàn)變量的交換：temp=a;a=b;b=a。實現(xiàn)代碼如下：

defreverseStr(str):

ch=list(str)

lens=len(ch)

i=0

j=lens-1

whilei＜j:

tmp=ch[i]

ch[i]=ch[j]

ch[j]=tmp

i+=1

j-=1

return".join(ch)

if__name__=="__main__":

str="abcdefg"

print"字符串"+str+"翻轉(zhuǎn)后為:",

printreverseStr(str)

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

字符串a(chǎn)bcdefg翻轉(zhuǎn)后為：gfedcba

算法性能分析：

這種方法只需要對字符數(shù)組變量遍歷一次，因此時間復(fù)雜度為O(N)(N為字符串的長度)。

方法二：直接交換法

在交換兩個變量的時候，另外一種常用的方法為異或的方法，這種方法主要基于如下的特性：a^a=0、a^0=a以及異或操作滿足交換律與結(jié)合律。假設(shè)要交換兩個變量a與b，則可以采用如下方法實現(xiàn)：

a=a^b:

b=a^b;//b=a^b=(a^b)^b=a^(b^b)=a^0=a

a=a^b;//a=a^b=(a^b)^a=(b^a)^a=b^(a^a)=b^0=b

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

defreverseStr(strs):

ch=list(strs)

lens=len(ch)

i=0

j=lens-1

whilei＜j:

#Python中不能直接對字符串進行異或操作,所以借助ord和chr函數(shù)。

ch[i]=chr(ord(ch[i])^ord(ch[j]))

ch[j]=chr(ord(ch[i])^ord(ch[j]))

ch[i]=chr(ord(ch[i])^ord(ch[j]))

i+=1

j-=1

return".join(ch)

算法性能分析：

這種方法只需要對字符數(shù)組遍歷一次，因此時間復(fù)雜度為O(N)(N為字符串的長度)。與方法一相比，這種方法在實現(xiàn)字符交換的時候不需要額外的變量。)解析：[考點]如何對字符串進行反轉(zhuǎn)4.

換位字符串是指組成字符串的字符相同，但位置不同。例如：由于字符串“aaaabbc”與字符串“abcbaaa”就是由相同的字符所組成的，因此它們是換位字符。

（分數(shù)：16.50）__________________________________________________________________________________________

正確答案：(在算法設(shè)計中，經(jīng)常會采用空間換時間的方法以降低時間復(fù)雜度，即通過增加額外的存儲空間來達到優(yōu)化算法性能的目的。就本題而言，假設(shè)字符串中只使用ASCH字符，由于ASCII字符共有256個(對應(yīng)的編碼為0～255)，在實現(xiàn)的時候可以通過申請大小為256的數(shù)組來記錄各個字符出現(xiàn)的個數(shù)，并將其初始化為0，然后遍歷第一個字符串，將字符對應(yīng)的ASCII碼值作為數(shù)組下標，把對應(yīng)數(shù)組的元素加1，然后遍歷第二個字符串，把數(shù)組中對應(yīng)的元素值減1。如果最后數(shù)組中各個元素的值都為0，那么說明這兩個字符串是由相同的字符所組成的；否則，這兩個字符串是由不同的字符所組成的。實現(xiàn)代碼如下：

"""

方法功能:判斷兩個字符串是否為換位字符串

輸入?yún)?shù):s1與s2為兩個字符串

返回值:如果是返回true,否則返回false

"""

defcompare(s1,s2):

result=True

bCount=[None]*256

i=0

whilei＜256:

bCount[i]=0

i+=1

i=0

whilei＜len(s1):

bCount[ord(list(s1)[i])-ord('0')]+=1

i+=1

i=0

whilei＜len(s2):

bCount[ord(list(s2)[i])-ord('O')]-=1

i+=1

i=0

whilei＜256:

ifbCount[i]!=0:

result=False

break;

i+=1

returnresult;

if__name__=="__main__":

str1="aaaabbc";

str2="abcbaaa";

printstr1+"和"+str2,

ifcompare(str1,str2):

print"是換位字符"

else:

print"不是換位字符"

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

aaaabbc和abcbaaa是換位字符

算法性能分析：

這種方法的時間復(fù)雜度為O(N)。)解析：[考點]如何判斷兩個字符串是否為換位字符串5.

給定由字母組成的字符串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”。

（分數(shù)：16.50）__________________________________________________________________________________________

正確答案：(方法一：直接法

最直接的方法就是對于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: