Go程序員面試分類模擬題16

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

題目描述：

編輯距離又稱Levenshtein距離，是指兩個(gè)字符串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符（江南博哥）、插入一個(gè)字符、刪除一個(gè)字符。請(qǐng)?jiān)O(shè)計(jì)并實(shí)現(xiàn)一個(gè)算法來(lái)計(jì)算兩個(gè)字符串的編輯距離，并計(jì)算其復(fù)雜度。在某些應(yīng)用場(chǎng)景下，替換操作的代價(jià)比較高，假設(shè)替換操作的代價(jià)是插入和刪除的兩倍，算法該如何調(diào)整?正確答案：本題可以使用動(dòng)態(tài)規(guī)劃的方法來(lái)解決，具體思路如下：

給定字符串s1，s2，首先定義一個(gè)函數(shù)D(i，j)(0＜=i＜=strlen(s1)，0＜=j＜=strlen(s2))，用來(lái)表示第一個(gè)字符串s1長(zhǎng)度為i的子串與第二個(gè)字符串s2長(zhǎng)度為i的子串的編輯距離。從s1變到s2可以通過(guò)如下三種操作：

(1)添加操作。假設(shè)已經(jīng)計(jì)算出D(i，j-1)的值(s1[0…i]與s2[0…j-1]的編輯距離)，則D(i，j)=D(i，j-1)+1(s1長(zhǎng)度為i的字串后面添加s2[j]即可)。

(2)刪除操作。假設(shè)已經(jīng)計(jì)算出D(i-1，j)的值(s1[0…i-1]到s2[0…j]的編輯距離)，則D(i，j)=D(i-1，j)+1(s1長(zhǎng)度為i的字串刪除最后的字符s1[j]即可)。

(3)替換操作。假設(shè)已經(jīng)計(jì)算出D(i-1，j-1)的值(s1[0…i-1]與s2[0…j-1]的編輯距離)，如果s1[i]=s2[j]，則D(i，j)=D(i-1，j-1)，如果s1[i]!=s2[j]，則D(i，j)=D(i-1，j-1)+1(替換s1[i]為s2[j]，或替換s2[j]為s1[i])。

此外，D(0,j)=j且D(i，0)=i(從一個(gè)字符串變成長(zhǎng)度為0的字符串的代價(jià)為這個(gè)字符串的長(zhǎng)度)。

由此可以得出如下實(shí)現(xiàn)方式：對(duì)于給定的字符串s1，s2，定義一個(gè)二維數(shù)組D，則有以下幾種可能性。

(1)如果i==0，那么D[i，j]=j(0＜=j＜=strlen(s2))。

(2)如果j==0，那么D[i，j]=i(0＜=i＜=strlen(s1))。

(3)如果i＞0且j＞0：

1)如果s1[i]==s2[j]，那么D(i，j)=min{edit(i-1，j)+1，edit(i，j-1)+1，edit(i-1，j-1)}。

2)如果s1[i]!=s2[j]，那么D(i，j)=min{edit(i-1，j)+1，edit(i，j-1)+1，edit(i-1，j-1)+1}。

通過(guò)以上分析可以發(fā)現(xiàn)，對(duì)于第一個(gè)問(wèn)題可以直接采用上述的方法來(lái)解決。對(duì)于第二個(gè)問(wèn)題，由于替換操作是插入或刪除操作的兩倍，因此，只需要修改如下條件即可：

如果s1[i]!=s2[j]，那么D(i，j)=min{edit(i-1，j)+1，edit(i，j-1)+1，edit(i-1，j-1)+2}。

根據(jù)上述分析，給出實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

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

)

//參數(shù)replaceWight用來(lái)表示替換操作與插入刪除操作相比的倍數(shù)

funcedit(s1,s2string,replaceWightint)int{

ifs1==""||s2==""{

return0

}

ifs1==""{

returnlen(s2)

}

ifs2==""{

returnlen(s1)

}

len1,len2:=len(s1),len(s2)

//申請(qǐng)二維數(shù)組來(lái)存儲(chǔ)中間的計(jì)算結(jié)果

D:=make([][]int,len1+1)

fori,_:=rangeD{

D[i]=make([]int,len2+1)

}

fori:=0;i＜len1+1;i++{

D[i][0]=i

}

fori:=0;i＜len2+1;i++{

D[0][i]=i

}

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

forj:=1;j＜len2+1;j++{

ifs1[i-1]==s2[j-1]{

D[i][j]=Min3(D[i-1][j]+1,D[i][j-1]+1,D[i-1][j-1])

}else{

D[i][j]=Min3(D[i-1][j]+1,D[i][j-1]+1,D[i-1][j-1]+replaceWight)

}

}

}

