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

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

題目描述：

給定一個字典和兩個長度相同的“開始”和“目標”的單詞。找到從“開始”到“目標”最小鏈的長度，如果它存在，那么這樣鏈中的相鄰單詞只有一個字符不同，（江南博哥）而鏈中的每個單詞都是有效的單詞，即它存在于字典中?？梢约僭O(shè)字典中存在“目標”字，且所有目標字的長度相同。

例如：

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

start=TooN

target=pbca

輸出結(jié)果為：7

因為：TooN(start)-pooN-poIN-poIc-pbIc-pbcc-pbca(target)。正確答案：本題主要的解決方法為：使用BFS的方式從給定的字符串開始遍歷所有相鄰(兩個單詞只有一個不同的字符)的單詞，直到遍歷找到目標單詞，或者遍歷完所有的單詞為止，實現(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}

}

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

funcisadjacent(a,bstring)bool{

diff:=0

fori,v:=rangea

ifbyte(v)!=b[i]{

diff++

}

ifdiff＞1{

returnfalse

}

}

ifdiff==1{

returntrue

}else{

returnfalse

}

}

/*返回從start到target的最短鏈*/

funcshortestChainLen(start,targetstring,D*list.List)int{

Q:=NewSliceQueue()

item:=NewQItem(start,1)

Q.EnQueue(item)

for!Q.IsEmpty(){

cur:=Q.DeQueue().(*Qltem)

varn*list.Element

fore:=D.FrontO;e!=nil;e=n{

n=e.Next()

tmp:=e.Value.(string)

ifisadjacent(cur.word,tmp){

item.word=tmp

item.len=cur.len+1

Q.EnQueue(item)//把這個字符串放入到隊列中

//把這個字符串從隊列中刪除來避免被重復遍歷

D.Remove(e)

//通過轉(zhuǎn)變后得到了目標字符

iftmp==target{

returnitem.len

}

}

}

}

return0

}

funcmain(){

D:=list.New()

D.PushBack("pooN")

D.PushBack("pbcc")

D.PushBack("zamc")

D.PushBack("poIc")

D.PushBack("pbca")

D.PushBack("pblc")

D.PushBack("poIN")

start:="TooN"

target:="pbca"

fmt.Println("最短的鏈條的長度為:",shortestChainLen(start,target,D))

}

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

最短的鏈條的長度為：7

算法性能分析：

這種方法的時間復雜度為O(n2m)，其中，n為單詞的個數(shù)，m為字符串的長度。[考點]如何查找到達目標詞的最短鏈長度

2.

題目描述：

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

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

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

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

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

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

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

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

packagemain

import(

"sort"

"fmt"

)

typeLongestWordstruct{

}

//判斷字符串str是否在字符串數(shù)組中

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

for_,v:=rangestrArr{

ifstr==v{

returntrue

}

}

retumfalse

}

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

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

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

ll:=len(word)

//遞歸的結(jié)束條件，當字符串長度為0時，說明字符串已經(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ù)組中其他字符串組成的最長字符串

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

//對字符串由大到小排序

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

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

})

//貪心地從最長的字符串開始判斷

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("最長的字符串為:",logestStr)

}

}

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

最長的字符串為：testbattingcat

算法性能分析：

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

3.

題目描述：

有兩個有序的集合，集合中的每個元素都是一段范圍，求其交集，例如集合{[4，8]，[9，13]}和{[6，12]}的交集為{[6，8]，[9，12]}。正確答案：方法一：蠻力法

最簡單的方法就是遍歷兩個集合，針對集合中的每個元素判斷是否有交集，如果有，則求出它們的交集，實現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

typeMySetstruct{

Minint

Maxint

}

funcgetIntersectionSub(s1,s2*MySet)*MySet{

ifs1.Min＜s2.Min{

ifs1.Max＜s2.Min{

returnnil

}elseifs1.Max＜=s2.Max

return&MySet{s2.Min,s1.Max}

}else{

return&MySet{s2.Min,s2.Max}

}

}elseifs1.Min＜s2.Max{

ifs1.Max＜=s2.Max{

return&MySet{s1.Min,s1.Max}

}else{

return&MySet{s1.Min,s2.Max}

}

}

returnnil

}

funcgetIntersection1(l1,l2[]*MySet)[]*MySet{

result:=make([]*MySet,0)

for_,v1:=rangel1{

for_,v2:=range;2{

s:=getIntersectionSub(v1,v2)

ifs!=nil{

result=append(result,s)

}

}

}

returnresult

}

funcmain(){

l1:=[]*MySet{

&MySet{4,8},

&MySet{9,13},

}

l2:=[]*MySet{

&MySet{6,12},

}

fmt.Println("暴力法")

result:=getlntersectionl(l1,l2)

for_,v:=rangeresult{

fmt.Println("[",v.Min,",",v.Max,"]")

}

}

