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

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

題目描述：

如何判斷1024!末尾有多少個0正確答案：方法一：蠻力法

最簡單的方法就是計算出1024!的值，然后判斷末尾有多少個0，但是這種方（江南博哥）法有兩個非常大的缺點：第一，算法的效率非常低下；第二，當(dāng)這個數(shù)字比較大的時候直接計算階乘可能會導(dǎo)致數(shù)據(jù)溢出，從而導(dǎo)致計算結(jié)果出現(xiàn)偏差。因此，下面給出一種比較巧妙的方法。

方法二：因子法

5與任何一個偶數(shù)相乘都會增加末尾0的個數(shù)，由于偶數(shù)的個數(shù)肯定比5的個數(shù)多，因此，1～1024所有數(shù)字中有5的因子的數(shù)字的個數(shù)決定了1024!末尾0的個數(shù)。因此，只需要統(tǒng)計因子5的個數(shù)即可。此外5與偶數(shù)相乘會使末尾增加一個0，25(有兩個因子5)與偶數(shù)相乘會使末尾增加兩個0，125(有三個因子5)與偶數(shù)相乘會使末尾增加3個0，625(有四個因子5)與偶數(shù)相乘會使末尾增加四個0。對于本題而言：

是5的倍數(shù)的數(shù)有：a1=1024/5=204個

是25的倍數(shù)的數(shù)有：a2=1024/25=40個(a1計算了25中的一個因子5)

是125的倍數(shù)的數(shù)有：a3=1024/125=8個(a1，a2分別計算了125中的一個因子5)

是625的倍數(shù)的數(shù)有：a4=1024/625=1個(a1，a2，a3分別計算了625中的一個因子5)

所以，1024!中總共有a1+a2+a3+a4=204+40+8+1=253個因子5。因此，末尾總共有253個0。根據(jù)以上思路實現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

funczeroCount(nint)int{

count:=0

forn＞0{

n=n/5

count+=n

}

returncount

}

funcmain(){

fmt.Println("1024!末尾0的個數(shù)為:",zeroCount(1024))

}

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

1024!末尾0的個數(shù)為：253

算法性能分析：

由于這種方法循環(huán)的次數(shù)為n/5，因此，算法時間復(fù)雜度為O(n)。[考點]如何判斷1024!末尾有多少個0

2.

題目描述：

如何比較a、b兩個數(shù)的大小，不能使用大于、小于以及if語句。正確答案：方法一：絕對值法

根據(jù)絕對值的性質(zhì)可知，如果|a-b|==a-b，那么max(a，b)=a，否則max(a，b)=b，根據(jù)這個思路實現(xiàn)代碼如下：

packagemain

import(

"fmt"

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

)

funcmax1(a,bint)int{

ifAbs(a-b)==a-b{

returna

}else{

returnb

}

}

funcmain(){

fmt.Println("絕對值法")

fmt.Println(max1(5,6))

}

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

6

需要注意的是，由于宏定義不同于函數(shù)定義，在上述宏定義中，a，b必須要有括號，否則當(dāng)a，b的值為表達式的時候會出現(xiàn)意想不到的錯誤。

方法二：二進制法

如果a＞b，那么a-b的二進制最高位為0，與任何數(shù)的與操作的結(jié)果還是0；如果a-b為負數(shù)，那么a-b的二進制最高位為1，與0x80000000(最高位為1，其他位為0，假設(shè)a與b都占4個字節(jié))執(zhí)行與操作之后為結(jié)果為1。由此根據(jù)兩個數(shù)的差的二進制最高位的值就可以比較兩個數(shù)的大小，實現(xiàn)代碼如下：

funcmax2(a,bint)int{

if(a-b)&(1＜＜31)!=0{

returnb

}else{

returna

}

}[考點]如何按要求比較兩個數(shù)的大小

3.

題目描述：

一個有序數(shù)列，序列中的每一個值都能夠被2或者3或者5所整除，1是這個序列的第一個元素。求第1500個值是多少。正確答案：方法一：蠻力法

