Python程序員面試分類真題13

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

給定一個如下格式的字符串：(1,(2,3),(4,(5,6),7))，括號內(nèi)的元素可以是數(shù)字，也可以是另一個括號，實現(xiàn)一個算法消除嵌套的括號，例如把上面的表達(dá)式變成(1,2,3,4,5,6,7)，如果表達(dá)式有誤，那么報錯。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(從問題描述可以看出，這道題要求實現(xiàn)兩個功能：一個是判斷表達(dá)式是否正確，另一個是消除表達(dá)式中嵌套的括號。對于判定表達(dá)式是否正確這個問題，可以從如下幾個方面來入手：首先，表達(dá)式中只有數(shù)字、逗號和括號這幾種字符，如果有其他的字符出現(xiàn)，那么是非法表達(dá)式。其次，判斷括號是否匹配，如果碰到‘(’，那么把括號的計數(shù)器的值加上1；如果碰到‘)’，那么判斷此時計數(shù)器的值，如果計數(shù)器的值大于1，那么把計數(shù)器的值減去1，否則為非法表達(dá)式，當(dāng)遍歷完表達(dá)式后，括號計數(shù)器的值為0，則說明括號是配對出現(xiàn)的，否則括號不配對，表達(dá)式為非法表達(dá)式。對于消除括號這個問題，可以通過申請一個額外的存儲空間，在遍歷原字符串的時候把除了括號以外的字符保存到新申請的額外的存儲空間中，這樣就可以去掉嵌套的括號了。需要特別注意的是，字符串首尾的括號還需要保存。實現(xiàn)代碼如下：

#方法功能:去掉字符串中嵌套的括號

defremoveNestedPare(strs):

ifstrs==None:

returnstrs

Parentheses_num=0#用來記錄不匹配的"("出現(xiàn)的次數(shù)

iflist(strs)[0]!='('orlist(strs)[-1]!=')':

returnNone

sb='('

#字符串首尾的括號可以單獨處理

i=1

whilei＜len(strs)-1:

ch=list(strs)[i]

ifch=='(:

Parentheses_num+=1

elifch==')':

Parentheses_num-=1

else:

sb=sb+(list(strs)[i])

i+=1

#判斷括號是否匹配

ifParentheses_num!=0:

print"由于括號不匹配,因此不做任何操作"

returnNone

#處理字符串結(jié)尾的")"

sb=sb+')'

returnsb

if__name__=="__main__":

strs="(1,(2,3),(4,(5,6),7))"

printstrs+"去除嵌套括號后為:"+removeNestedPare(strs)

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

(1,(2,3),(4,(5,6),7))去除嵌套括號后為：(1,2,3,4,5,6,7)

算法性能分析：

這種方法對字符串進(jìn)行了一次遍歷，因此時間復(fù)雜度為O(N)(其中，N為字符串的長度)。此外，這種方法申請了額外的N+1個存儲空間，因此空間復(fù)雜度也為O(N)。)解析：[考點]如何消除字符串的內(nèi)嵌括號。2.

