Go程序員面試分類模擬題14論述題1.

題目描述：

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

packagemain

import(

"bytes"

"fmt"

//去掉字符串中嵌套的括號

funcremoveNestedPare(strstring)string{

arr:=[]rune(str)

Parentheses_num:=0

/用來記錄不匹配的“(”出現(xiàn)的次數(shù)

ifarr[0]!='('||arr[len(arr)-1]!=')'{

return""

}

varbufbytes.Buffer

buf.WfiteRune('(')

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

for_,v:=rangearr{

switchv{

case'(':

Parentheses_num++

case')':

Parentheses_num--

default:

buf.WriteRune(v)

}

}

//判斷括號是否匹配

ifParentheses_num!=0{

fmt.Println("由于括號不匹配，因此不做任何操作")

return""

}

//處理字符串結尾的")"

bur.WriteRune(')')

returnbuf.String()

}

funcmain(){

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

fmt.Printf("%v去除嵌套括號后為:%v",str,removeNestedPare(str))

}

程序的運行結果為

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

算法性能分析：

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

2.

題目描述

寫一個方法，檢查字符串是否是整數(shù)，如果是，返回其整數(shù)值。正確答案：整數(shù)分為負數(shù)與非負數(shù)，負數(shù)只有一種表示方法，而整數(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ù)的正負，接著對字符串從右往左遍歷，假設字符串為“c1c2c3…cn”，如果cn不是整數(shù)，那么這個字符串不能表示成整數(shù)；如果這個數(shù)是非負數(shù)(c1!=‘-’)，那么這個整數(shù)的值為“c1c2c3…cn-1”對應的整數(shù)值乘以10加上cn對應的整數(shù)值，如果這個數(shù)是負數(shù)(c1==‘-’)，那么這個整數(shù)的值為c1c2c3…cn-1對應的整數(shù)值乘以10減去cn對應的整數(shù)值。而求解子字符串“c1c2c3…cn-1”對應的整數(shù)的時候，可以用相同的方法來求解，因此可以采用遞歸的方法來求解。對于“+123”這種情況，可以首先去掉“+”，然后處理方法與“123”相同。由此可以得到遞歸表達式為：

c1==‘-’?toint(“c1c2c3…cn-1”)*10-(cn-'0')：toint(“c1c2c3…cn-1”)*10+(cn-'0')。

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

packagemain

import(

"fmt"

."/isdamir/gotype"http://引入定義的數(shù)據(jù)結構

)

varflagbool

funcstrToIntSub(arr[]rune,lengthint)int{

iflength＞1{

if!IsNumber(arr[len(arr)-1]){

fmt.Println("不是數(shù)字")

flag=false

return-1

}

ifarr[0]=='-'{

returnstrToIntSub(arr,length-1)*10-int(arr[length-1]-'0')

}else{

returnstrToIntSub(arr,length-1)*10+int(arr[length-1]-'0')

}

}else{

ifarr[0]=='-'{

return0

}else{

if!IsNumber(arr[0]){

fmt.Println("不是數(shù)字")

flag=false

return-1

}

returnint(arr[0]-'0')

}

}

}

funcstrToInt(sstring)int{

arr:=[]rune(s)

flag=true

ifarr[0]=='+'{

returnstrToIntSub(arr[1:],len(arr)-1)

}else{

returnstrToIntSub(arr,len(arr))

}

}

funcmain(){

fmt.Println("方法一")

printResult("-543")

printResult("543")

printResult("+543")

printResult("++43")

}

funcprintResult(sstring){

re:=strToInt(s)

ifflag{

fmt.Println(re)

}

}

程序的運行結果為

-543

543

543

不是數(shù)字

算法性能分析：

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

方法二：非遞歸法

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

packagemain

import(

"fmt"

."/isdamir/gotype"

//引入定義的數(shù)據(jù)結構

)

vatflagbool

funcstrToInt2(strstring)int{

arr:=[]rune(str)

flag=true

res:=0

//是否是負數(shù)

i:=0

minus:=false

ifarr[i]=='-'{

minus-true

i++

}

ifarr[i]-='+'{

i++

}

for;i＜len(arr);i++{

ifIsNumber(arr[i]){

res=res*10+int(arr[i]-'0')

}else{

flag=false

fmt.Println("不是數(shù)字")

return-1

}

}

ifminus{

return-res

}else{

returnres

}

}

funcmain(){

fmt.Println("方法二")

printResult2("-543")

printResult2("543")

printResult2("+543")

printResult2("++43")

}

funcprintResult2(sstring){

re:=strToInt2(s)

ifflag{

fmt.Println(re)

}

}

算法性能分析：

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

3.

題目描述：

給定主字符串s與模式字符串p，判斷p是否是s的子串，如果是，則找出p在s中第一次出現(xiàn)的下標。正確答案：對于字符串的匹配，最直接的方法就是挨個比較字符串中的字符，這種方法比較容易實現(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，這種方法的時間復雜度為O(mn)。此外如果i＞m-n的時候，在主串中以Si為首的子串的長度必定小于模式串P的長度，因此，在這種情況下就沒有必要再做比較了。實現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

//方法功能：判斷p是否為s的字串，如果是返回p在s中第一次出現(xiàn)的下標，否則返回-1

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

funcmatch(s,pstring)int{

slen,plen:=len(s),len(p)

//p肯定不是s的字串

ifslen＜plen{

return-1

}

i,j:=0,0

fori＜slen&&j＜plen{

ifs[i]==p[j]{

//如果相同，則繼續(xù)比較后面的字符

i,j=i+1,j+1

}else{

//后退回去重新比較

i=i-j+1

j=0

ifi＞slen-plen{

return-1

}

}

}

ifj＞=plen{//匹配成功

returni-plen

}

return-1

}

funcmain(){

s,p:="xyzabcd","abc"

fmt.Println(match(s,p))

}

程序的運行結果為

3

算法性能分析：

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

方法二：KIVIP算法

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

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

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

在已經(jīng)匹配的結果滿足下面的關系：

“Pj-k…Pj-1”==“Si-k…Si-1”

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

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

因此，當模式串滿足“P0P1P2…Pk-1”==“Pj-k…Pj-1”時，如果主串第i個字符與模式串第j個字符匹配失敗，此時只需要接著比較主串第i個字符與模式串第k個字符。

為了在任何字符匹配失敗的時候都能找到對應k的值，這里給出next數(shù)組的定義，next[i]=m表示的意思為：“P0P1…Pm-1”=“pi-m…Pi-2Pi-1”。計算方法如下：

(1)next[j]=-1

(當j==0時)

(2)next[j]=max(Max{k|1＜k＜j且“p0…pk”==“pj-k-1…pj-1”})

(3)next[j]=0

(其他情況)

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

packagemain

import(

"fmt"

)

funcgetNext(pstring,next[]int){

next[0]=-1

fori,j:=0,-1;i＜len(p);{

ifj==-1||p[i]==p[j]{

i++

j++

next[i]=j

}else{

j=next[j]

}

}

}

funcmatchKMP(s,pstring,next[]int)int{

slen,plen:=len(s),len(p)

//p肯定不是s的字串

ifslen＜plen{

return-1

}

i,j:=0,0

fori＜slen&&j＜plen{

fmt.Printf("i=%v,j=%v",i,j)

fmt.Println()

ifj==-1||s[i]==p[j]{

//如果相同，則繼續(xù)比較后面的字符

i++

j++

}else{

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

j=next[j]

}

}

ifj＞=plen{

returni-plen

}

return-1

}

funcmain(){

fmt.Println("KMP")

s,p:="abababaabcbab","abaabc"

next:=make([]int,len(p)+1)

getNext(p,next)

fmt.Println("next數(shù)組為:",neXt)

fmt.Println("匹配結果為:",matChKMP(s,p,next))

}

程序的運行結果為

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

匹配結果為：4

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

算法性能分析：

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

4.

題目描述：

回文字符串是指一個字符串從左到右與從右到左遍歷得到的序列是相同的。例如“abcba”就是回文字符串，而“abcab”則不是回文字符串。正確答案：最容易想到的方法為遍歷字符串所有可能的子串(蠻力法)，判斷其是否為回文字符串，然后找出最長的回文子串。但是當字符串很長的時候，這種方法的效率是非常低下的，因此，這種方法不可取。下面介紹幾種相對高效的方法。

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

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

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

P(i,i)=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)代碼如下：

packagemain

import(

"fmt"

)

typeTeststruct{

startIndexint

lenint

}

func(p*Test)getLlongestPalindrome(strstring){

ll:=len(str)

ifll＜1{

return

}

p.startIndex=0

p.len=1

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

historyRecord:=make([][]int,ll)

fori,_:=rangehistoryRecord{

historyRecord[i]=make([]int,ll)

}

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

fori:=0;i＜ll;i++{

historyRecord[i][i]=1

}

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

fori:=0;i＜ll-1;i++{

ifstr[i]==str[i+1]{

historyRecord[i][i+1]=1

p.startlndex=i

p.len=2

}

}

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

forpCen:=3;pLen＜=ll;pLen++{

fori:=0;i＜ll-pLen+1;i++{

vartmp=i+pLen-1

ifstr[i]==str[tmp]&&historyRecord[i+1][trap-1]==1{

historyRecord[i][tmp]=1

p.startIndex=i

p.len=pLen

}

}

}

}

//對字符串str，以c1和c2為中心向兩側擴展尋找回文字串

func(p*Test)expandBothSide(strstring,c1,c2int){

n:=len(str)

forc1＞=0&&c2＜n&&str[c1]==str[c2]{

c1--

c2++

}

tmpStartlndex:=c1+1

tmpLen:=c2-c1-1

iftmpLen＞p.len{

p.len=tmpLen

p.startlndex=tmpStartIndex

}

}

funcmain(){

str:="abcdefgfedxyz"

t:=&Test{}

fmt.Println("方法一")

t.getLIongestPalindrome(str)

ift.startIndex!=-1&&t.len!=-1{

fmt.Println("最長的回文子串為:",string(str[t.startIndex:t.startIndex+t.len]))

}else{

fmt.Println("查找失敗")

}

}

程序的運行結果為

最長的回文子串為：defgfed

算法性能分析：

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

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

方法二：中心擴展法

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

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

packagemain

import(

"fmt"

)

typeTeststruct{

startIndexint

lenint

}

//對字符串str，以c1和c2為中心向兩側擴展尋找回文子串

func(p*Test)expandBothSide(strstring,c1,c2int){

n:=len(str)

forc1＞=0&&c2＜n&&str[c1]==str[c2]{

c1--

c2++

}

tmpStartIndex:=c1+1

tmpLen:=c2-c1-1

iftmpLen＞p.len{

p.len=tmpLen

p.startIndex=tmpStartIndex

}

}

//找出字符串最長的回文子串

func(p*Test)getLlongestPalindrome2(strstring){

n:=len(str)

ifn＜1{

return

}

fori,_:=rangestr{

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

p.expandBothSide(str,i,j);

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

p.expandBothSide(str,i,i+1)

}

}

funcmain(){

str:="abcdefgfedxyz"

fmt.Println("方法二")

t:=&Test{}

t.getLlongestPalindrome2(str)

ift.startIndex!=-1&&t.len!=-1{

fmt.Println("最長的回文子串為:",string(str[t.startIndex:t.startIndex+t.len]))

}else{

fmt.Println("查找失敗")

}

}

算法性能分析：

這種方法的時間復雜度為O(n2)，空間復雜度為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)一進行處理。

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

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

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

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

(2)i落到了P[id]對應的回文字符串中，此時可以把id當作對稱點，找出i對稱的位置2*id-i，如果P[2*id-i]對應的回文字符的左半部分有一部分落在P[id]內，另外一部分落在P[id]外(如上圖(2))，那么P[i]=id+P[id]-i，也就是P[i]的值等于P[id]與P[2*id-i]重疊部分的長度。需要注意的是，P[i]不可能比id+P[id]-i更大，證明過程如下：假設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]內，因此，c=d，又因為b和c落在了P[id]內，因此，b=c，所以，可以得到a=d，這與已經(jīng)求出的P[id]矛盾，因此，p[id]的值不可能更大。

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

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

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

