Go程序員面試分類(lèi)模擬題15

Go程序員面試分類(lèi)模擬題15論述題1.

題目描述：

給定一個(gè)字符串?dāng)?shù)組，找出數(shù)組中最長(zhǎng)的字符串，使其能由數(shù)組中其他的字符串組成。例如給定字符串?dāng)?shù)組{“test”，“tester”，“testert（江南博哥）est”，“testing”，“apple”，“seattle”，“banana”，“batting”，“ngcat”，“batti”，“bat”，“testingtester”，“testbattingcat”}。滿足題目要求的字符串為“testbattingcat”，因?yàn)檫@個(gè)字符串可以由數(shù)組中的字符串“test”，“batti”和“ngcat”組成。正確答案：既然題目要求找最長(zhǎng)的字符串，那么可以采用貪心的方法，首先對(duì)字符串由大到小進(jìn)行排序，從最長(zhǎng)的字符串開(kāi)始查找，如果能由其他字符串組成，就是滿足題目要求的字符串。接下來(lái)就需要考慮如何判斷一個(gè)字符串能否由數(shù)組中其他的字符串組成，主要的思路為：找出字符串的所有可能的前綴，判斷這個(gè)前綴是否在字符數(shù)組中，如果在，那么用相同的方法遞歸地判斷除去前綴后的子串是否能由數(shù)組中其他的子串組成。

以題目中給的例子為例，首先對(duì)數(shù)組進(jìn)行排序，排序后的結(jié)果為：{“testbattingcat”，“testingtester”，“testertest”，“testing”，“seattle”，“batting”，“tester”，“banana”，“apple”，“ngcat”，“batti”，“test”，“bat”}。首先取“testbattingcat”進(jìn)行判斷，具體步驟如下：

(1)分別取它的前綴“t”，“te”，“tes”都不在字符數(shù)組中，“test”在字符數(shù)組中。

(2)接著用相同的方法遞歸地判斷剩余的子串“battingcat”，同理，“b”，“ba”都不在字符數(shù)組中，“bat”在字符數(shù)組中。

(3)接著判斷“tingcat”，通過(guò)判斷發(fā)現(xiàn)“tingcat”不能由字符數(shù)組中其他字符組成。因此，回到上一個(gè)遞歸調(diào)用的子串接著取字符串的前綴進(jìn)行判斷。

(4)回到上一個(gè)遞歸調(diào)用，待判斷的字符串為“batcingcat”，當(dāng)前比較到的前綴為“bat”，接著取其他可能的前綴“batt”，“battt”都不在字符數(shù)組中，“battti”在字符數(shù)組中。接著判斷剩余子串“ngcat”。

(5)通過(guò)比較發(fā)現(xiàn)“ngcat”在字符數(shù)組中。因此，能由其他字符組成的最長(zhǎng)字符串為“testbattingcat”。

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

packagemain

import(

"sort"

"fmt"

)

typeLongestWordstruct{

}

//判斷字符串str是否在字符串?dāng)?shù)組中

func(p*LongestWord)find(strArr[]string,strstring)bool{

for_,v:=rangestrArr{

ifstr==v{

returntrue

}

}

retumfalse

}

//方法功能：判斷字符串word是否能由數(shù)組strArray中的其他單詞組成

//參數(shù)：word為待判斷的后綴子串，length為待判斷字符串的長(zhǎng)度

func(p*LongestWord)isContain(strArr[]string,wordstring,lengthint)bool{

ll:=len(word)

//遞歸的結(jié)束條件，當(dāng)字符串長(zhǎng)度為0時(shí)，說(shuō)明字符串已經(jīng)遍歷完了

ifll==0{

returntrue

}

//循環(huán)取字符串的所有前綴

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

//取到的子串為自己

ifi==length{

returnfalse

}

str:=string(word[0:i])

ifp.find(strArr,str){

//查找完字符串的前綴后，遞歸判斷后面的子串能否由其他單詞組成

ifp.isContain(strArr,string(word[i:]),length){

returntrue

}

}

}

returnfalse

}

//找出能由數(shù)組中其他字符串組成的最長(zhǎng)字符串

func(p*LongestWord)GetLogestStr(strArr[]string)string{

//對(duì)字符串由大到小排序

sort.Slice(strArr,func(i,jint)bool{

returnlen(strArr[i])＞len(strArr[j])

})

//貪心地從最長(zhǎng)的字符串開(kāi)始判斷

for_,v:=rangestrArr{

ifp.isContain(strArr,v,len(v)){

returnv

}

}

return""

}