寫一個方法，檢查字符串是否是整數(shù)，如果是整數(shù)，那么返回其整數(shù)值。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(整數(shù)分為負(fù)數(shù)與非負(fù)數(shù)，負(fù)數(shù)只有一種表示方法，而非負(fù)數(shù)可以有兩種表示方法。例如：-123，123，+123。因此在判斷字符串是否為整數(shù)的時候，需要把這幾個問題都考慮到。下面主要介紹兩種方法。

方法一：遞歸法

對于整數(shù)而言，例如123，可以看成12*10+3，而12又可以看成1*10+2。而-123可以看成(-12)*10-3，-12可以被看成(-1)*10-2。根據(jù)這個特點可以采用遞歸的方法來求解，可以首先根據(jù)字符串的第一個字符確定整數(shù)的正負(fù)，接著對字符串從右往左遍歷，假設(shè)字符串為“c1c2c3…cn”，如果cn不是整數(shù)，那么這個字符串不能表示成整數(shù)；如果這個數(shù)是非負(fù)數(shù)(c1!='-')，那么這個整數(shù)的值為“c1c2c3…cn-1”對應(yīng)的整數(shù)值乘以10加上cn對應(yīng)的整數(shù)值，如果這個數(shù)是負(fù)數(shù)(c1=='-')，那么這個整數(shù)的值為c1c2c3%…cn-1對應(yīng)的整數(shù)值乘以10減去cn對應(yīng)的整數(shù)值。而求解子字符串“c1c2c3…sc-1”對應(yīng)的整數(shù)的時候，可以用相同的方法來求解，因此可以采用遞歸的方法來求解。對于“+123”，可以首先去掉“+”，然后處理方法與“123”相同。由此可以得到遞歸表達(dá)式為：

c1=='-'?toint("c1c2c3…cn-1")*10-(cn-'0'):toint("c1c2c3…cn-1")*10+(cn-'0')。

遞歸的結(jié)束條件為：當(dāng)字符串長度為1時，直接返回字符對應(yīng)的整數(shù)的值。實現(xiàn)代碼如下：

classTest:

def__init__(self):

self.flag=None

defgetFlag(self):returnself.flag

#判斷c是否是數(shù)字,如果是返回True,否則返回False

defisNumber(self,c):

returnc＞='0'andc＜='9'

"""

判斷str是否是數(shù)字,如果是返回數(shù)字,且設(shè)置flag=True,否則設(shè)置flag=False

輸入?yún)?shù):str為字符數(shù)組,length為數(shù)組長度,flag表示str是否是數(shù)字

"""

defstrtoint(selt,strs,length):

iflength＞1:

ifnotself.isNumber(list(strs)[length-1]):

#不是數(shù)字

print"不是數(shù)字"

self.flag=False

return-1

iflist(strs)[0]=='-':

returnself.strtoint(strs,length-1)*10-(ord(list(strs)[length-1])-ord('0'))

else:

returnself.strtoint(strs,length-1)*10+ord(list(strs)[length-1])-ord('0')

else:

iflist(strs)[0]=='-':

return0

else:

ifnotself.isNumber(list(strs)[0]):

print"不是數(shù)字"

self.flag=False

return-1

returnord(list(strs)[0])-ord('0')

defstrToint(self,s):

self.flag=True

ifs==Noneorlen(s)＜=0or(list(s)[0]=='-'andlen(s)==1):

print"不是數(shù)字"

self.flag=False

return-1

iflist(s)[0]=='+':

returnself.strtoint(s[1:len(s)],len(s)-1)

else:

returnself.strtoint(s,len(s))

if__name__=="__main__":

t=Test()

s="-543"

printt.strToint(s)

s="543"

printt.strToint(s)

s="+543"

printt.strToint(s)

s="++43"

result=t.strToint(s)

ift.getFlag():

printresult

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

-543

543

543

不是數(shù)字

算法性能分析：

由于這種方法對字符串進(jìn)行了一次遍歷，因此，時間復(fù)雜度為O(N)(其中，N是字符串的長度)。

方法二：非遞歸法

首先通過第一個字符的值確定整數(shù)的正負(fù)性，然后去掉符號位，把后面的字符串當(dāng)做正數(shù)來處理，處理完成后再根據(jù)正負(fù)性返回正確的結(jié)果。實現(xiàn)方法為從左到右遍歷字符串計算整數(shù)的值，以“123”為例，遍歷到‘1’的時候結(jié)果為1，遍歷到‘2’的時候結(jié)果為1*10+2=12，遍歷到‘3’的時候結(jié)果為12*10+3=123。其本質(zhì)思路與方法一類似，根據(jù)這個思路實現(xiàn)代碼如下：

classTest:

def__init__(self):

self.flag=None

defgetFlag(self):returnself.flag

#判斷c是否是數(shù)字,如果是返回True,否則返回False

defisNumber(self,c):

returnc＞='0'andc＜='9'

defstrToint(self,strs):

ifstrs==None:

self.flag=False

print"不是數(shù)字"

return-1

self.flag=True

res=0

i=0

minus=False#是否是負(fù)數(shù)

iflist(strs)[i]=='-':#結(jié)果是負(fù)數(shù)

minus=True

i+=1

iflist(strs)[i]=='+1:#正數(shù)

i+=1

whilei＜len(strs):

ifself.isNumber(list(strs)[i]):

res=res*10+ord(list(strs)[i])-ord('0')

else:

self.flag=False

print"不是數(shù)字"

return-1

i+=1

return-resifminuselseres

if__name__=="__main__":

t=Test()

s="-543"

printt.strToint(s)

s="543"

printt.strToint(s)

s="+543"

printt.strToint(s)

s="++43"

result=t.strToint(s)

ift.getFlag():

printresult

算法性能分析：

由于這種方法對字符串進(jìn)行了一次遍歷，因此算法的時間復(fù)雜度為O(N)(其中N是指字符串的長度)。但是由于方法一采用了遞歸法，而遞歸法需要大量的函數(shù)調(diào)用，也就有大量的壓棧與彈棧操作(函數(shù)調(diào)用都是通過壓棧與彈棧操作來完成的)。因此，雖然這兩個方法有相同的時間復(fù)雜度，但是方法二的運行速度會比方法一更快，效率更高。)解析：[考點]如何判斷字符串是否是整數(shù)。3.

