Python程序员面试分类真题18

Python程序员面试分类真题18(总分：100.00，做题时间：90分钟)面试题(总题数：5，分数：100.00)1.

给定任意一个正整数，求比这个数大且最小的“不重复数”，“不重复数”的含义是相邻两位不相同，例如1101是重复数，而1201是不重复数。

（分数：20.00）__________________________________________________________________________________________

正确答案：(方法一：蛮力法

最容易想到的方法就是对这个给定的数加1，然后判断这个数是不是“不重复数”，如果不是，那么继续加1，直到找到“不重复数”为止。显然这种方法的效率非常低下。

方法二：从右到左的贪心法

例如给定数字11099，首先对这个数字加1，变为11000，接着从右向左找出第一对重复的数字00，对这个数字加1，变为11001，继续从右向左找出下一对重复的数00，将其加1，同时把这一位往后的数字变为0101…串(当某个数字自增后，只有把后面的数字变成0101…，才是最小的不重复数字)，这个数字变为11010，接着采用同样的方法，11010-＞12010就可以得到满足条件的数。

需要特别注意的是当对第i个数进行加1操作后可能会导致第i个数与第i+1个数相等，因此，需要处理这种特殊情况，下图以99020为例介绍处理方法。

(1)把数字加1并转换为字符串。

(2)从右到左找到第一组重复的数99(数组下标为i=2)，然后把99加1，变为100，然后把后面的字符变为0101…串。得到100010。

(3)由于执行步骤(2)后对下标为2的值进行了修改，导致它与下标为i=3的值相同，因此，需要对i自增变为i=3，接着从i=3开始从右向左找出下一组重复的数字00，对00加1变为01，后面的字符变为0101…串，得到100101。

(4)由于下标为i=3与i+1=4的值不同，因此，可以从i-1=2的位置开始从右向左找出下一组重复的数字00，对其加1就可以得到满足条件的最小的“不重复数”。

根据这个思路给出实现方法如下：

1)对给定的数加1。

2)循环执行如下操作：对给定的数从右向左找出第一对重复的数(下标为i)，对这个数字加1，然后把这个数字后面的数变为0101…得到新的数。如果操作结束后下标为i的值等于下标为i+1的值，那么对i进行自增，否则对i进行自减；然后从下标为i开始从右向左重复执行步骤2)，直到这个数是“不重复数”为止。

实现代码如下：

"""

方法功能:处理数字相加的进位

输入参数:num为字符数组,pos为进行加1操作对应的下标位置

"""

defcarry(num,pos):

whilepos＞0:

ifint(num[pos])＞9:

num[pos]='0'

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

pos-=1

"""

方法功能:获取大于n的最小不重复数

输入参数:n为正整数

返回值:大于n的最小不重复数

"""

deffindMinNonDupNum(n):

count=0#用来记录循环次数

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)#末尾数字加1

carry(ch,i)#处理进位

#把下标为i后面的字符串变为0101…串

j=i+1

whilej＜lens:

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

ch[j]=0'

else:

ch[j]='1'

j+=1

#第i位加1后,可能会与第i+1位相等

i+=1

else:

i-=1

print"循环次数为:"+str(count)

returnint(".join(ch))

if__name__=="__main__":

printfindMinNonDupNum(23345)

printfindMinNonDupNum(1101010)

printfindMinNonDupNum(99010)

printfindMinNonDupNum(8989)

程序的运行结果为：

循环次数为：7

23401

循环次数为：11

1201010

循环次数为：13

101010

循环次数为：10

9010

方法三：从左到右的贪心法

与方法二类似，只不过是从左到右开始遍历，如果碰到重复的数字，那么把其加1，后面的数字变成0101…串。实现代码如下：

"""

方法功能:处理数字相加的进位

输入参数:num为字符数组,pos为进行加1操作对应的下标位置

"""

defcarry(num,pos):

whilepos＞0:

ifint(num[pos])＞9:

num[pos]='0'

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

pos-=1

"""

方法功能:获取大于n的最小不重复数

输入参数:n为正整数

返回值:大于n的最小不重复数

"""

deffindMinNonDupNum(n):

count=0#用来记录循环次数

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)#末尾数字加1

carry(ch,i)#处理进位

#把下标为i后面的字符串变为0101...串

j=i+1

whilej＜lens:

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

ch[j]='0'

else:

ch[j]='1'

j+=1

else:

i+=1

print"循环次数为:"+str(count)

