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

題目描述：

給定任意一個正整數(shù)，求比這個數(shù)大且最小的“不重復數(shù)”，“不重復數(shù)”的含義是相鄰兩位不相同，例如1101是重復數(shù)，而1201是不重復數(shù)。參考（江南博哥）答案：方法一：蠻力法

最容易想到的方法就是對這個給定的數(shù)加1，然后判斷這個數(shù)是不是“不重復數(shù)”，如果不是，則繼續(xù)加1，直到找到“不重復數(shù)”為止。顯然這種方法的效率非常低下。

方法二：從右到左的貪心法

例如給定數(shù)字11099，首先對這個數(shù)字加1，變?yōu)?1000，接著從右向左找出第一對重復的數(shù)字00，對這個數(shù)字加1，變?yōu)?1001，繼續(xù)從右向左找出下一對重復的數(shù)00，將其加1，同時把這一位往后的數(shù)字變?yōu)?101…串(當某個數(shù)字自增后，只有把后面的數(shù)字變成0101…，才是最小的不重復數(shù)字)，這個數(shù)字變?yōu)?1010，接著采用同樣的方法，11010-＞12010就可以得到滿足條件的數(shù)。

需要特別注意的是當對第i個數(shù)進行加1操作后可能會導致第i個數(shù)與第i+1個數(shù)相等，因此，需要處理這種特殊情況，下圖以99020為例介紹處理方法。

(1)把數(shù)字加1并轉換為字符串。

(2)從右到左找到第一組重復的數(shù)99(數(shù)組下標為i=2)，然后把99加1，變?yōu)?00，然后把后面的字符變?yōu)?101…串，得到100010。

(3)由于執(zhí)行(2)后對下標為2的值進行了修改，導致它與下標為i=3的值相同，因此，需要對i自增變?yōu)閕=3，接著從i=3開始從右向左找出下一組重復的數(shù)字00，對00加1變?yōu)?1，后面的字符變?yōu)?101…串，得到100101。

(4)由于下標為i=3與i+1=4的值不同，因此，可以從i-1=2的位置開始從右向左找出下一組重復的數(shù)字00，對其加1就可以得到滿足條件的最小的“不重復數(shù)”。

根據(jù)這個思路給出實現(xiàn)方法如下：

1)對給定的數(shù)加1。

2)循環(huán)執(zhí)行如下操作：對給定的數(shù)從右向左找出第一對重復的數(shù)(下標為i)，對這個數(shù)字加1，然后把這個數(shù)字后面的數(shù)變?yōu)?101…得到新的數(shù)。如果操作結束后下標為i的值等于下標為i+1的值，則對i進行自增，否則對i進行白減；然后從下標為i開始從右向左重復執(zhí)行步驟2)，直到這個數(shù)是“不重復數(shù)”為止。

實現(xiàn)代碼如下：

packagemain

import(

"strcony"

"fmt"

)

//處理數(shù)字相加的進位

funccarry(num[]rune,posint){

for;pos＞0;pos--{

ifnum[pos]＞'9'{

num[pos]='0'

num[pos-1]++

}

}

}

//獲取大于n的最小不重復數(shù)

funcfindMinNonDupNum1(nint)int{

count:=0//用來記錄循環(huán)次數(shù)

mRune:=[]rune(strconv.Itoa(n+1))

ch:=make([]rune,len(mRune)+2)

ch[0]='0'

ch[len(ch)-1]='0'

fori:=0;i＜len(mRune);i++{

ch[i+1]=mRune[i]

}

ll:=len(ch)

i:=ll-2//從右向左遍歷

fori＞0{

count++

ifch[i-1]==ch[i]{

ch[i]++//末尾數(shù)字加1

carry(ch,i)//處理進位

//把下標為i后面的字符串變?yōu)?101…串

forj:=i+1;j＜ll;j++{

if(j-i)%2==1{

ch[j]='0'

}else{

ch[j]='1'

}

}

//第i位加1全，可能會與第i+1位相等，i++用來處理這種情況

i++

}else{

i--

}

}

fmt.Println("循環(huán)次數(shù)為:",count)

result,_:=strconv.Atoi(string(ch))

returnresult

}

funcmain(){

fmt.Println("從右到左的貪心法")

fmt.Println(findMinNonDupNum1(23345))

fmt.Println(findMinNonDupNum1(1101010))

fmt.Println(findMinNonDupNum1(99010))

fmt.Println(findMinNonDupNum1(8989))

}

程序的運行結果為

循環(huán)次數(shù)為：7

23401

循環(huán)次數(shù)為：11

1201010

循環(huán)次數(shù)為：13

101010

循環(huán)次數(shù)為：10

9010

方法三：從左到右的貪心法

與方法二類似，只不過是從左到右開始遍歷，如果碰到重復的數(shù)字，則把其加1，后面的數(shù)字變成0101…串。實現(xiàn)代碼如下：

packagemain

import(

"strconv"

"fmt"

)

//處理數(shù)字相加的進位

funccarry(hum[]rune,posint){

for;pos＞0;pos--{

ifnum[pos]＞'9'{

num[pos]='0'

num[pos-1]++

}

}

}

funcfindMinNonDupNum2(nint)int{

count:=0//用來記錄循環(huán)次數(shù)

mRune:=[]rune(strconv.Itoa(n+1))

ch:=make([]rune,len(mRune)+2)

ch[0]='0'

ch[len(ch)-1]='0'

fori:=0;i＜len(mRune);i++{

ch[i+l]=mRune[i]

}

ll:=len(ch)

i:=2//從左向右遍歷

fori＜ll{

count++

ifch[i-1]==ch[i]{

ch[i]++//末尾數(shù)字加1

carry(ch,i)//處理進位

//把下標為i后面的字符串變?yōu)?101…串

forj:=i+1;j＜ll;j++{

if(j-i)%2==1{

ch[j]='0'

}else{

ch[j]='1'

}

}

}else{

i++

}

}

fmt.Println("循環(huán)次數(shù)為:",count)

result,_:=strconv.Atoi(string(ch))

returnresult

}