packagemain

import(

"fmt"

."/isdamir/gotype"http://引入定義的數(shù)據(jù)結構

)

typeManacherstruct{

centerint

palindromeLenint

}

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

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

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

func(p*Manacher)Manacher(strstring){

ll:=len(str)

newLen:=2*ll+1

//插入分隔符后的字符串

s:=make([]rune,newLen)

pp:=make([]int,newLen)

//id表示以第id個字符為中心的回文字符串最右端的下標值最大

id:=0

fori:=0;i＜newLen;i++{

s[i]='*'

pp[i]=0

}

fori:=0;i＜ll;i++{

s[(i+1)*2]=rune(str[i])

}

p.center=-1

p.palindromeLen=-1

//求解p數(shù)組

fori:=1;i＜newLen;i++{

ifid+pp[id]＞i{//圖中(1),(2),(3)三種情況

pp[i]=Min(id+pp[id]-i,pp[2*id-i])

}else{

//對應圖中第(1)種情況

pp[i]=1

}

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

fori+pp[i]＜newLen&&i-pp[i]＞0&&s[i-pp[i]]==s[i+pp[i]]{

pp[i]++

}

//求出當前更大的回文字符串最后端的下標

ifi+pp[i]＞id+pp[id]{

id=i

}

//求出當前更長的回文字符串

ifpp[i]-1＞p.palindromeLen{

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

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

}

}

}

