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

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

題目描述：

單鏈表有環(huán)指的是單鏈表中某個結(jié)點的next域指向的是鏈表中在它之前的某一個結(jié)點，這樣在鏈表的尾部形成一個環(huán)形結(jié)構(gòu)。如何判斷單鏈表是否有環(huán)存在?（江南博哥）正確答案：方法一：蠻力法

定義一個Set用來存放結(jié)點的引用，并將其初始化為空，從鏈表的頭結(jié)點開始向后遍歷，每遍歷到一個結(jié)點就判斷Set中是否引用這個結(jié)點，如果沒有，說明這個結(jié)點是第一次訪問，還沒有形成環(huán)，那么將這個引用結(jié)點添加到指針Set中去。如果在Set中找到了同樣的結(jié)點，那么說明這個結(jié)點已經(jīng)被訪問過了，于是就形成了環(huán)。這種方法的時間復(fù)雜度為O(n)，空間復(fù)雜度也為O(n)。

方法二：快慢指針遍歷法

定義兩個指針fast(快)與slow(慢)，二者的初始值都指向鏈表頭，指針slow每次前進一步，指針fast每次前進兩步，兩個指針同時向前移動，快指針每移動一次都要跟慢指針比較，如果快指針等于慢指針，就證明這個鏈表是帶環(huán)的單向鏈表，否則，證明這個鏈表是不帶環(huán)的循環(huán)鏈表。[考點]如何檢測一個較大的單鏈表是否有環(huán)

2.

題目描述：

如何把十進制數(shù)(long型)分別以二進制和十六進制形式輸出?正確答案：由于十進制數(shù)本質(zhì)上還是以二進制的方式來存儲的，在實現(xiàn)的時候可以把十進制數(shù)看成二進制的格式，通過移位的方式計算出每一位的值。為了方便起見，下面以byte類型的數(shù)為例介紹實現(xiàn)方法，假如現(xiàn)在要把十進制數(shù)7以二進制的形式來輸出，由于7的二進制的表示為00000111，計算第6位二進制碼是0還是1的方法為：首先把這個值左移6位得到11000000，然后再右移7位，得到00000001，移位后得到的值就是第6位二進制碼的值。由此可以得出如下計算方法：假設(shè)十進制數(shù)對應(yīng)的二進制數(shù)的長度為binNum，那么計算十進制數(shù)n的第i位二進制碼值的公式為n＜＜i＞＞binNum-1。通過這種計算方法可以得到每一位的值，然后把對應(yīng)的值存儲在字符數(shù)組中即可。

上面介紹的方法使用的是移位操作，雖然效率比較高，但是難以理解。下面介紹一種簡單的轉(zhuǎn)換為十六進制的方法?？梢允褂妙愃朴谑M制轉(zhuǎn)二進制的方法。把十進制的數(shù)對16求余數(shù)。得到的結(jié)果就是十六進制的最后一位，然后把這個十進制數(shù)除以16，用得到的數(shù)繼續(xù)使用相同的方法計算其他的位數(shù)。需要注意的是對于十六進制10～15需要轉(zhuǎn)換為A～F。示例代碼如下：

packagemare

import(

"bytes"

"fmt"

)

funcintToBinary(nint)string{

ifn＜0{

fmt.Println("不支持負數(shù)")

return""

}

hexNum:=8*8;//二進制的位數(shù)(long占8個字節(jié))

varpBinarybytes.Buffer

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

//先左移i位把pBinary[i]移到最高位，然后右移hexNum-1位把pBinary[i]移到最后一位

tmpBinary:=(n＜＜uint(i))＞＞(uint(hexNum)-1)

if(tmpBinary==0){

pBinary.WriteRune('0')

}else{

pBinary.WriteRune('1')

}

}

returnpBinary.String()

}

funcintToHex(sint)string{

hex:=""

remainder:=0

fors!=0{

remainder=s%16

if(remainder＜10){

hex=string(remainder+'0')+hex

}else{

hex=string(remainder-10+'A')+hex

}

s=s＞＞4

}

returnhex

}

funcmain(){

fmt.Println("10的二進制輸出為:",intToBinary(10))

fmt.Println("10的十六進制輸出為:",intToHex(10))

}

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

10的二進制輸出為：0000000000000000000000000000000000000000000000000000000000001010

10的十六進制輸出為：A[考點]如何把十進制數(shù)(long型)分別以二進制和十六進制形式輸出

3.