最簡單的方法就是用一個計數(shù)器來記錄滿足條件的整數(shù)的個數(shù)，然后從1開始遍歷整數(shù)，如果當(dāng)前遍歷的數(shù)能被2或者3或者5整除，則計數(shù)器的值加1，當(dāng)計數(shù)器的值為1500時，當(dāng)前遍歷到的值就是所要求的值。根據(jù)這個思路實現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

funcsearth1(nint)int{

i,count:=0,0

fortrue{

i++

if(i%2==0||i%3==0||i%5==0){

count++

}

ifcount==n{

break

}

}

returni

}

funcmain(){

fmt.Println("方法一")

fmt.Println(searthl(1500))

}

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

2045

方法二：數(shù)字規(guī)律法

首先可以很容易得到2，3和5的最小公倍數(shù)為30，此外，1～30這個區(qū)間內(nèi)滿足條件的數(shù)有22個{2，3，4，5，6，8，9，10，12，14，15，16，18，20，21，22，24，25，26，27，28，30}，由于最小公倍數(shù)為30，我們可以猜想，滿足條件的數(shù)字是否具有周期性(周期為30)呢?通過計算可以發(fā)現(xiàn)，31～60這個區(qū)間內(nèi)滿足條件的數(shù)也恰好有22個{32，33，34，35，36，38，39，40，42，44，45，46，48，50，51，52，54，55，56，57，58，60}，從而發(fā)現(xiàn)這些滿足條件的數(shù)具有周期性(周期為30)。由于1500/22=68，1500%68=4，從而可以得出第1500個數(shù)經(jīng)過了68個周期，然后在第69個周期中取第四個滿足條件的數(shù){2，3，4，5}。從而可以得出第1500個數(shù)為68*30+5=2045。根據(jù)這個思路實現(xiàn)代碼如下：

funcsearth2(nint)int{

a:=[]int{0,2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30}

return(n/22)*30+a[n%22]

}

算法性能分析：

方法二的時間復(fù)雜度為O(1)，此外，方法二使用了22個額外的存儲空間。方法二的計算方法可以用來分析方法一的執(zhí)行效率，從方法二的實現(xiàn)代碼可以得出，方法一中循環(huán)執(zhí)行的次數(shù)為(n/22)*30+a[n%22]，其中，a[n%22]的取值范圍為2～30，因此，方法一的時間復(fù)雜度為O(n)。[考點]如何求有序數(shù)列的第1500個數(shù)的值

4.

題目描述：

如何把十進制數(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型)分別以二進制和十六進制形式輸出

5.

題目描述：

給定一個整數(shù)，輸出這個整數(shù)的二進制表示中1的個數(shù)。例如：給定整數(shù)7，其二進制表示為111，因此，輸出結(jié)果為3。正確答案：方法一：移位法

可以采用位操作來完成。具體思路如下：首先，判斷這個數(shù)的最后一位是否為1，如果為1，則計數(shù)器加1，然后，通過右移丟棄掉最后一位，循環(huán)執(zhí)行該操作直到這個數(shù)等于0為止。在判斷二進制表示的最后一位是否為1時，可以采用與運算來達到這個目的。具體實現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

//判斷二進制碼中1的個數(shù)

funccountOne1(nint)int{

count:=0//用來計數(shù)

forn＞0{

if(n&1)==1{//判斷最后一位是否為1

count++

}

n＞＞=1//移位丟掉最后一位

}

returncount

}

funcmain(){

fmt.Println("方法一")

fmt.Println(CountOne1(7))

fmt.Println(countOne1(8))

}

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

3

1

算法性能分析：

這種方法的時間復(fù)雜度為O(n)，其中，n代表二進制數(shù)的位數(shù)。

方法二：與操作法

給定一個數(shù)n，每進行一次n&(n-1)計算，其結(jié)果中都會少了一位1，而且是最后一位。例如，n=6，其對應(yīng)的二進制表示為110，n-1=5，對應(yīng)的二進制表示為101，n&(n-1)運算后的二進制表示為100，其效果就是去掉了110