給定主字符串S與模式字符串P，判斷P是否是S的子串，如果是，那么找出P在S中第一次出現(xiàn)的下標(biāo)。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(對于字符串的匹配，最直接的方法就是逐個比較字符串中的字符，這種方法比較容易實現(xiàn)，但是效率也比較低下。對于這種字符串匹配的問題，除了最常見的直接比較法外，經(jīng)典的KMP算法也是不二選擇，它能夠顯著提高運行效率，下面分別介紹這兩種方法。

方法一：直接計算法

假定主串S=“S0S1S2…Sm”，模式串P=“P0P1P2…Pn”。實現(xiàn)方法為：比較從主串S中以Si(0≤i＜m)為首的字符串和模式串P，判斷P是否為S的前綴，如果是，那么P在S中第一次出現(xiàn)的位置則為i，否則接著比較從Si+1開始的子串與模式串P，這種方法的時間復(fù)雜度為O(m*n)。此外如果i＞m-n，那么在主串中以Si為首的子串的長度必定小于模式串P的長度，因此，在這種情況下就沒有必要再做比較了。實現(xiàn)代碼如下：

"""

方法功能:判斷p是否為s的子串,如果是,那么返回p在s中第一次出現(xiàn)的下標(biāo),否則返回-1

輸入?yún)?shù):s和p分別為主串和模式串

"""

defmatch(s,p):

#檢查參數(shù)的合理性

ifs==Noneorp==None:

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

return-1

slen=len(s)

plen=len(p)

#p肯定不是s的子串

ifslen＜plen:

return-1

i=0

j=0

whilei＜slenandj＜plen:

iflist(s)[i]==list(p)[j]:

#如果相同,那么繼續(xù)比較后面的字符

i+=1

j+=1

else:

#后退回去重新比較

i=i-j+1

j=0

if(i＞slen-plen):

return-1

ifj＞=plen:#匹配成功

returni-plen

return-1

if__name__=="__main__":

s="xyzabcd"

p="abc"

printmatch(s,p)

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

3

算法性能分析：

這種方法在最差的情況下需要對模式串P遍歷m-n次(m，n分別為主串和模式串的長度)，因此，算法的時間復(fù)雜度為O(n(m-n))。

方法二：KMP算法

在方法一中，如果“P0P1P2…Pj-1”==“Si-j…Si-1”，那么模式串的前j個字符已經(jīng)和主串中i-j到i-1的字符進(jìn)行了比較，此時如果Pj!=Si，那么模式串需要回退到0，主串需要回退到i-j+1的位置重新開始下一次比較。而在KMP算法中，如果Pj!=Si，那么不需要回退，即i保持不動，j也不用清零，而是向右滑動模式串，用Pk和Si繼續(xù)匹配。這種方法的核心就是確定k的大小，顯然，k的值越大越好。

如果Pj!=Si，可以繼續(xù)用Pk和Si進(jìn)行比較，那么必須滿足：

(1)“P0P1P2…Pk-1”==“Si-k…Si-1”

已經(jīng)匹配的結(jié)果應(yīng)滿足下面的關(guān)系：

(2)“Pj-k…Pj-1”==“Si-k…Si-1”

由以上這兩個公式可以得出如下結(jié)論：

“P0P1P2…Pk-1”=“Pj-k…Pj-1”

因此，當(dāng)模式串滿足“P0P1P2…Pk-1”==“Pj-k…Pj-1”時，如果主串第i個字符與模式串第j個字符匹配失敗，那么只需要接著比較主串第i個字符與模式串第k個字符。為了在任何字符匹配失敗的時候都能找到對應(yīng)k的值，這里給出next數(shù)組的定義，next[i]=m表示的意思為：“P0P1…Pm-1”=“Pi-m…Pi-2Pi-1”。計算方法如下：

(1)next[j]=-1(當(dāng)j==0時)

(2)next[j]=max(Max{k|1＜k＜j且“P0…Pk”==“Pj-k-1…Pj-1”)

(3)next[j]=0(其他情況)

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

"""

方法功能:求字符串的next數(shù)組

輸入?yún)?shù):p為字符串,nexts為p的next數(shù)組

"""

defgetNext(p,nexts):

i=0

j=-1

nexts[0]=-1

whilei＜len(p):

ifj==-1orlist(p)[i]==list(p)[j]:

i+=1

j+=1

nexts[i]=j

else:

j=nexts[j]

defmatch(s,p,nexts):

#檢查參數(shù)的合理性,s的長度一定不會小于p的長度

ifs==Noneorp==None:

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

return-1

slen=len(s)

plen=len(p)

#p肯定不是s的子串

ifslen＜plen:

return-1

i=0

j=0

whilei＜slenandj＜plen:

print"i="+str(i)+","+"j="+str(i)

ifj==-1orlist(s)[i]==list(p)[j]:

#如果相同,那么繼續(xù)比較后面的字符

i+=1

j+=1

else:

#主串i不需要回溯,從next數(shù)組中找出需要比較的模式串的位置j

j=nexts[j]

ifj＞=plen:#匹配成功

returni-plen

return-1

if__name__=="__main__":

s="abababaabcbab"

p="abaabc"

lens=len(p)

nexts=[0]*(lens+1)

getNext(p,nexts)

print"nexts數(shù)組為:"+str(nexts[0]),

i=1

whilei＜lens-1:

print","+str(nexts[i]),

i+=1

print'\n'

print"匹配結(jié)果為:"+str(match(s,p,nexts))

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

next數(shù)組為:-1,0,0,1,1

i=0,j=0

i=1,j=1

i=2,j=2

i=3,j=3

i=3,j=1

i=4,j=2

i=5,j=3

i=5,j=1

i=6,j=2

i=7,j=3

i=8,j=4

i=9,j=5

匹配結(jié)果為：4

從運行結(jié)果可以看出，模式串P="abaabc"的next數(shù)組為[-1,0,0,1,1]，next[3]=1，說明P[0]==P[2]。當(dāng)i=3，j=3的時候S[i]!=P[j]，此時主串S不需要回溯，跟模式串位置j=next[j]=next[3]=1的字符繼續(xù)進(jìn)行比較。因為此時S[i-1]一定與P[0]相等，所以，就沒有必要再比較了。

算法性能分析：

這種方法在求next數(shù)組的時候循環(huán)執(zhí)行的次數(shù)為n(n為模式串的長度)，在模式串與主串匹配的過程中循環(huán)執(zhí)行的次數(shù)為m(m為主串的長度)。因此，算法的時間復(fù)雜度為O(m+n)。但是由于算法申請了額外的n個存儲空間來存儲next數(shù)組，因此，算法的空間復(fù)雜度為O(n)。)解析：[考點]如何實現(xiàn)字符串的匹配。4.

回文字符串是指一個字符串從左到右與從右到左遍歷得到的序列是相同的。例如“abcba”就是回文字符串，而“abcab”則不是回文字符串。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(最容易想到的方法為遍歷字符串所有可能的子串(蠻力法)，判斷其是否為回文字符串，然后找出最長的回文子串。但是當(dāng)字符串很長的時候，這種方法的效率是非常低下的，因此這種方法不可取。下面介紹幾種相對高效的方法。

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

在采用蠻力法找回文子串的時候有很多字符的比較是重復(fù)的，因此可以把前面比較的中間結(jié)果記錄下來供后面使用。這就是動態(tài)規(guī)劃的基本思想。那么如何根據(jù)前面查找的結(jié)果判斷后續(xù)的子串是否為回文字符串呢?下面給出判斷的公式，即動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移公式：

給定字符串“S0S1S2…Sn”，假設(shè)P(i,j)=1表示“SiSi+1…Sj”是回文字符串；P(i,j)=0則表示“SiSi+1…Sj”不是回文字符串。那么：

P(i,1)=1

如果Si==Si+1：那么P(i,i+1)=1，否則P(i,i+1)=0。

如果Si+1==Sj+1：那么P(i+1,j+1)=P(i,j)。

根據(jù)這幾個公式，實現(xiàn)代碼如下：

classTest:

def__new__(seif):

self.startIndex=None

self,lens=None

defgetStartIndex(self):returnself.startIndex

defgetLen(self):returnself.lens

"""

方法功能:找出字符串中最長的回文予串

輸入?yún)?shù):str為字符串,startIndex與len為找到的回文字符串的起始位置與長度

"""

defgetLongestPalindrome(self,strs):

ifstrs==None:

return

n=len(strs)#字符串長度

ifn＜1:

return

self.startIndex=0

self.lens=1

#申請額外的存儲空間記錄查找的歷史信息

historyRecord=[([None]*n)foriinrange(n)]

i=0

whilei＜n:

j=0

whilej＜n:

historyRecord[i][j]=0

j+=1

i+=1

#初始化長度為1的回文字符串信息

i=0

whilei＜n:

historyRecord[i][i]=1

i+=1

#初始化長度為2的回文字符串信息

i=0

whilei＜n-1:

ifList(strs)[i]==list(strs)[i+1]:

historyRecord[i][i+1]=1

self.startIndex=i

self.lens=2

i+=1

#查找從長度為3開始的回文字符串

pLen=3

whilepLen＜=n:

i=0

whilei＜n-pLen+1:

j=i+pLen-1

iflist(strs)[i]==list(strs)[j]andhistoryRecord[i+1][j-1]==1:

historyRecord[il[j]=1

self.startIndex=i

self.lens=pLen

i+=1

pLen+=1

if__name__=="__main__":

strs="abcdefgfedxyz"

t=Test()

t.getLongestPalindrome(strs)

ift.getStartIndex()!=-1andt.getLen()!=-1:

print"最長的回文字串為:",

i=t.getStartIndex()

whilei＜t.getStartIndex()+t.getLen():

printlist(strs)[i],

i+=1

else:

print"查找失敗"

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

最一長的回文子串為：defgfed

算法性能分析：

這種方法的時間復(fù)雜度為O(n2)，空間復(fù)雜度也為O(n2)。

此外，還有另外一種動態(tài)規(guī)劃的方法來實現(xiàn)最長回文字符串的查找。主要思路為：對于給定的字符串str1，求出對其進(jìn)行逆序的字符串str2，然后str1與str2的最長公共子串就是str1的最長回文子串。

方法二：中心擴展法

判斷一個字符串是否為回文字符串最簡單的方法為：從字符串最中間的字符開始向兩邊擴展，通過比較左右兩邊字符是否相等就可以確定這個字符串是否為回文字符串。這種方法對于字符串長度為奇數(shù)和偶數(shù)的情況需要分別對待。例如：對于字符串“aba”，就可以從最中間的位置b開始向兩邊擴展；但是對于字符串“baab”，就需要從中間的兩個字母開始分別向左右兩邊擴展。

基于回文字符串的這個特點，可以設(shè)計這樣一個方法來找回文字符串：對于字符串中的每個字符Ci，向兩邊擴展，找出以這個字符為中心的回文子串的長度。由于上面介紹的回文字符串長度的奇偶性，這里需要分兩種情況：(1)以Ci為中心向兩邊擴展；(2)以Ci和Ci+1為中心向兩邊擴展。實現(xiàn)代碼如下：

classTest:

def__init__(self):

self.startIndex=None

self.lens=None

defgetStartIndex(self):returnself.startIndex

defgetLen(self):returnself.lens

#對字符串str,以c1和c2為中心向兩側(cè)擴展尋找回文子串

defexpandBothSide(self,strs,c1,c2):

n=len(strs)

whilec1＞=0andc2＜nandlist(strs)[c1]==list(strs)[c2]:

c1-=1

c2+=1

tmpStartIndex=c1+1

tmpLen=c2-c1-1

iftmpLen＞self.lens:

self.lens=tmpLen

self.startIndex=tmpStartIndex

#方法功能:找出字符串最長的回文子串

defgetLongestPalindrome(self,strs):

ifstrs==None:

return

n=len(strs)

if(n＜1):

return

i=0

whilei＜n-1:

#找回文字符串長度為奇數(shù)的情況(從第i個字符向兩邊擴展)

self.expandBothSide(strs,i,i)

#找回文字符串長度為偶數(shù)的情況(從第i和i+1兩個字符向兩邊擴展)

self.expandBothSide(strs,i,i+1)

i+=1

if__name__=="__main__":

strs="abcdefgfedxyz"

t=Test()

t.getLongestPalindrome(strs)

ift.getStartIndex()!=-1andt.getLen()!=-1:

print"最長的回文字串為:",

i=t.getStartIndex()

whilei＜t.getStartIndex()+t.getLen():

printlist(strs)[i],

i+=1

else:

print"查找失敗"

算法性能分析：

這種方法的時間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。

方法三：Manacher算法

方法二需要根據(jù)字符串的長度分偶數(shù)與奇數(shù)兩種不同情況單獨處理，Manacher算法可以通過向相鄰字符中插入一個分隔符，把回文字符串的長度都變?yōu)槠鏀?shù)，從而可以對這兩種情況統(tǒng)一處理。例如：對字符串“aba”插入分隔符后變?yōu)椤?a*b*a*”，回文字符串的長度還是奇數(shù)。對字符串“aa”插入分隔符后變?yōu)椤?a*a*”，回文字符串長度也是奇數(shù)。因此，采用這種方法后可以對這兩種情況統(tǒng)一進(jìn)行處理。