fmt.Println("-----------------")

fori:=0;i＜len1+1;i++{

forj:=0;j＜len2+1;j++{

fmt.Print(D[i][j],"")

}

fmt.Println()

}

fmt.Println("----------------")

returnD[len1][len2]

}

funcmain(){

s1:="bciln"

s2:="fciling"

fmt.Println("第一問(wèn):")

fmt.Println("編輯距離:",edit(s1,s2,1))

fmt.Println("第二問(wèn):")

fmt.Println("編輯距離:",edit(s1,s2,2))

}

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

第一問(wèn)：

-----------------------------

01234567

11234567

22123456

33212345

44321234

55432223

-----------------------------

編輯距離：3

第二問(wèn)：

-----------------------------

01234567

12345678

23234567

34323456

45432345

56543434

-----------------------------

編輯距離：4

算法性能分析：

這種方法的時(shí)間復(fù)雜度與空間復(fù)雜度都為O(m*n)(其中，m，n分別為兩個(gè)字符串的長(zhǎng)度)。[考點(diǎn)]如何求字符串的編輯距離

2.

題目描述：

尋找一條從左上角(arr[0][0])到右下角(arr[m-1][n-1])的路線，使得沿途經(jīng)過(guò)的數(shù)組中的整數(shù)的和最小。正確答案：對(duì)于這道題，可以從右下角開(kāi)始倒著來(lái)分析這個(gè)問(wèn)題：最后一步到達(dá)arr[m-1][n-1]只有兩條路：通過(guò)arr[m-2][n-1]到達(dá)或通過(guò)arr[m-1][n-2]到達(dá)，假設(shè)從arr[0][0]到arr[m-2][n-1]沿途數(shù)組最小值為f(m-2，n-1)，到arr[m-1]【n-2]沿途數(shù)組最小值為f(m-1，n-2)。因此，最后一步選擇的路線為min{f(m-2，n-1)，f(m-1，n-2))。同理，選擇到arr[m-2][n-1]或arr[m-1][n-2]的路徑可以采用同樣的方式來(lái)確定。

由此可以推廣到一般的情況。假設(shè)到arr[i-1][j]與arr[i][j-1]的最短路徑的和為f(i-1，j)和f(i，j-1)，那么到達(dá)arr[i][j]的路徑的上所有數(shù)字和的最小值為：f(i，j)=min{f(i-1，j)，f(i，j-1)}+arr[i][j]。

方法一：遞歸法

根據(jù)這個(gè)遞歸公式可知，可以采用遞歸的方法來(lái)實(shí)現(xiàn)，遞歸的結(jié)束條件為遍歷到arr[0][0]。在求解的過(guò)程中，還需要考慮另外一種特殊情況：遍歷到arr[i][j](當(dāng)i=0或j=0)的時(shí)候，只能沿著一條固定的路徑倒著往回走直到arr[0][0]。根據(jù)這個(gè)遞歸公式與遞歸結(jié)束條件可以給出實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

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

)

funcgetMineathSub(arr[][]int,i)jint)int{

//倒著走到了第一個(gè)結(jié)點(diǎn)，遞歸結(jié)束

ifi==0&&j==0{

returnarr[i][j]

}elseifi＞0&&j＞0{

//選取兩條可能路徑上的最小值

returnarr[j][j]+Min(getMinPathSub(arr,i-1,j),getMinPathSub(arr,i,j-1))

}elseifi＞0&&j==0{

ieturnarr[i][j]+getMinPathSub(arr,i-1,j)

}else{

returnarr[i][j]+getMinPathSub(arr,i,j-1)

}

}

funsgetMinPath1(arr[][]int)int{

ifarr==nil||len(arr)==0{

return0

}

returngetMinPathSub(arr,len(arr)-1,len(arr[0])-1)

}

funcmain(){

arr:=[][]int{

{1,4,3),

{8,7,5},

{2,1,5},

}

fmt.Println("方法一")

fmt.Println(getMinPath1(arr))

}

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

17

