Go程序員面試分類(lèi)模擬題18

Go程序員面試分類(lèi)模擬題18論述題1.

題目描述：

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

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

方法二：因子法

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

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

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

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

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

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

packagemain

import(

"fmt"

)

funczeroCount(nint)int{

count:=0

forn＞0{

n=n/5

count+=n

}

returncount

}

funcmain(){

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

}

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

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

算法性能分析：

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

2.

題目描述：

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

根據(jù)絕對(duì)值的性質(zhì)可知，如果|a-b|==a-b，那么max(a，b)=a，否則max(a，b)=b，根據(jù)這個(gè)思路實(shí)現(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("絕對(duì)值法")

fmt.Println(max1(5,6))

}

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

6

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

方法二：二進(jìn)制法

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

funcmax2(a,bint)int{

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

returnb

}else{

returna

}

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

3.

題目描述：

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

最簡(jiǎn)單的方法就是用一個(gè)計(jì)數(shù)器來(lái)記錄滿(mǎn)足條件的整數(shù)的個(gè)數(shù)，然后從1開(kāi)始遍歷整數(shù)，如果當(dāng)前遍歷的數(shù)能被2或者3或者5整除，則計(jì)數(shù)器的值加1，當(dāng)計(jì)數(shù)器的值為1500時(shí)，當(dāng)前遍歷到的值就是所要求的值。根據(jù)這個(gè)思路實(shí)現(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))

}

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

2045

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

首先可以很容易得到2，3和5的最小公倍數(shù)為30，此外，1～30這個(gè)區(qū)間內(nèi)滿(mǎn)足條件的數(shù)有22個(gè){2，3，4，5，6，8，9，10，12，14，15，16，18，20，21，22，24，25，26，27，28，30}，由于最小公倍數(shù)為30，我們可以猜想，滿(mǎn)足條件的數(shù)字是否具有周期性(周期為30)呢?通過(guò)計(jì)算可以發(fā)現(xiàn)，31～60這個(gè)區(qū)間內(nèi)滿(mǎn)足條件的數(shù)也恰好有22個(gè){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)這些滿(mǎn)足條件的數(shù)具有周期性(周期為30)。由于1500/22=68，1500%68=4，從而可以得出第1500個(gè)數(shù)經(jīng)過(guò)了68個(gè)周期，然后在第69個(gè)周期中取第四個(gè)滿(mǎn)足條件的數(shù){2，3，4，5}。從而可以得出第1500個(gè)數(shù)為68*30+5=2045。根據(jù)這個(gè)思路實(shí)現(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]

}

算法性能分析：

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

4.

題目描述：

如何把十進(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ì)算出每一位的值。為了方便起見(jiàn)，下面以byte類(lèi)型的數(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)制的方法?？梢允褂妙?lèi)似于十進(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)制形式輸出

5.

題目描述：

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

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

packagemain

import(

"fmt"

)

//判斷二進(jìn)制碼中1的個(gè)數(shù)

funccountOne1(nint)int{

count:=0//用來(lái)計(jì)數(shù)

forn＞0{

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

count++

}

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

}

returncount

}

funcmain(){

fmt.Println("方法一")

fmt.Println(CountOne1(7))

fmt.Println(countOne1(8))

}

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

3

1

算法性能分析：

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

方法二：與操作法

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