Manacher算法的主要思路為：首先在字符串中相鄰的字符中插入分割字符，字符串的首尾也插入分割字符(字符串中不存在的字符，本例以字符*為例作為分割字符)。接著用另外的一個輔助數(shù)組P來記錄以每個字符為中心對應(yīng)的回文字符串的信息。P[i]記錄了以字符串第i個字符為中心的回文字符串的半徑(包含這個字符)，以P[i]為中心的回文字符串的長度為2*P[i]-1。P[i]-1就是這個回文字符串在原來字符串中的長度。例如：“*a*b*a*”對應(yīng)的輔助數(shù)組P為：[1,2,1,4,1,2,1]，最大值為P[3]=4，那么原回文字符串的長度則為4-1=3。

那么如何來計算P[i]的值呢?如下圖所示可以分為四種情況來討論：

假設(shè)在計算P[i]的時候，在已經(jīng)求出的P[id](id＜i)中，找出使得id+P[id]的值為最大的id，即找出這些回文字符串的尾字符下標(biāo)最大的回文字符的中心的下標(biāo)id。

(1)i沒有落到P[id]對應(yīng)的回文字符串中(如上圖(1))。此時因為沒有參考的值，所以只能把字符串第i個字符作為中心，向兩邊擴展來求P[i]的值。