這種方法雖然能得到題目想要的結(jié)果，但是效率太低，主要因?yàn)槔锩嬗写罅康闹貜?fù)計(jì)算過(guò)程，比如在計(jì)算(i-1，j)與f(j-1，i)的過(guò)程中都會(huì)去計(jì)算f(i-1，j-1)。如果把第一次計(jì)算得到的f(i-1，j-1)緩存起來(lái)就不需要額外的計(jì)算了，而這也是典型的動(dòng)態(tài)規(guī)劃的思路，下面重點(diǎn)介紹動(dòng)態(tài)規(guī)劃方法。

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

動(dòng)態(tài)規(guī)劃其實(shí)也是一種空間換時(shí)間的算法，通過(guò)緩存計(jì)算的中間值，從而減少重復(fù)計(jì)算的次數(shù)，提高算法的效率。方法一從arr[m-1][n-1]開(kāi)始逆向通過(guò)遞歸來(lái)求解，而動(dòng)態(tài)規(guī)劃要求正向求解，以便利用前面計(jì)算出來(lái)的結(jié)果。

對(duì)于本題而言，顯然，f(i,0)=arr[0][0]+…+arr[i][0]，f[0,j]=arr[0][0]+…+arr[0][j]。根據(jù)遞推公式：f(i,j)=min{f(i-1,j)，f(i,j-1)}+arr[i][j]。從i=1，j=1開(kāi)始順序遍歷二維數(shù)組，可以在遍歷的過(guò)程中求出所有的f(i，j)的值，同時(shí)，把求出的值保存到另外一個(gè)二維數(shù)組中以供后續(xù)使用。當(dāng)然，在遍歷的過(guò)程中可以確定這個(gè)最小值對(duì)應(yīng)的路線，在這種方法中，除了求出最小值外順便還打印出了最小值的路線，實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

funcgetMinPath2(arr[][]int)int{

ifarr==nil||len(arr)==0{

return0

}

row,col:=len(arr),len(arr[0])

//用來(lái)保存計(jì)算的中間值

cache:=make([][]int,row)

fori:=rangecache{

cache[i]=make([]int,col)

}

cache[0][0]=arr[0][0]

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

cache[0][i]=cache[0][i-1]+arr[0][i]

}

forj:=1;j＜row;j++{

cache[j][0]=cache[j-1][0]+arr[j][0]

}

//在遍歷二維數(shù)組的過(guò)程中不斷把計(jì)算結(jié)果保存到cache中

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

forj:=1;j＜col;j++{

//可以確定選擇的路線為arr[i][j-1]

ifcache[i-1][j]＞cache[i][j-1]{

cache[i][j]=cache[i][j-1]+arr[i][j]

fmt.Print("[",i,",",j-1,"]")

}else{//可以確定選擇的路線為arr[i-1][j]

cache[i][j]=cache[i-1][j]+arr[i][j]

fmt.Print("[",i-1,",",j,"]")

}

}

}

fmt.Print("[",row-1,",",col-1,"]")

fmt.Println()

returncache[row-1][col-1]

}

funcmain(){

arr:=[][]int{

{1,4,3},

{8,7,5),

{2,1,5},

}

fmt.Println("方法二")

fmt.Println(getMinPath2(arr))

}

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

路徑：[0,1][0,2][2,0][2,1][2,2]

最小值為：17

算法性能分析：

這種方法對(duì)二維數(shù)組進(jìn)行了一次遍歷，因此，其時(shí)間復(fù)雜度為O(m*n)。此外由于這種方法同樣申請(qǐng)了一個(gè)二維數(shù)組來(lái)保存中間結(jié)果，因此，其空間復(fù)雜度也為O(m*n)。[考點(diǎn)]如何在二維數(shù)組中尋找最短路線

3.

題目描述：

編寫(xiě)一個(gè)截取字符串的函數(shù)，輸入為一個(gè)字符串和字節(jié)數(shù)，輸出為按字節(jié)截取的字符串。但是要保證漢字不被截半個(gè)，例如"人ABC"4，應(yīng)該截為"人AB"，輸入"人ABC們DEF"，6，應(yīng)該輸出為"人ABC"而不是"人ABC+們的半個(gè)"。正確答案：在Go語(yǔ)言中，使用了UTF-8存儲(chǔ)，使用rune即可直接處理。根據(jù)這個(gè)特點(diǎn)，可以采用如下代碼來(lái)完成題目的要求：

packagemain

import(

"fmt"

)

functruncateStr(strstring,nint)string{

arr:=[]rune(str)

returnstring(arr[:n])

}

funcmain(){

str:="人ABC們DEF"

fmt.Println(truncateStr(str,6))

}

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