returnint(".join(ch))

if__name__=="__main__":

printfindMinNonDupNum(23345)

printfindMinNonDupNum(1101010)

printfindMinNonDupNum(99010)

printfindMinNonDupNum(8989)

显然，方法三循环的次数少于方法二，因此，方法三的性能要优于方法二。)解析：[考点]如何找最小的不重复数2.

给定一个数d和n，如何计算d的n次方?例如：d=2，n=3，d的n次方为23=8。

（分数：20.00）__________________________________________________________________________________________

正确答案：(方法一：蛮力法

可以把n的取值分为如下几种情况：

(1)n=0，那么计算结果肯定为1；

(2)n=1，计算结果肯定为d；

(3)n＞0，计算方法为：初始化计算结果result=1，然后对result执行n次乘以d的操作，得到的结果就是d的n次方；

(4)n＜0，计算方法为：初始化计算结果result=1，然后对result执行|n|次除以d的操作，得到的结果就是d的n次方；

以2的3次方为例，首先初始化result=1，接着对result执行三次乘以2的操作：result=result*2=1*2=2，result=result*2=2*2=4，result=result*2=4*2=8，因此，2的3次方等于8。根据这个思路给出实现代码如下：

"""

方法功能:计算一个数的n次方

输入参数:d为底数,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)

程序的运行结果为：

8

-8

0.125

算法性能分析：

这种方法的时间复杂度为O(n)，需要注意的是，当n非常大的时候，这种方法的效率是非常低下的。

方法二：递归法

由于方法一没有充分利用中间的计算结果，因此，算法效率还有很大的提升余地。例如在计算2的100次方的时候，假如已经计算出了2的50次方的值tmp=250，就没必要对tmp再乘以50次2，可以直接利用tmp*tmp就得到了2100的值。可以利用这个特点给出递归实现方法如下：

(1)n=0，那么计算结果肯定为1；

(2)n=1，计算结果肯定为d；

(3)n＞0，首先计算2n/2的值tmp，如果n为奇数，那么计算结果result=tmp*tmp*d，如果n为偶数，那么计算结果result=tmp*tmp；

(4)n＜0，首先计算2|n/2|的值tmp，如果n为奇数，那么计算结果result=1/(tmp*tmp*d)，如果n为偶数，那么计算结果result=1/(tmp*tmp)。

根据以上思路实现代码如下：

defpower(d,n):

ifn==0:return1

ifn==1:returnd

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

#printtmp

ifn＞0:

ifn%2==1:#n为奇数

returntmp*tmp*d

else:#n为偶数

returntmp*tmp

else:

ifn%2==1:

print1/(tmp*tmp*d)

return1/(tmp*tmp*d)

else:

return1/(tmp*tmp)

算法性能分析：

这种方法的时间复杂度为O(logn)。)解析：[考点]如何计算一个数的n次方3.

给定一个数n，求出它的平方根，比如16的平方根为4。要求不能使用库函数。

（分数：20.00）__________________________________________________________________________________________

正确答案：(正数n的平方根可以通过计算一系列近似值来获得，每个近似值都比前一个更加接近准确值，直到找出满足精度要求的那个数位置。具体而言，可以找出第一个近似值是1，接下来的近似值则可以通过下面的公式来获得：ai+1=(ai+n/ai)/2。实现代码如下：

#获取n的平方根,e为精度要求

defsquareRoot(n,e):

new_one=n

last_one=1.0#第一个近似值为1

whilenew_one-last_one＞e:#直到满足精度要求为止

new_one=(new_one+last_one)/2#求下一个近似值

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))

程序的运行结果为：

50的平方根为7.071068

4的平方根为2.000000)解析：[考点]如何在不能使用库函数的条件下计算n的平方根4.

不使用^操作实现异或运算。

（分数：20.00）__________________________________________________________________________________________

正确答案：(最简单的方法是遍历两个整数的所有的位，如果两个数的某一位相等，那么结果中这一位的值为0，否则结果中这一位的值为1，实现代码如下：

classMyXOR:

def__init__(self):

self.BITS=32

#获取x与y的异或的结果

defxor(self,x,y):

res=0

i=self.BITS-1

whilei＞=0:

#获取x与y当前的bit值

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

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

#只有这两位都是1或0的时候结果为0

if(b1==b2):

xoredBit=0

else:

xoredBit=1

res＜＜=1

res|=xoredBit

i-=1

returnres

if__name__=="__main__":