(2)i落到了P[id]對應(yīng)的回文字符串中。此時可以把id當(dāng)做對稱點，找出i對稱的位置2*id-i，如果P[2*id-i]對應(yīng)的回文字符的左半部分有一部分落在P[id]內(nèi)，另外一部分落在P[id]外(如上圖(2))，那么P[i]=id+P[id]-i，也就是P[i]的值等于P[id]與P[2*id-i]重疊部分的長度。需要注意的是，P[i]不可能比id+P[id]-i更大，證明過程如下：假設(shè)P[i]＞id+P[id]-i，以i為中心的回文字符串可以延長a，b兩部分(延長的長度足夠小，使得P[i]＜P[2*id-i])，如上圖(2)所示：根據(jù)回文字符串的特性可以得出：a=b，找出a與b以id為對稱點的子串d，c。由于d和c落在了P[2*id-i]內(nèi)，因此，c=d，又因為b和c落在了P[id]內(nèi)，因此，b=c，所以，可以得到a=d，這與已經(jīng)求出的P[id]矛盾，因此，P[id]的值不可能更大。

(3)i落到了P[id]對應(yīng)的回文字符串中，把id當(dāng)做對稱點，找出i對稱的位置2*id-i，如果P[2*id-i]對應(yīng)的回文字符的左半部分與P[id]對應(yīng)的回文字符的左半部分完全重疊，那么P[i]的最小值為P[2*id-i]，在此基礎(chǔ)上繼續(xù)向兩邊擴展，求出P[i]的值。