funcmain(){

strArr:=[]string{"test","tester","testertest","testing","apple","seattle","banana","batting",

"ngcat","batti","bat","testingtester","testbattingcat"}

lw:=new(LongestWord)

logestStr:=lw.GetLogestStr(strArr)

iflogestStr==""{

fmt.Println("不存在這樣的字符串")

}else{

fmt.Println("最長(zhǎng)的字符串為:",logestStr)

}

}

程序的運(yùn)行結(jié)果為

最長(zhǎng)的字符串為：testbattingcat

算法性能分析：

排序的時(shí)間復(fù)雜度為O(nlogn)，假設(shè)單詞的長(zhǎng)度為m，那么有m種前綴，判斷一個(gè)單詞是否在數(shù)組中的時(shí)間復(fù)雜度為O(mn)，由于總共有n個(gè)字符串，因此，判斷所需的時(shí)間復(fù)雜度為O(m*n2)。因此，總的時(shí)間復(fù)雜度為O(nlogn+m*n2)。當(dāng)n比較大的時(shí)候，時(shí)間復(fù)雜度為O(n2)。[考點(diǎn)]如何找到由其他單詞組成的最長(zhǎng)單詞

2.

題目描述：

用遞歸的方式實(shí)現(xiàn)一個(gè)求字符串中連續(xù)出現(xiàn)相同字符的最大值，例如字符串“aaabbcc”中連續(xù)出現(xiàn)字符‘a(chǎn)’的最大值為3，字符串“abbc”中連續(xù)出現(xiàn)字符‘b’的最大值為2。正確答案：如果不要求采用遞歸的方法，那么算法的實(shí)現(xiàn)就非常簡(jiǎn)單，只需要在遍歷字符串的時(shí)候定義兩個(gè)額外的變量curMaxLen與maxLen，分別記錄與當(dāng)前遍歷的字符重復(fù)的連續(xù)字符的個(gè)數(shù)和遍歷到目前為止找到的最長(zhǎng)的連續(xù)重復(fù)字符的個(gè)數(shù)。在遍歷的時(shí)候，如果相鄰的字符相等，則執(zhí)行curMaxLen+1；否則，更新最長(zhǎng)連續(xù)重復(fù)字符的個(gè)數(shù)，即maxLen=max(curMaxLen，maxLen)，由于碰到了新的字符，因此，curMaxLen=1。

題目要求用遞歸的方法來(lái)實(shí)現(xiàn)，通過(guò)對(duì)非遞歸方法進(jìn)行分析可以知道，在遍歷字符串的時(shí)候，curMaxLen與maxLen是最重要的兩個(gè)變量，那么在進(jìn)行遞歸調(diào)用的時(shí)候，通過(guò)傳入兩個(gè)額外的參數(shù)(curMaxLen與maxLen)就可以采用與非遞歸方法類(lèi)似的方法來(lái)實(shí)現(xiàn)，實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

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

)

funcgetMaxDupChar(sstring,startIndex,curMaxLen,maxLenint)int{

//字符串遍歷結(jié)束，返回最長(zhǎng)連續(xù)重復(fù)字符串的長(zhǎng)度

ifstartIndex==len(s)-1{

returnMax(curMaxLen,maxLen)

}

//如果兩個(gè)連續(xù)的字符相等，則在遞歸調(diào)用的時(shí)候把當(dāng)前最長(zhǎng)串的長(zhǎng)度加1

ifs[startIndex]==s[startIndex+1]{

returngetMaxDupChar(s,startIndex+1,curMaxLen+1,maxLen)

}else{

//兩個(gè)連續(xù)的子串不相等，求出最長(zhǎng)串(max(curMaxLen,maxLen))，

//當(dāng)前連續(xù)重復(fù)字符串的長(zhǎng)度變?yōu)?

returngetMaxDupChar(s,startIndex+1,1,Max(curMaxLen,maxLen))

}

}

funcmain(){

fmt.Println("abbc的最長(zhǎng)連續(xù)重復(fù)子串長(zhǎng)度為:",getMaxDupChar("abbc",0,0,1))

fmt.Println("aaabbcc的最長(zhǎng)連續(xù)重復(fù)子串長(zhǎng)度為:",getMaxDupChar("aaabbcc",0,0,1))

}

程序的運(yùn)行結(jié)果為

abbc的最長(zhǎng)連續(xù)重復(fù)子串長(zhǎng)度為：2

