




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
Go程序員面試分類模擬題27論述題1.
題目描述:
給定一個字典和兩個長度相同的“開始”和“目標”的單詞。找到從“開始”到“目標”最小鏈的長度,如果它存在,那么這樣鏈中的相鄰單詞只有一個字符不同,(江南博哥)而鏈中的每個單詞都是有效的單詞,即它存在于字典中??梢约僭O字典中存在“目標”字,且所有目標字的長度相同。
例如:
給定一個單詞字典為:{pooN,pbcc,zamc,poIc,pbca,pbIc,poIN)
start=TooN
target=pbca
輸出結果為:7
因為:TooN(start)-pooN-poIN-poIc-pbIc-pbcc-pbca(target)。正確答案:本題主要的解決方法為:使用BFS的方式從給定的字符串開始遍歷所有相鄰(兩個單詞只有一個不同的字符)的單詞,直到遍歷找到目標單詞,或者遍歷完所有的單詞為止,實現代碼如下:
packagemain
import(
"container/list"
"fmt"
."/isdamir/gotype"http://引入定義的數據結構
)
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)
//通過轉變后得到了目標字符
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))
}
程序的運行結果為
最短的鏈條的長度為:7
算法性能分析:
這種方法的時間復雜度為O(n2m),其中,n為單詞的個數,m為字符串的長度。[考點]如何查找到達目標詞的最短鏈長度
2.
題目描述:
給定一個字符串數組,找出數組中最長的字符串,使其能由數組中其他的字符串組成。例如給定字符串數組{“test”,“tester”,“testertest”,“testing”,“apple”,“seattle”,“banana”,“batting”,“ngcat”,“batti”,“bat”,“testingtester”,“testbattingcat”}。滿足題目要求的字符串為“testbattingcat”,因為這個字符串可以由數組中的字符串“test”,“batti”和“ngcat”組成。正確答案:既然題目要求找最長的字符串,那么可以采用貪心的方法,首先對字符串由大到小進行排序,從最長的字符串開始查找,如果能由其他字符串組成,就是滿足題目要求的字符串。接下來就需要考慮如何判斷一個字符串能否由數組中其他的字符串組成,主要的思路為:找出字符串的所有可能的前綴,判斷這個前綴是否在字符數組中,如果在,那么用相同的方法遞歸地判斷除去前綴后的子串是否能由數組中其他的子串組成。
以題目中給的例子為例,首先對數組進行排序,排序后的結果為:{“testbattingcat”,“testingtester”,“testertest”,“testing”,“seattle”,“batting”,“tester”,“banana”,“apple”,“ngcat”,“batti”,“test”,“bat”}。首先取“testbattingcat”進行判斷,具體步驟如下:
(1)分別取它的前綴“t”,“te”,“tes”都不在字符數組中,“test”在字符數組中。
(2)接著用相同的方法遞歸地判斷剩余的子串“battingcat”,同理,“b”,“ba”都不在字符數組中,“bat”在字符數組中。
(3)接著判斷“tingcat”,通過判斷發(fā)現“tingcat”不能由字符數組中其他字符組成。因此,回到上一個遞歸調用的子串接著取字符串的前綴進行判斷。
(4)回到上一個遞歸調用,待判斷的字符串為“batcingcat”,當前比較到的前綴為“bat”,接著取其他可能的前綴“batt”,“battt”都不在字符數組中,“battti”在字符數組中。接著判斷剩余子串“ngcat”。
(5)通過比較發(fā)現“ngcat”在字符數組中。因此,能由其他字符組成的最長字符串為“testbattingcat”。
實現代碼如下:
packagemain
import(
"sort"
"fmt"
)
typeLongestWordstruct{
}
//判斷字符串str是否在字符串數組中
func(p*LongestWord)find(strArr[]string,strstring)bool{
for_,v:=rangestrArr{
ifstr==v{
returntrue
}
}
retumfalse
}
//方法功能:判斷字符串word是否能由數組strArray中的其他單詞組成
//參數:word為待判斷的后綴子串,length為待判斷字符串的長度
func(p*LongestWord)isContain(strArr[]string,wordstring,lengthint)bool{
ll:=len(word)
//遞歸的結束條件,當字符串長度為0時,說明字符串已經遍歷完了
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
}
//找出能由數組中其他字符串組成的最長字符串
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)
}
}
程序的運行結果為
最長的字符串為:testbattingcat
算法性能分析:
排序的時間復雜度為O(nlogn),假設單詞的長度為m,那么有m種前綴,判斷一個單詞是否在數組中的時間復雜度為O(mn),由于總共有n個字符串,因此,判斷所需的時間復雜度為O(m*n2)。因此,總的時間復雜度為O(nlogn+m*n2)。當n比較大的時候,時間復雜度為O(n2)。[考點]如何找到由其他單詞組成的最長單詞
3.
題目描述:
有兩個有序的集合,集合中的每個元素都是一段范圍,求其交集,例如集合{[4,8],[9,13]}和{[6,12]}的交集為{[6,8],[9,12]}。正確答案:方法一:蠻力法
最簡單的方法就是遍歷兩個集合,針對集合中的每個元素判斷是否有交集,如果有,則求出它們的交集,實現代碼如下:
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,"]")
}
}
代碼運行結果為:
[6,8]
[9,12]
算法性能分析:
這種方法的時間復雜度為O(n2)。
方法二:特征法
上述這種方法顯然沒有用到集合有序的特點,因此,它不是最佳的方法。假設兩個集合為s1,s2。當前比較的集合為s1[i]和s2[j],其中,i與j分別表示的是集合s1與s2的下標。可以分為如下幾種情況:
(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]才有可能會有交集。
根據以上分析給出實現代碼如下:
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.
題目描述:
兩棵二叉樹相等是指這兩棵二叉樹有著相同的結構,并且在相同位置上的結點有相同的值。如何判斷兩棵二叉樹是否相等?正確答案:如果兩棵二叉樹root1、root2相等,那么root1與root2結點的值相同,同時它們的左右孩子也有著相同的結構,并且對應位置上結點的值相等,即root1.data==root2.data,并且root1的左子樹與root2的左子樹相等,root1的右子樹與root2的右子樹相等。根據這個條件,可以非常容易地寫出判斷兩棵二叉樹是否相等的遞歸算法。實現代碼如下:
packagemain
import(
"fmt"
."/isdamir/gotype"http://引入定義的數據結構
)
//判斷兩棵二叉樹是否相等
/參數:root1與root2分別為兩棵二叉樹的根結點
//返回值: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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年地鐵隧道二維位移自動監(jiān)測系統項目建議書
- 以學生為中心的教育心理學課堂實踐
- 智慧城市安防升級保障公共安全技術合作新篇章
- 提升學生自主學習動力的教育心理學方法論
- 數字化校園教育園區(qū)的智能升級
- 商業(yè)教育中技術應用的新趨勢
- 教育心理學在個人自學策略中的應用
- 教育大數據下的學生個性化發(fā)展研究
- 2025屆河北省秦皇島市盧龍中學物理高二下期末學業(yè)質量監(jiān)測模擬試題含解析
- 學習動力與學業(yè)成就的關系研究
- 2024-2029全球及中國福利管理系統行業(yè)市場發(fā)展分析及前景趨勢與投資發(fā)展研究報告
- 新標準英語小學五年級下各模塊習題
- 開票稅點自動計算器
- 中華護理學會成人腸內營養(yǎng)支持護理團標解讀
- 2022-2023年人教版八年級化學上冊期末測試卷(及參考答案)
- DLT 5175-2021 火力發(fā)電廠熱工開關量和模擬量控制系統設計規(guī)程-PDF解密
- 全國中醫(yī)優(yōu)才計劃
- 排風工程全過程BIM建模與協同設計
- 提升員工服務能力的實用培訓方案
- 數字化系列研究之財務數智化篇:大型集團企業(yè)財務管理的數智化
- 鍋爐安裝知識講座
評論
0/150
提交評論