Python程序員面試分類真題18

Python程序員面試分類真題18(總分：100.00，做題時(shí)間：90分鐘)面試題(總題數(shù)：5，分?jǐn)?shù)：100.00)1.

給定任意一個(gè)正整數(shù)，求比這個(gè)數(shù)大且最小的“不重復(fù)數(shù)”，“不重復(fù)數(shù)”的含義是相鄰兩位不相同，例如1101是重復(fù)數(shù)，而1201是不重復(fù)數(shù)。

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(方法一：蠻力法

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

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

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

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

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

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

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

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

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

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

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

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

"""

方法功能:處理數(shù)字相加的進(jìn)位

輸入?yún)?shù):num為字符數(shù)組,pos為進(jìn)行加1操作對(duì)應(yīng)的下標(biāo)位置

"""

defcarry(num,pos):

whilepos＞0:

ifint(num[pos])＞9:

num[pos]='0'

num[pos-1]=str(int(num[pos-1])+1)

pos-=1

"""

方法功能:獲取大于n的最小不重復(fù)數(shù)

輸入?yún)?shù):n為正整數(shù)

返回值:大于n的最小不重復(fù)數(shù)

"""

deffindMinNonDupNum(n):

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

nChar=list(str(n+1))

ch=[None]*(len(nChar)+2)

ch[0]='0'

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

i=0

whilei＜len(nChar):

ch[i+1]=nChar[i]

i+=1

lens=len(ch)

i=lens-2#從右向左遍歷

whilei＞0:

count+=1

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

ch[i]=str(int(ch[i])+1)#末尾數(shù)字加1

carry(ch,i)#處理進(jìn)位

#把下標(biāo)為i后面的字符串變?yōu)?101…串

j=i+1

whilej＜lens:

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

ch[j]=0'

else:

ch[j]='1'

j+=1

#第i位加1后,可能會(huì)與第i+1位相等

i+=1

else:

i-=1

print"循環(huán)次數(shù)為:"+str(count)

returnint(".join(ch))

if__name__=="__main__":

printfindMinNonDupNum(23345)

printfindMinNonDupNum(1101010)

printfindMinNonDupNum(99010)

printfindMinNonDupNum(8989)

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

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

23401

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

1201010

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

101010

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

9010

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

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

"""

方法功能:處理數(shù)字相加的進(jìn)位

輸入?yún)?shù):num為字符數(shù)組,pos為進(jìn)行加1操作對(duì)應(yīng)的下標(biāo)位置

"""

defcarry(num,pos):

whilepos＞0:

ifint(num[pos])＞9:

num[pos]='0'

num[pos-1]=str(int(num[pos-1])+1)

pos-=1

"""

方法功能:獲取大于n的最小不重復(fù)數(shù)

輸入?yún)?shù):n為正整數(shù)

返回值:大于n的最小不重復(fù)數(shù)

"""

deffindMinNonDupNum(n):

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

nChar=list(str(n+1))

ch=[None]*(len(nChar)+1)

ch[0]='0'

i=0

whilei＜len(nChar):

ch[i+1]=nChar[i]

i+=1

lens=len(ch)

i=2#從左向右遍歷

whilei＜lens:

count+=1

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

ch[i]=str(int(ch[i])+1)#末尾數(shù)字加1

carry(ch,i)#處理進(jìn)位

#把下標(biāo)為i后面的字符串變?yōu)?101...串

j=i+1

whilej＜lens:

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

ch[j]='0'

else:

ch[j]='1'

j+=1

else:

i+=1

print"循環(huán)次數(shù)為:"+str(count)

returnint(".join(ch))

if__name__=="__main__":

printfindMinNonDupNum(23345)

printfindMinNonDupNum(1101010)

printfindMinNonDupNum(99010)

printfindMinNonDupNum(8989)

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

給定一個(gè)數(shù)d和n，如何計(jì)算d的n次方?例如：d=2，n=3，d的n次方為23=8。

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(方法一：蠻力法

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

(1)n=0，那么計(jì)算結(jié)果肯定為1；

(2)n=1，計(jì)算結(jié)果肯定為d；

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

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

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

"""

方法功能:計(jì)算一個(gè)數(shù)的n次方

輸入?yún)?shù):d為底數(shù),n為冪

返回值:d^n

"""

defpower(d,n):

ifn==0:return1

ifn==1:returnd

result=1.0

ifn＞0:

i=1

whilei＜=n:

result*=d

i+=1

returnresult

else:

i=1

whilei＜=abs(n):

resultresult/d

i+=1

returnresult

if__name__=="__main__":

printpower(2,3)

printpower(-2,3)

printpower(2,-3)

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

8

-8

0.125

算法性能分析：

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

方法二：遞歸法

由于方法一沒有充分利用中間的計(jì)算結(jié)果，因此，算法效率還有很大的提升余地。例如在計(jì)算2的100次方的時(shí)候，假如已經(jīng)計(jì)算出了2的50次方的值tmp=250，就沒必要對(duì)tmp再乘以50次2，可以直接利用tmp*tmp就得到了2100的值。可以利用這個(gè)特點(diǎn)給出遞歸實(shí)現(xiàn)方法如下：

(1)n=0，那么計(jì)算結(jié)果肯定為1；

(2)n=1，計(jì)算結(jié)果肯定為d；

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

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

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

defpower(d,n):

ifn==0:return1

ifn==1:returnd

tmp=power(d,abs(n)/2)+0.0

#printtmp

ifn＞0:

ifn%2==1:#n為奇數(shù)

returntmp*tmp*d

else:#n為偶數(shù)

returntmp*tmp

else:

ifn%2==1:

print1/(tmp*tmp*d)

return1/(tmp*tmp*d)

else:

return1/(tmp*tmp)

算法性能分析：

這種方法的時(shí)間復(fù)雜度為O(logn)。)解析：[考點(diǎn)]如何計(jì)算一個(gè)數(shù)的n次方3.

給定一個(gè)數(shù)n，求出它的平方根，比如16的平方根為4。要求不能使用庫(kù)函數(shù)。

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(正數(shù)n的平方根可以通過計(jì)算一系列近似值來獲得，每個(gè)近似值都比前一個(gè)更加接近準(zhǔn)確值，直到找出滿足精度要求的那個(gè)數(shù)位置。具體而言，可以找出第一個(gè)近似值是1，接下來的近似值則可以通過下面的公式來獲得：ai+1=(ai+n/ai)/2。實(shí)現(xiàn)代碼如下：

#獲取n的平方根,e為精度要求

defsquareRoot(n,e):

new_one=n

last_one=1.0#第一個(gè)近似值為1

whilenew_one-last_one＞e:#直到滿足精度要求為止

new_one=(new_one+last_one)/2#求下一個(gè)近似值

last_one=n/new_one

returnnew_one

if__name__=="__main__":

n=50

e=0.000001

printstr(n)+"的平方根為"+str(squareRoot(n,e))

n=4

printstr(n)+"的平方根為"+str(squareRoot(n,e))

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

50的平方根為7.071068

4的平方根為2.000000)解析：[考點(diǎn)]如何在不能使用庫(kù)函數(shù)的條件下計(jì)算n的平方根4.

不使用^操作實(shí)現(xiàn)異或運(yùn)算。

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

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

classMyXOR:

def__init__(self):

self.BITS=32

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

defxor(self,x,y):

res=0

i=self.BITS-1

whilei＞=0:

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

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

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

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

if(b1==b2):

xoredBit=0

else:

xoredBit=1

res＜＜=1

res|=xoredBit

i-=1

returnres

if__name__=="__main__":