Python程序员面试分类真题18

Python程序员面试分类真题18

（总分：100.00,做题时间：90分钟）

面试题（总题数：5,分数：1C0.00）

1.给定任意一个正整数，求比这个数大且最小的“不重身数”，“不重更数”的含义是相邻两位不相

同，例如1101是重发数，而1201是不重灾数。

（分数:20,00）

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

最容易想到的方法就是对这个给定的数加1,然后判断这个数是不是“不重复数”，如果不是，那

么继续加1,直到找到“不重复数”为止。显然这种方法的效率非常低相

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

例如给定数字11099,首先对这个数字加【，变为11000,接着从右向左找出第•对重复的数字00,

对这个数字加1,变为11001,继续从右向左找出下一对重宴的数00,将其加1,同时把这一位往后的数

字变为0101…串（当某个数字自增后，只有把后面的数字变成0101…，才是最小的不重复数字），这个数

字变为11010,接着采用同样的方法，11010->12010就可以得到满足条件的数。

需要特别注意的是“1对第i个数进行加1操作后可能会导致第i个数与第i+1个数相等，因此，需

要处理这种特殊情况，下图以99020为例介绍处理方法。

（1）把数字加1并转换为字符串。

（2）从右到左找到第•组重复的数99（数组下标为i=2）,然后把99加I,变为100,然后把后面的字

符变为0101…串。得到100010。

（3）由于执行步骤（2）后对下标为2的值进行了修改，导致它与下标为i=3的值相同，因此，需要对

i自增变为i=3,接着从i=3开始从右向左找出下一组重更的数字00,对00加1变为01,后面的字符变

为0101…串,得到100101。

（力由于下标为i=3与i+l=4的值不同，因此，可以从i-l=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[posJ)>9:

num[pos]=,0'

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

pos-=]

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

输入参数：n为正整数

返回值：大于n的最小不重且数

〃“"

deffindMinNonDupNum(n):

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

nChar=list(str(n+l))

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

ch[0]='O'

ch[len(ch)-l]=，O'

i=0

whilei<len(nChar):

ch[i+l]=nChar[iJ

i+=l

lens=len(ch)

i=lens-2#从右向左遍历

whilei>0:

count+=l

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

ch[i]=str(int(ch[i])+l)#末尾数字加1

carry(ch.i)#处理进位

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

j=i+l

whilej<lens:

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

ch[j]=0'

else:

ch[j]=r

J+=l

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

i+=l

else:

i-=l

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

returnint(w.join(ch))

ifnamemain”:

printfindMinNonDupNum(23345)

printfindMinNonDupNum(1131010)

printfindMinNonDupNum(99310)

printfindMinNonDupNum(8939)

程序的运行结果为：

循环次数为：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-l]=str(int(r)um[pos-l])+l)

pos-=l

方法功能：获取大于n的最小不重第数

输入参数：n为正整数

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

deffindMinNonDupNum(n):

counts#用来记录循环次数

nChar=lisl(str(n+l))

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

ch[0]='O'

i=0

whilei<len(nChar):

ch[i+l]=nChar[i]

i+=l

lens=len(ch)

i=2#从左向右遍历

whilei<lens:

count+=l

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

ch[i]=str(int(ch[i])+l)#末尾数字加1

carry(ch,i)#处理进位

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

j=i+l

whilej<lens:

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

ch[j]=>0f

else:

ch[j]=-r

j+=l

else:

i+=l

print”循环次数为："+slr(count)

returninijoin(ch))

if_name_—*_main_*:

printfindMinNonDupNum(23345)

printfindMinNonDupNum(1131010)

printfindMinNonDupNum(99310)

printfindMinNonDupNum(8939)

显然，方法三循环的次数少于方法二，因此，方法三的性能要优于方法二。)

解析：［考点］如何找最小的不重熨数

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

(分数：20.00)

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

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

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

(2)n=l,计算结果肯定为d：

(3)n>0,计算方法为：初始化计算结果results,然后对result执行n次乘以d的操作,得到的