題目描述：

不使用^操作實現(xiàn)異或運算。正確答案：最簡單的方法是遍歷兩個整數(shù)的所有的位，如果兩個數(shù)的某一位相等，那么結(jié)果中這一位的值為0，否則結(jié)果中這一位的值為1，實現(xiàn)代碼如下：

packagemain

import(

"strconv"

"fmt"

)

//獲取x與y異或的結(jié)果

funcxor1(x,yint)int{

BITS:=strconv.IntSize//以具體平臺為例

res:=0

varxoredBitint

fori:=BITS-1;i＞=0;i--{

/*獲取x與y當前的bit值*/

b1:=(x&(1＜＜uint(i)))＞0

b2:=(y&(1＜＜uint(i)))＞0

/*只有這兩位都是1或0的時候結(jié)果為0*/

if(b1=b2){

xoredBit=0

}else{

xoredBit=1

}

res＜＜=1

res|=xoredBit

}

returnres

}

funcmain(){

fmt.Println("方法一")

fmt.Println(xor1(3,5))

}

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

6

下面介紹另外一種更加簡便的實現(xiàn)方法：x^y=(x|y)&(～x|～y)，其中x|y表示如果在x或y中的bit為1，那么結(jié)果的這一個bit的值也為1，顯然這個結(jié)果包括三部分：這個bit只有在x中為1，只有在y中為1，在x和y中都為1，要在這個基礎(chǔ)上計算出異或的結(jié)果，顯然要去掉第三種情況，也就是說去掉在x和y中都為1的情況，而當一個bit在x和y中都為1的時候“～x|～y”的值為0，因此(x|y)&(～x|～y)的值等于x^y。實現(xiàn)代碼如下：

funcxor2(x,yint)int{

return(x|y)&(^x|^y)//這里是golang的取反語法，不是異或

}

算法性能分析：

這種方法的時間復(fù)雜度為O(n)。[考點]如何不使用^操作實現(xiàn)異或運算

4.

題目描述：

有N個磁盤，每個磁盤大小為D[i](i=0…N-1)，現(xiàn)在要在這N個磁盤上"順序分配"M個分區(qū)，每個分區(qū)大小為P[j](j=0…M-1)，順序分配的意思是：分配一個分區(qū)P[j]時，如果當前磁盤剩余空間足夠，則在當前磁盤分配；如果不夠，則嘗試下一個磁盤，直到找到一個磁盤D[i+k]可以容納該分區(qū)，分配下一個分區(qū)P[j+1]時，則從當前磁盤D[i+k]的剩余空間開始分配，不在使用D[i+k]之前磁盤未分配的空間，如果這M個分區(qū)不能在這N個磁盤完全分配，則認為分配失敗，請實現(xiàn)函數(shù)，isallocable判斷給定N個磁盤(數(shù)組D)和M個分區(qū)(數(shù)組P)，是否會出現(xiàn)分配失敗的情況?舉例：磁盤為[120，120，120]，分區(qū)為[60，60，80，20，80]可分配，如果為[60，80，80，20，80]，則分配失敗。正確答案：本題的主要思路如下：對所有的分區(qū)進行遍歷，同時用一個變量dIndex記錄上次分配磁盤的下標，初始化為0；對于每個分區(qū)，從上次分配的磁盤開始繼續(xù)分配，如果沒有足夠的空間，則順序找其他的磁盤，直到找到合適的磁盤為止，進行分配；如果找不到合適的磁盤，則分配失敗，實現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

funcisAllocable(d,p[]int)bool{

//磁盤分區(qū)下標

dIndex:=0

for_,v:=rangep{

//找到符合條件的磁盤

fordIndex＜len(d)&&v＞d[dlndex]{

dIndex++

}

//沒有可用的磁盤

ifdIndex＞=len(d){

returnfalse

}

//給分區(qū)分配磁盤

d[dIndex]-=v

}

returntrue

}

funcmain(){

//磁盤

d:=[]int{120,120,120}

//分區(qū)

p:=[]int{60,60,80,20,80}

ifisAllocable(d,p){

fmt.Println("分配成功")

)else{

fmt.Println("分配失敗")

}

}

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

分配成功

算法性能分析：

這種方法使用了雙重循環(huán)，因此，時間復(fù)雜度為O(mn)。[考點]如何對磁盤分區(qū)

5.

題目描述：