aaabbcc的最長(zhǎng)連續(xù)重復(fù)子串長(zhǎng)度為：3

算法性能分析：

由于這種方法對(duì)字符串進(jìn)行了一次遍歷，因此，算法的時(shí)間復(fù)雜度為O(n)。這種方法也沒(méi)有申請(qǐng)額外的存儲(chǔ)空間。[考點(diǎn)]如何統(tǒng)計(jì)字符串中連續(xù)重復(fù)字符的個(gè)數(shù)

3.

題目描述：

假設(shè)L=＜a1，a2，…，an＞是n個(gè)不同的實(shí)數(shù)的序列，L的遞增子序列是這樣一個(gè)子序列Lin=＜aK1，ak2，…，akm＞，其中，k1＜k2＜…＜km且aK1＜ak2＜…＜akm。求最大的m值。正確答案：方法一：最長(zhǎng)公共子串法

對(duì)序列L=＜a1，a2，…，an＞按遞增進(jìn)行排序得到序列LO=＜b1，b2，…，bn＞。顯然，L與LO的最長(zhǎng)公共子序列就是L的最長(zhǎng)遞增子序列。因此，可以使用求公共子序列的方法來(lái)求解。

方法二：動(dòng)態(tài)規(guī)劃法

由于以第i個(gè)元素為結(jié)尾的最長(zhǎng)遞增子序列只與以第i-1個(gè)元素為結(jié)尾的最長(zhǎng)遞增子序列有關(guān)，因此，本題可以采用動(dòng)態(tài)規(guī)劃的方法來(lái)解決。下面首先介紹動(dòng)態(tài)規(guī)劃方法中的核心內(nèi)容遞歸表達(dá)式的求解。

以第i個(gè)元素為結(jié)尾的最長(zhǎng)遞增子序列的取值有兩種可能：

(1)1，當(dāng)?shù)趇個(gè)元素單獨(dú)作為一個(gè)子串(L[i]＜=L[i-1])。

(2)以第i-1個(gè)元素為結(jié)尾的最長(zhǎng)遞增子序列加1(L[i]＞L[i-1])。

由此可以得到如下的遞歸表達(dá)式：假設(shè)maxLen[i]表示以第i個(gè)元素為結(jié)尾的最長(zhǎng)遞增字序列，那么

(1)maxLen[i]=max{1,maxLen[j]+1),j＜iandL[j]＜L[i]

(2)maxLen[0]=1

根據(jù)這個(gè)遞歸表達(dá)式可以非常容易地寫(xiě)出實(shí)現(xiàn)的代碼如下：

packagemain

import(

"fmt"

)

funcgetMaxAscendingLen(strstring)int{

maxLen:=make([]int,len(str))

maxAcsendingLen:=1

fori,_:=rangestr{

maxLen[i]=1

forj:=0;j＜i;j++{

ifstr[j]＜str[i]&&maxLen[j]＞maxLen[i]-1{

maxLen[i]=maxLen[j]+1

maxAcsendingLen=maxLen[i]

}

}

}

returnmaxAcsendingLen

}

funcmain(){

fmt.Println("最長(zhǎng)遞增子序列的長(zhǎng)度為:",getMaxAscendingLen("xbcdza"))

}

程序的運(yùn)行結(jié)果為

xbcdza最長(zhǎng)遞增子序列的長(zhǎng)度為：4

算法性能分析：

由于這種方法用雙重循環(huán)來(lái)實(shí)現(xiàn)，因此，這種方法的時(shí)間復(fù)雜度為O(n2)，此外由于這種方法還使用了n個(gè)額外的存儲(chǔ)空間，因此，空間復(fù)雜度為O(n)。[考點(diǎn)]如何求最長(zhǎng)遞增子序列的長(zhǎng)度

4.

題目描述：

給定一個(gè)字符串，找出這個(gè)字符串中最長(zhǎng)的重復(fù)子串，比如給定字符串“banana”，子字符串“ana”出現(xiàn)2次，因此最長(zhǎng)的重復(fù)子串為“ana”。正確答案：由于題目要求最長(zhǎng)重復(fù)子串，顯然可以先求出所有的子串，然后通過(guò)比較各子串是否相等從而求出最長(zhǎng)公共子串，具體的思路為：首先找出長(zhǎng)度為n-1的所有子串，判斷是否有相等的子串，如果有相等的子串，那么就找到了最長(zhǎng)的公共子串；否則找出長(zhǎng)度為n-2的子串繼續(xù)判斷是否有相等的子串，依次類(lèi)推直到找到相同的子串或遍歷到長(zhǎng)度為1的子串為止，這種方法的思路比較簡(jiǎn)單，但是算法復(fù)雜度較高。下面介紹一種效率更高的算法：后綴數(shù)組法。