funcmain(){

str:="abcbax"

m:=&Manacher{}

m.Manacher(str)

ifm.center!=-1&&m.palindromeLen!=-1{

fmt.Print("最長的回文子串為:")

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

ifm.palindromeLen%2==1{

fori:=m.center-m.palindromeLen/2;i＜=m.center+m.palindromeLen/2;i++{

fmt.Print(string(str[i]))

}

}else{//回文字符串長度為偶數(shù)

fori:=m.center-m.palindromeLen/2;i＜m.center+m.palindromeLen/2;i++{

fmt.Print(string(str[i]))

}

}

}else{

fmt.Println("查找失敗")

}

fmt.Println()

}

程序的運行結果為

最長的回文子串為：abcba

算法性能分析：

這種方法的時間復雜度和空間復雜度都為O(n)。[考點]如何求字符串里的最長回文子串

5.

題目描述：

已知字母序列[d，g，e，c，f，b，o，a]，請實現(xiàn)一個方法，要求對輸入的一組字符串input[]={“bed”，“dog”，“dear”，“eye”}，按照字母順序排序并打印。本例的輸出順序為：dear，dog，eye，bed。正確答案：這道題本質上還是考查對字符串排序的理解，唯一不同的是，改變了比較字符串大小的規(guī)則，因此，這道題的關鍵是如何利用給定的規(guī)則比較兩個字符串的大小，只要實現(xiàn)了兩個字符串的比較，那么利用任何一種排序方法都可以。下面重點介紹字符串比較的方法。