结果就是d的n次方；

(4)n<0,计算方法为：初始化计算结果results,然后对rcsult执行|n|次除以d的操作，得到

的结果就是d的n次方：

以2的3次方为例，首先初妗化results,接着对result执行三次乘以2的操作：

resu1t=resu11*2=1*2=2,resu1t=resu11*2=2*2=4»resu1t=resu11*2=4*2=8,因此，2的3次方等于8。

根据这个思路给出实现代码如下：

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

输入参数：d为底数，n为岳

返回值：d'n

“R2

defpower(d,n):

ifn==0:return1

ifn=l:returnd

result=l.0

ifn>0:

i=l

whilei<=n:

result*=d

i+=l

returnresult

else:

i=l

whi1ci<=abs(n):

resultresult/d

i+=l

returnresult

if_name_="_main

printpower(2,3)

printpower(-2,3)

printpower(2,-3)

程序的运行结果为:

8

-8

0.125

算法性能分析：

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

的。

方法二：递归法

由于方法一没有充分利用中间的计算结果，因此，算法效率还有很大的提升余地。例如在计算2的

100次方的时候，假如己经计算出了2的50次方的值imp=2力就没必要对imp再乘以50次2,可以宜接

利用tmp*tmp就得到了2H1'的值。可以利用这个特点给出递归实现方法如下：

(l)n=0,那么计算结果肯定为1：

(2)n=b计算结果肯定为d：

(3)n>0,首先计算2"的值：叩，如果n为奇数,那么计算结果result=tmp*tmp*d,如果n为偶

数，那么计算结果result=tmp*tmp；

(4)n<0,首先计算2"的值imp,如果n为奇数，那么计算结果result=l/(tmp*tmp*d),如果n为

偶数,那么计算结果result=l/(tnp*tfnp)o

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

defpower(d,n):

ifn=0:return1

ifn—1:returnd

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

Sprinttmp

ifn>0:

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

returntmp*tmp*d

else:为偶数

returnImp*tmp

else:

ifn%2==l:

printl/(tmp*tmp*d)

returnl/(tmp*tinp*d)

else:

returnl/(tmp*tmp)

算法性能分析：

这种方法的时间复杂度为O(logn)。)

解析：［考点］如何计算一个数的n次方

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

(分数:20.00)

正确答案：(正数n的平方根可以通过计算一系列近似值来获得，每个近似值都比前一个更加接近准确

值，直到找出满足精度要求的那个数位置。具体而言，可以找出第一个近似他是1，接下来的近似值则可

以通过卜面的公式来获得:/2。实现代蚂如卜：

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

defsquareRoot(n,e):

new_one=n

last_one=l.0#第一个近似值为1

whilenew_one-lastone>e:#直到满足精度要求为止

newone=(newone+lastone)求下一个近似伯.

last_one=n/new_one

returnnew_one

if_name_—*_main_":

n=50

e=0.000001

printslr(n)「的平方根为“+slr(squareRool(n,e))

n=4

printstr(n)+”的平方根为“+str(squareRoot(n,e))

程序的运行结果为：

50的平方根为7.071068

4的平方根为2.000000)

解析：［考点］如何在不能使用库函数的条件下计算n的平方根

4.不使用一操作实现异或运算。

(分数:20.00)

正确答案：(最简单的方法是遍历两个整数的所有"的位，如果两个数的某一位相等，那么结果中这•位的

值为0,否则结果中这一位的值为1,实现代码如下：

classMyXOR:

definit(self):

self.BITS=32

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

defxor(self,x,y):

res=0

i=self.B!TS-l

whilei>=0:

力获取x与y当前的bil值

bl=(x&(l<<i))>0

b2=(y&(l<<i))>0

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

if(bl==b2):

xoredBit=0

else:

xoredBit=l

res<<=l

resl=xoredBit

i-=l

returnres

if_name_=*_main*:

x=3

y=5

mx=MyX0R()

print