(4)i落到了P[id]對應(yīng)的回文字符串中，把id當(dāng)做對稱點，找出i對稱的位置2*id-i，如果P[2*id-i]對應(yīng)的回文字符的左半部分完全落在了P[id]對應(yīng)的回文字符的左半部分，那么P[i]=P[2*id-i]。

根據(jù)以上四種情況可以得出結(jié)論：P[i]＞=MIN(P[2*id-i],P[id]-i)。在計算的時候可以先求出P[i]=MN(P[2*id-i],P[id]-i)，然后在此基礎(chǔ)上向兩邊繼續(xù)擴展尋找最長的回文子串，根據(jù)這個思路的實現(xiàn)代碼如下：

classTest:

def__init__(self):

self.center=None

self.palindromeLen=None

defgetCenter(self):returnselfcenter

defgetLen(self):returnselfpalindromeLen

defmins(self,a,b):

returnbifa＞belsea

"""

方法功能:找出字符串最長的回文子串

輸入?yún)?shù):str為字符串,center為回文字符的中心字符,len表示回文字符串長度

如果長度為偶數(shù),那么表示中間偏左邊的那個字符的位置

"""

defManacher(self,strs):

lens=len(strs)#字符串長度

newLen=2*lens+1

s=[None]*newLen#插入分隔符后的字符串