找出兩個字符串的最長公共子串，例如字符串“abccade”與字符串“dgcadde”的最長公共子串為“cad”。正確答案：對于這道題而言，最容易想到的方法就是采用蠻力的方法，假設(shè)字符串s1與s2的長度分別為len1和len2(假設(shè)len1＞=len2)，首先可以找出s2的所有可能的子串，然后判斷這些子串是否也是s1的子串，通過這種方法可以非常容易地找出兩個字符串的最長子串。當然，這種方法的效率是非常低下的，主要原因為：s2中的大部分字符需要與s1進行很多次的比較。那么是否有更好的方法來降低比較的次數(shù)呢?下面介紹兩種通過減少比較次數(shù)從而降低時間復(fù)雜度的方法。

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

通過把中間的比較結(jié)果記錄下來，從而可以避免字符的重復(fù)比較。主要思路如下：

首先定義二元函數(shù)f(i，j)：表示分別以s1[i]，s2[j]結(jié)尾的公共子串的長度，顯然，f(0，j)=0(j＞=0)，f(i，0)=0(i＞=0)，那么，對于f(i+1，j+1)而言，則有如下兩種取值：

(1)f(i+1，j+1)=0，當str1[i+1]!=str2[j+1]時。

(2)f(i+1，j+1)=f(i，j)+1，當str1[i+1]==str2[j+1]時。

根據(jù)這個公式可以計算出f(i，j)(0=＜i＜=len(s1)，0=＜j＜=len(s2))所有的值，從而可以找出最長的子串，如下圖所示：

通過上圖所示的計算結(jié)果可以求出最長公共子串的長度max與最長子串結(jié)尾字符在字符數(shù)組中的位置maxI，由這兩個值就可以唯一確定一個最長公共子串為“cad”，這個子串在數(shù)組中的起始下標為：maxI-max=3，子串長度為max=3。實現(xiàn)代碼如下：

packagemain

import(

"bytes"

"fmt"

)

//方法功能：獲取兩個字符串的最長公共字串

//輸入?yún)?shù)：str1和str2為指向字符的指針

funcgetMaxSubStr(str1,str2string)string{

len1:=len(str1)

len2:=len(str2)

varbufbytes.Buffer

maxI:=0

//用來記錄最長公共字串最后一個字符的位置

max:=0

//申請新的空間來記錄公共字串長度信息

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

fori,_:=rangeM{

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

}

//通過利用遞歸公式填寫新建的二維數(shù)組(公共字串的長度信息)

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

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

ifstr1[i-1]==str2[j-1]{

M[i][j]=M[i-1][j-1]+1

ifM[i][j]＞max{

max=M[i][j]

maxI=i

}

}else{

M[i][j]=0

}

}

}

fori:=maxI-max;i＜maxI;i++{

buf.WriteByte(str1[i])

}

returnbur.String()

}

funcmain(){

str1:="abccade"

str2:="dgcadde"

fmt.Println("動態(tài)規(guī)劃法")

fmt.Printin(getMaxSubStr(str1,str2))

}

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

cad

算法性能分析：

由于這種方法使用了二重循環(huán)分別遍歷兩個字符數(shù)組，因此，時間復(fù)雜度為O(m*n)(其中，m和n分別為兩個字符串的長度)，此外，由于這種方法申請了一個m*n的二維數(shù)組，因此，算法的空間復(fù)雜度也為O(m+n)。很顯然，這種方法的主要缺點為申請了m*n個額外的存儲空間。

方法二：滑動比較法

如下圖所示，這種方法的主要思路為：保持s1的位置不變，然后移動s2，接著比較它們重疊的字符串的公共子串(記錄最大的公共子串的長度maxLen，以及最長公共子串在s1中結(jié)束的位置maxLenEnd1)，在移動的過程中，如果當前重疊子串的長度大于maxLen，則更新maxLen為當前重疊子串的長度。最后通過maxLen和maxLenEnd1就可以找出它們最長的公共子串。實現(xiàn)方法如下圖所示：

v如上圖所示，這兩個字符串的最長公共子串為“bc”，實現(xiàn)代碼如下：

packagemain

import(

"bytes"

"fmt"

)

funcgetMaxSubStr2(str1,str2string)string{

len1:=len(str1)

len2:=len(str2)

varbufbytes.Buffer

maxLen:=0

maxLenEnd1:=0

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

s1begin:=0

s2begin:=0

tmpMaxLne:=0

ifi＜len1{

s1begin=len1-i

}else{

s