人ABC[考點(diǎn)]如何截取包含中文的字符串

4.

題目描述：

寫(xiě)一個(gè)函數(shù)，根據(jù)兩個(gè)文件的絕對(duì)路徑算出其相對(duì)路徑。例如

a="/qihoo/app/a/b/c/d/new.c",b="/qihoo/app/1/2/test.c"，那么b相對(duì)于a的相對(duì)路徑是"../../../../1/2/test.c"正確答案：首先找到兩個(gè)字符串相同的路徑(/aihoo/app)，然后對(duì)于剩下的不同的目錄結(jié)構(gòu)(a="/a/b/c/d/new.c",b="/1/2/test.c")，對(duì)于a中的每一個(gè)目錄結(jié)構(gòu)，在b前面加“../”，對(duì)于本題而言，除了相同的目錄前綴外，a還有四級(jí)目錄a/b/c/d，因此，只需要在b="/1/2/test.c"前面增加四個(gè)"../"得到"../../../../1/2/test.c"就是b相對(duì)a的路徑，實(shí)現(xiàn)代碼如下：

packagemain

import(

"bytes"

"errors"

"fmt"

)

funcgetRelativePath(pathl,path2string)string{

ifpath1==""||path2==""{

defererrors.New("參數(shù)不合法")

}

arr1,arr2:=[]rune(path1),[]rune(path2)

//用來(lái)指向兩個(gè)路徑中不同目錄的起始路徑

diff1,diff2:=0,0

len1,len2:=len(arr1),len(arr2)

varrelativePathbytes.Buffer

fori,j:=0,0;i＜len1&&j＜len2;{

//如果目錄相同則往后遍歷

ifarr1[i]==arr2[j]{

ifarr1[i]=='/'{

diff1,diff2=i,j

}

i++

j++

}else{

//不同的目錄

//把path1非公共部分的目錄轉(zhuǎn)換為../

diff1++;//跳過(guò)目錄分隔符/

fordiff1＜len1{

//碰到下一級(jí)目錄

ifarr1[diff1]=='/'{

relativePath.WriteString("../")

}

diff1++

}

//把path2的非公共部分的路徑加到后面

diff2++

relativePath.WriteString(string(arr2[diff2:]))

break

}

}

returnrelativePath.String()

}

funcmain(){

path1:="/qihoo/app/a/b/c/d/new.c"

path2:="/qihoo/app/1/2/test.c"

fmt.Println(getRelatiVePath(path1,Path2))

}

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

../../../../1/2/test.c

算法性能分析：

這種方法的時(shí)間復(fù)雜度與空間復(fù)雜度都為O(max(m，n))(其中，m，n分別為兩個(gè)路徑的長(zhǎng)度)。[考點(diǎn)]如何求相對(duì)路徑

5.

題目描述：

給定一個(gè)字典和兩個(gè)長(zhǎng)度相同的“開(kāi)始”和“目標(biāo)”的單詞。找到從“開(kāi)始”到“目標(biāo)”最小鏈的長(zhǎng)度，如果它存在，那么這樣鏈中的相鄰單詞只有一個(gè)字符不同，而鏈中的每個(gè)單詞都是有效的單詞，即它存在于字典中。可以假設(shè)字典中存在“目標(biāo)”字，且所有目標(biāo)字的長(zhǎng)度相同。

例如：

給定一個(gè)單詞字典為：{pooN，pbcc，zamc，poIc，pbca，pbIc，poIN)

start=TooN

target=pbca

輸出結(jié)果為：7

因?yàn)椋篢ooN(start)-pooN-poIN-poIc-pbIc-pbcc-pbca(target)。正確答案：本題主要的解決方法為：使用BFS的方式從給定的字符串開(kāi)始遍歷所有相鄰(兩個(gè)單詞只有一個(gè)不同的字符)的單詞，直到遍歷找到目標(biāo)單詞，或者遍歷完所有的單詞為止，實(shí)現(xiàn)代碼如下：

packagemain

import(

"container/list"

"fmt"

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

)

typeQItemstruct{

wordstring

lenint

}

funcNewQItem(wordstring,lenint)*QItem{

return&QItem{word,len}

}

/*判斷兩個(gè)字符串是否只有一個(gè)不同的字符*/

funcisadjacent(a,bstring)bool{

diff:=0

fori,v:=rangea

ifbyte(v)!=b[i]{

diff++

}

ifdiff＞1{

returnfalse

}

}

ifdiff==1{

returntrue

}else{