p=[None]*newLen

id=0#id表示以第id個字符為中心的回文字符串最右端的下標(biāo)值最大

i=0

whilei＜newLen:

#構(gòu)造填充字符串

s[i]='*'

p[i]=0

i+=1

i=0

whilei＜lens:

s[(i+1)*2]=list(strs)

i+=1

self.center=-1

self.palindromeLen=-1

#求解p數(shù)組

i=1

whilei＜newLen:

ifid+p[id]＞i:#圖中(1),(2),(3)三種情況

p[i]=self.mins(id+p[id]-i,p[2*id-i])

else:#對應(yīng)圖中第(4)種情況

p[i]=1

#然后接著向左右兩邊擴展求最長的回文予串

whilei+p[i]＜newLenandi-p[i]＞0ands[i-p[i]]==s[i+p[i]]:

p[i]+=1

#當(dāng)前求出的回文字符串最右端的下標(biāo)更大

ifi+p[i]＞id+p[id]:

id=i

#當(dāng)前求出的回文字符串更長

ifp[i]-1＞self.palindromeLen:

self.center=(i+1)/2-1

self.palindromeLen=p[i]-1#更新最長回文子串的長度

i+=1

if__name__=="__main__":

strs="abcbax"

t=Test()

t.Manacher(strs)

center=t.getCenter()

palindromeLen=t.getLen()

ifcenter!=-1andpalindromeLen!=-1:

print"最長的回文子串為:",

#回文字符串長度為奇數(shù)

ifpalindromeLen%2==1:

i=center-palindromeLen/2

whilei＜=center+palindromeLen/2:

printlist(strs)[i],

i+=1

#回文字符串長度為偶數(shù)

else:

i=center-palindromeLen/2

whilei＜center+palindromeLen/2:

printlist(strs)[i],

i+=1

else:

print"查找失敗"

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

最長的回文子串為：abcba

算法性能分析：

這種方法的時間復(fù)雜度和空間復(fù)雜度都為O(N)。)解析：[考點]如何求字符串里的最長回文子串。5.

已知字母序列[d,g,e,c,f,b,o,a]，請實現(xiàn)一個方法，要求對輸入的一組字符串input=[“bed”，“dog”，“dear”，“eye”]按照字母順序排序并打印。本例的輸出順序為：dear,dog,eye,bed。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(這道題本質(zhì)上還是考察對字符串排序的理解，唯一不同的是，改變了比較字符串大小的規(guī)則，因此這道題的關(guān)鍵是如何利用給定的規(guī)則比較兩個字符串的大小，只要實現(xiàn)了兩個字符串的比較，那么利用任何一種排序方法都可以。下面重點介紹字符串比較的方法。

本題的主要思路為：為給定的字母序列建立一個可以進(jìn)行大小比較的序列，在這里我們采用map數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)map的鍵為給定的字母序列，其值為從0開始依次遞增的整數(shù)，對于沒在字母序列中的字母，對應(yīng)的值統(tǒng)一按-1來處理。這樣在比較字符串中的字符時，不是直接比較字符的大小，而是比較字符在map中對應(yīng)的整數(shù)值的大小。以“bed”、“dog”為例，[d,g,e,c,f,b,o,a]構(gòu)建的map為char_to_int['d']=0,char_to_int['g']=1,char_to_int['e']=2，char_to_int['c']=3,char_to_int['f"]=4,char_to_int['b']=5,char_to_int['o']=6,char_to_int['a']=7。在比較“bed”與“dog”的時候，由于char_to_int['b']=5,char_to_int['d']=0，顯然5＞0，因此，'b'＞'d'，所以，"bed"＞"dog"。

下面以插入排序為例，給出實現(xiàn)代碼：

#根據(jù)char_to_int規(guī)定的字符的大小關(guān)系比較兩個字符的大小

defcompare(str1,str2,char_to_int):

len1=len(str1)

len2=len(str2)

i=0

j=0

whilei＜len1andj＜len2:

#如果字符不在給定的序列中,那么把值賦為-1

iflist(str1)[i]notinchar_to_int.keys():

char_to_int[list(str1)[i]]=-1

iflist(str2)[j]notinchar_to_int.keys():

char_to_int[list(str2)[j]]=-1

#比較各個字符的大小

ifchar_to_int[list(str1)[i]]＜char_to_int[list(str2)[j]]:

return-1

elifchar_to_int[list(str1)[i]]＞char_to_int[list(str2)[j]]:

return1

else:

i+=1

j+=1

ifi==len1andj==len2:

return0

elifi==len1:

return-1

else:

return1

definsertSort(s,char_to_int):

#對字符串?dāng)?shù)組進(jìn)行排序

lens=len(s)

i=1

whilei＜lens:

temp=s[i]

j=i-1

whilej＞=0:

#用給定的規(guī)則比較字符串的大小

ifcompare(temp,s[j],char_to_int)==-1:

s[j+1]=s[j]

else:

break

j-=1

s[j+1]=temp

i+=1

if__name__="__main__":

s=["bed","dog","dear","eye"]

sequence="dgecfboa"

lens=len(sequence)

#用來存儲字母序列與其對應(yīng)的值的鍵值對

char_to_int=dict()

#根據(jù)給定字符序列構(gòu)造字典

i=0

whilei＜lens:

char_to_int[list(sequence)[i]]=i

i+=1

insertSort(s,char_to_int)

i=0

whilei＜len(s):

prints[i],

i+=