后綴數(shù)組是一個(gè)字符串的所有后綴的排序數(shù)組。后綴是指從某個(gè)位置i開(kāi)始到整個(gè)串末尾結(jié)束的一個(gè)子串。字符串r的從第i個(gè)字符開(kāi)始的后綴表示為Suffix(i)，也就是Suffix(i)=r[i..len(r)]。例如：字符串“banana”的所有后綴如下：

所以“banana”的后綴數(shù)組為：{5，3，1，0，4，2}。由此可以把找字符串的重復(fù)子串的問(wèn)題轉(zhuǎn)換為從后綴排序數(shù)組中，通過(guò)對(duì)比相鄰的兩個(gè)子串的公共串的長(zhǎng)度找出最長(zhǎng)的公共串的問(wèn)題。在上例中3:ana與1:anana的最長(zhǎng)公共子串為ana。這也就是這個(gè)字符串的最常公共子串。實(shí)現(xiàn)代碼如下：

packagemain

import(

"sort"

"fmt"

)

//找出最長(zhǎng)的公共子串的長(zhǎng)度

funcmaxPrefix(s1,s2string)int{

i:=0

fori＜len(s1)&&i＜len(s2){

ifs1[i]==s2[i]{

i++

}else{

break

}

}

returni

}

//獲取最長(zhǎng)的公共子串

funcgetMaxCommonStr(txtstring)string{

n:=len(txt)

//用來(lái)存儲(chǔ)后綴數(shù)組

suffixes:=make([]string,n)

longestSubStrLen:=0

varlongestSubStrstring

//獲取到后綴數(shù)組

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

suffixes[i]=txt[i:]

}

sort.Strings(suffixes)

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

tmp:=maxPrefix(suffixes[i],suffixes[i-1])

iftmp＞longestSubStrLen{

longestSubStrLen=tmp

longestSubStr=(suffixes[i])[0:i+1]

}

}

returnlongestSubStr

}

funcmain(){

txt:="banana"

fmt.Println("最長(zhǎng)的公共子串為",getMaxCommonStr(txt))

}

算法性能分析：

這種方法在生成后綴數(shù)組的復(fù)雜度為O(n)，排序的算法復(fù)雜度為O(nlogn*n)，最后比較相鄰字符串的操作的時(shí)間復(fù)雜度為O(n)，所以，算法的時(shí)間復(fù)雜度為O(nlogn*n)。此外，由于申請(qǐng)了長(zhǎng)度為n的額外的存儲(chǔ)空間，因此空間復(fù)雜度為O(n)。[考點(diǎn)]求一個(gè)串中出現(xiàn)的第一個(gè)最長(zhǎng)重復(fù)子串

5.

題目描述：

給定一個(gè)字符串，求串中字典序最大的子序列。字典序最大的子序列是這樣構(gòu)造的：給定字符串a(chǎn)0a1…an-1，首先在字符串a(chǎn)0a1…an-1找到值最大的字符ai，然后在剩余的字符串a(chǎn)i+1…an-1中找到值最大的字符aj，然后在剩余的aj+1…an-1中找到值最大的字符ak…直到字符串的長(zhǎng)度為0，則aiajak…即為答案。正確答案：方法一：順序遍歷法

最直觀的思路就是首先遍歷一次字符串，找出最大的字符ai，接著從ai開(kāi)始遍歷再找出最大的字符，依此類(lèi)推直到字符串長(zhǎng)度為0。

以”acbdxmng”為例，首先對(duì)字符串遍歷一遍找出最大的字符‘x’，接著從‘m’開(kāi)始遍歷找出最大的字符‘n’，然后從‘g’開(kāi)始遍歷找到最大的字符為‘g’，因此“acbdxmng”的最大子序列為“xng”。實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

//求串中字典序最大的子序列

funcgetLargestSub(strstring)string{

ll:=len(str)

largestSub:=make([]byte,ll+1)

k:=0

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

largestSub[k]=str[i]

fofj:=i+1;j＜ll;j++{

//找出第i個(gè)字符后面最大的字符放到largestSub[k]中

ifstr[j]＞largestSub[k]{

largestSub[k]=str[j]

i=j

}

}

k++

}

returnstring(largestSub[0:k])

}