funcmain(){

fmt.Println("從左到右的貪心法")

fmt.Println(findMinNonDupNum2(23345))

fmt.Println(findMinNonDupNum2(1101010))

fmt.Println(findMinNonDupNum2(99010))

fmt.Println(findMinNonDupNum2(8989))

}

顯然，方法三循環(huán)的次數(shù)少于方法二，因此，方法三的性能要優(yōu)于方法二。[考點]如何找最小的不重復數(shù)

2.

題目描述：

給定一個數(shù)d和n，如何計算d的n次方?例如：d=2，n=3，d的n次方為2^3=8。正確答案：方法一：蠻力法

可以把n的取值分為如下幾種情況：

(1)n=0，那么計算結果肯定為1。

(2)n=1，計算結果肯定為d。

(3)n＞0，計算方法為：初始化計算結果result=1，然后對result執(zhí)行n次乘以d的操作，得到的結果就是d的n次方。

(4)n＜0，計算方法為：初始化計算結果result=1，然后對result執(zhí)行|n|次除以d的操作，得到的結果就是d的n次方。

以2的三次方為例，首先初始化result=1，接著對result執(zhí)行三次乘以2的操作：result=result*2=1*2=2，result=result*2=2*2=4，result=result*2=4*2=8，因此，2的三次方等于8。根據(jù)這個思路給出實現(xiàn)代碼如下：

packagemain

import(

"fmt"

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

)

fimcpower1(dfloat64,nint)float64{

if(n==0){return1}

if(n==1){returnd}

result:=1.0

ifn＞0{

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

result*=d

)

returnresult

}else{

fori:=1;i＜=Abs(n);i++{

result=result/d

}

}

returnresult

}

funcmain(){

fmt.Println("方法一")

fmt.Println(power1(2,3))

fmt.Println(power1(-2,3))

fmt.Println(power1(2,-3))

}

程序的運行結果為

8

-8

0.125

算法性能分析：

這種方法的時間復雜度為O(n)，需要注意的是，當n非常大的時候，這種方法的效率是非常低下的。

方法二：遞歸法

由于方法一沒有充分利用中間的計算結果，因此，算法效率還有很大的提升的余地。例如在計算2的100次方的時候，假如已經(jīng)計算出了2的50次方的值tmp=2^50，就沒必要對tmp再乘以50次2，可以直接利用tmp*tmp就得到了2^100的值?？梢岳眠@個特點給出遞歸實現(xiàn)方法如下：

(1)n=0，那么計算結果肯定為1。

(2)n=1，計算結果肯定為d。

(3)n＞0，首先計算2^(n/2)的值tmp，如果n為奇數(shù)，那么計算結果result=tmp*tmp*d，如果n為偶數(shù)，那么計算結果result=tmp*tmp。

(4)n＜0，首先計算2^(|n/2|)的值tmp，如果n為奇數(shù)，那么計算結果result=1/(tmp*tmp*d)，如果n為偶數(shù)，那么計算結果result=1/(tmp*tmp)。

根據(jù)以上思路實現(xiàn)代碼如下：

funcpower2(dfloat64,nint)float64{

if(n==0){return1}

if(n==1){returnd}

tmp:=power2(d,Abs(n/2))

ifn＞0{

if(n%2==1){//n為奇數(shù)

returntmp*tmp*d

}else{//n為偶數(shù)

returntmp*tmp

}

}else{

if(n%2==1){

return1/(tmp*tmp*d)

}else{

return1/(tmp*tmp)

}

}

}

算法性能分析：

這種方法的時間復雜度為O(logn)。[考點]如何計算一個數(shù)的n次方

3.

題目描述：

給定一個數(shù)n，求出它的平方根，比如16的算術平方根為4。要求不能使用庫函數(shù)。正確答案：正數(shù)n的平方根可以通過計算一系列近似值來獲得，每個近似值都比前一個更加接近準確值，直到找出滿足精度要求的那個數(shù)位置。具體而言，可以找出第一個近似值是1，接下來的近似值則可以通過下面的公式來獲得：ai+1=(ai+n/ai)/2。實現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

//獲取n的平方根，e為精度要求

funcsquareRoot(n,efloat64)float64{

newOne:=n

lastOne:=1.0//第一個近似值為1

fornewOne-lastOne＞e{//直到滿足精度要求為止

newOne=(newOne+lastOne)/2//求下一個近似值

lastOne=n/newOne

}

returnnewOne

}

funcmain(){

n:=50.0

e:=0.00000l

fmt.Printf("%f的平方根為%f",n,squareRoot(n,e))

fmt.Println()

n=4.0

fmt.Pfintf("%f的平方根為%f",squareRoot(n,e))

fmt.Println()

}

程序的運行結果為

50的平方根為7.071068

4的平方根為2.000000[考點]如何在不能使用庫函數(shù)的條件下計算n的算術平方根

4.

題目描述：

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

packagemain

import(

"strconv"

"fmt"

)

//獲取x與y異或的結果

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的時候結果為0*/

if(b1=b2){

xoredBit=0

}else{

xoredBit=1

}

res＜＜=1

res|=xoredBit

}

returnres

}

funcmain(){

fmt.Println("方