本題的主要思路為：為給定的字母序列建立一個可以進行比較大小的序列，在這里采用map數(shù)據(jù)結構來實現(xiàn)map為給定的字母序列，值為從0開始依次遞增的整數(shù)，對于沒在字母序列中的字母，對應的值統(tǒng)一按-1來處理。這樣在比較字符串中的字符時，不是直接比較字符的大小，而是比較字符在map中對應的整數(shù)值的大小。以“bed”、“dog”為例，[d，g，e，c，f，b，o，a]構建的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[‘h’]=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)代碼：

packagemian

import(

"fmt"

)

funccompare(str1,str2string,charToIntmap[byte]int)int{

len1,len2:=len(str1),len(str2)

i,j:=0,0

fori＜len1&&i＜len2{

//如果字符不在給定的序列中，把值賦為-1

if_,ok:=charToInt[str1[i]];!ok{

charToInt[str1[i]]=-1

}

if_,ok:=charToInt[str2[j]];!ok{

charToInt[str2[j]]=-1

}

//比較各個字符的大小

ifcharToInt[str1[i]]＜charToInt[str2[j]]{

return-1

}elseifcharToInt[str1[i]1]＞charToInt[str2[j]]{

return1

}else{

i++

j++

}

}

ifi==len1&&j==len2{

return0

}elseifi==len1{

return-1

}else{

return1

}

}

//對字符串數(shù)組進行排序

funcinsertSort(s[]string,charTolntmap[byte]int){

i,j:=0,0

ll:=len(s)

fori=1;i＜ll;i++{

tmp:=s[i]

forj=i-1;j＞=0;j--{

//用給業(yè)的規(guī)則比較字符串的大小

ifcompare(tmp,s[j],charToInt)==-1{

s[j+1]=s[j]

}else{

break

}

}

s[j+1]=tmp

}

}

funcmain(){

s:=[]string{"bed","dog","dear","eye"}

sequence:="dgecfboa"

//用來存儲字母序列與其對應的值的鍵值對

charToInt:=map[byte]int{}

fori,v:=rangesequence{

charToInt[byte(v)]=i

}

insertSort(s,charToInt)

fmt.Println(s)

}

程序的運行結果為

deardogeyebed

算法性能分析：

這種方法的時間復雜度為O(n3)(其中n為字