funcmain()(

s:="acbdxmng"

result:=getLargestSub(s)

ifresult==""{

fmt.Println("字符串為空")

}else{

fmt.Println(result)

}

}

程序的運(yùn)行結(jié)果為

xng

算法性能分析：

這種方法在最壞的情況下(字符串中的字符按降序排列)，時(shí)間復(fù)雜度為O(n2)；在最好的情況下(字符串中的字符按升序排列)，時(shí)間復(fù)雜度為O(n)。此外這種方法需要申請(qǐng)n+1個(gè)額外的存儲(chǔ)空間，因此，空間復(fù)雜度為O(n)。

方法二：逆序遍歷法

通過(guò)對(duì)上述運(yùn)行結(jié)果進(jìn)行分析，發(fā)現(xiàn)an-1一定在所求的子串中，接著逆序遍歷字符串，大于或等于an-1的字符也一定在子串中，依次類(lèi)推，一直往前遍歷，只要遍歷到的字符大于或等于子串首字符時(shí)，就把這個(gè)字符加到子串首。由于這種方法首先找到的是子串的最后一個(gè)字符，最后找到的是子串的第一個(gè)字符，因此，在實(shí)現(xiàn)的時(shí)候首先按照找到字符的順序把找到的字符保存到數(shù)組中，最后再對(duì)字符數(shù)組進(jìn)行逆序從而得到要求的字符。以"acbdxmng"為例，首先，字符串的最后一個(gè)字符‘g’一定在子串中，接著逆向遍歷找到大于等于‘g’的字符‘n’加入到子串中“gn”(子串的首字符為‘n’)，接著繼續(xù)逆向遍歷找到大于或等于‘n’的字符‘x’加入到子串中“gnx”，接著繼續(xù)遍歷，沒(méi)有找到比‘x’大的字符。最后對(duì)子串“gnx”逆序得到"xng”。實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

funcgetLargestSub2(txtstring)string{

ll:=len(txt)

largestSub:==make([]byte,ll+1)

//最后一個(gè)字符一定在子串中

largestSub[0]=txt[ll-1]

i:=ll-2

j:=0

//逆序遍歷字符串

for;i＞=0;i--{

iftxt[i]＞=largestSub[j]{

j++

largestSub[j]=txt[i]

}

}

largestSub[j+1]=''

//對(duì)子串進(jìn)行逆序遍歷

fori=0;i＜j;i,j=i+1,j-1{

trap:=largestSub[i]

largestSub[i]=largestSub[j]

largestSub[j]=tmp

}

returnstring(largestSub)

}

funcmain(){

s:="acbdxmng"

fmt.Println("逆序遍歷法")

result:=getLargestSub2(s)

ifresult==""{

fmt.Println("字符串為空")

}else{

fmt.Println(result)

}

}

算法性能分析：

這種方法只需要對(duì)字符串遍歷一次，因此，時(shí)間復(fù)雜度為O(n)。此外，這種方法需要申請(qǐng)n+1個(gè)額外的存儲(chǔ)空間，因此，空間復(fù)雜度為O(n)。[考點(diǎn)]如何求解字符串中字典序最大的子序列

6.

題目描述：

給定一個(gè)能判斷一個(gè)單詞是否為另一個(gè)單詞的子字符串的方法，記為isSubstring。如何判斷s2是否能通過(guò)旋轉(zhuǎn)s1得到(只能使用一次isSubstring方法)。例如：“waterbottle”可以通過(guò)字符串“erbottlewat”旋轉(zhuǎn)得到。正確答案：如果題目沒(méi)有對(duì)isString使用的限制，可以通過(guò)求出s2進(jìn)行旋轉(zhuǎn)的所有組合，然后與s1進(jìn)行比較。但是這種方法的時(shí)間復(fù)雜度比較高。通過(guò)對(duì)字符串旋轉(zhuǎn)進(jìn)行仔細(xì)分析，發(fā)現(xiàn)對(duì)字符串s1進(jìn)行旋轉(zhuǎn)得到的字符串一定是s1s1的子串。因此可以通過(guò)判斷s2是否是s1s1的子串來(lái)判斷s2能夠通過(guò)旋轉(zhuǎn)s1得到。例如：s1=“waterbottle”，那么s1s1=“waterbottlewaterbottle”，顯然s2是s1s1的子串。因此s2能通過(guò)旋轉(zhuǎn)s1得到。實(shí)現(xiàn)代碼如下：

packagemain

import(

"s