代碼運行結(jié)果為：

[6，8]

[9，12]

算法性能分析：

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

方法二：特征法

上述這種方法顯然沒有用到集合有序的特點，因此，它不是最佳的方法。假設(shè)兩個集合為s1，s2。當前比較的集合為s1[i]和s2[j]，其中，i與j分別表示的是集合s1與s2的下標?？梢苑譃槿缦聨追N情況：

(1)s1集合的下界小于s2的上界，如下圖所示：

在這種情況下，s1[i]和s2[j]顯然沒有交集，那么接下來只有s1[i+1]與s2[j]才有可能會有交集。

(2)s1的上界介于s2的下界與上界之間

在這種情況下，s1[i]和s2[j]有交集(s2[j]的下界和s1[i]的上界)，那么接下來只有s1[i+1]與s2[j]才有可能會有交集。

(3)s1包含s2

在這種情況下，s1[i]和s2[j]有交集(交集為s2[j])，那么接下來只有s1[i]與s2[j+1]才有可能會有交集。

(4)s2包含s1

在這種情況下，s1[i]和s2[j]有交集(交集為s1[i])，那么接下來只有s1[i+1]與s2[j]才有可能會有交集。

(5)s1的下界介于s1的下界與上界之間

在這種情況下，s1[i]和s2[j]有交集(交集為s1[i]的下界和s2[j]的上界)，那么接下來只有s1[i]與s2[j+1]才有可能會有交集。

(6)s2的上界小于s1的下界

在這種情況下，s1[i]和s2[j]顯然沒有交集，那么接下來只有s1[i]與s2[j+1]才有可能會有交集。

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

funcgetIntersection2(l1,l2[]*MySet)[]*MySet{

result:=make([]*MySet,0)

fori,j:=0,0;i＜len(l1)&&j＜len(l2);{

s1:=l1[i]

s2:=l2[j]

ifs1.Min＜s2.Min{

ifs1.Max＜s2.Min{

i++

}elseifs1.Max＜=s2.Max{

result=append(result,&MySet{s2.Min,s1.Max})

i++

}else{

result=append(result,&MySet{s2.Min,s2.Max})

j++

}

}elseifs2.Min＜=s2.Max{

ifs1.Max＜=s2.Max{

result=append(result,&MySet{s1.Min,s1.Max})

i++

}else{

result=append(result,&MySet{s1.Min,s2.Max})

j++

}

}else{

j++

}

}

returnresult

}

算法性能分析：

這種方法的時間復雜度為O(n1+n2)，其中n1、n2分別為兩個集合的大小。[考點]如何求兩個有序集合的交集

4.

題目描述：

兩棵二叉樹相等是指這兩棵二叉樹有著相同的結(jié)構(gòu)，并且在相同位置上的結(jié)點有相同的值。如何判斷兩棵二叉樹是否相等?正確答案：如果兩棵二叉樹root1、root2相等，那么root1與root2結(jié)點的值相同，同時它們的左右孩子也有著相同的結(jié)構(gòu)，并且對應(yīng)位置上結(jié)點的值相等，即root1.data==root2.data，并且root1的左子樹與root2的左子樹相等，root1的右子樹與root2的右子樹相等。根據(jù)這個條件，可以非常容易地寫出判斷兩棵二叉樹是否相等的遞歸算法。實現(xiàn)代碼如下：

packagemain

import(

"fmt"

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

)

//判斷兩棵二叉樹是否相等

/參數(shù)：root1與root2分別為兩棵二叉樹的根結(jié)點

//返回值：true：如果兩棵樹相等則返回true，否則返回false

funcIsEqual(root1*BNode,root2*BNode)bool{

ifroot1==nil&&root2==nil{

returntrue

}

ifroot1==nil&&root2!=nil{

returnfalse

}

ifroot1!=nil&&root2==nil{

returnfalse

}

ifroot1.Data==root2.Data{

returnIsEqual(root1.LeftChild,root2.LeftChild)&&IsEqual(root1.RightChild,root2.RightChild)

}

returnfalse

}

funcCreateTree()*BNode{

root:=&BNode{}

node1:=&BNode{}

node2:=&BNode{}

node3:=&BNode{}

node4:=&BNode{)

root.Data=6

node1.Data=3

node2.Data=-7

node3.Data=-1

node4.Data=9

root.LeftChild=node1

root.RightChild=node2

node1.LeftChild=node3

node1.RightChild=node4

returnroot

}

funcmain(){

root1:=CreateTree()

root2:=CreateTree()

ifIsEq