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

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

題目描述：

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

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

方法二：快慢指針遍歷法

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

2.

題目描述：

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

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

packagemare

import(

"bytes"

"fmt"

)

funcintToBinary(nint)string{

ifn＜0{

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

return""

}

hexNum:=8*8;//二進(jìn)制的位數(shù)(long占8個(gè)字節(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的二進(jìn)制輸出為:",intToBinary(10))

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

}

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

10的二進(jìn)制輸出為：0000000000000000000000000000000000000000000000000000000000001010

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

3.

題目描述：

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

packagemain

import(

"strconv"

"fmt"

)

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

funcxor1(x,yint)int{

BITS:=strconv.IntSize//以具體平臺(tái)為例

res:=0

varxoredBitint

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

/*獲取x與y當(dāng)前的bit值*/

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

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

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

if(b1=b2){

xoredBit=0

}else{

xoredBit=1

}

res＜＜=1

res|=xoredBit

}

returnres

}

funcmain(){

fmt.Println("方法一")

fmt.Println(xor1(3,5))

}

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

6

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

funcxor2(x,yint)int{

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

}

算法性能分析：

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

4.

題目描述：

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

packagemain

import(

"fmt"

)

funcisAllocable(d,p[]int)bool{

//磁盤分區(qū)下標(biāo)

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("分配失敗")

}

}

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

分配成功

算法性能分析：

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

5.

題目描述：

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

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

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

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

(1)f(i+1，j+1)=0，當(dāng)str1[i+1]!=str2[j+1]時(shí)。

(2)f(i+1，j+1)=f(i，j)+1，當(dāng)str1[i+1]==str2[j+1]時(shí)。

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

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

packagemain

import(

"bytes"

"fmt"

)

//方法功能：獲取兩個(gè)字符串的最長(zhǎng)公共字串

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

funcgetMaxSubStr(str1,str2string)string{

len1:=len(str1)

len2:=len(str2)

varbufbytes.Buffer

maxI:=0

//用來(lái)記錄最長(zhǎng)公共字串最后一個(gè)字符的位置

max:=0

//申請(qǐng)新的空間來(lái)記錄公共字串長(zhǎng)度信息

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

fori,_:=rangeM{

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

}

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

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("動(dòng)態(tài)規(guī)劃法")

fmt.Printin(getMaxSubStr(str1,str2))

}

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

cad

算法性能分析：

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

方法二：滑動(dòng)比較法

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

v如上圖所示，這兩個(gè)字符串的最長(zhǎng)公共子串為“bc”，實(shí)現(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