Python程序员面试分类真题15

Python程序员面试分类真题15

1.编辑距离又称Levenshtein距离，是指两个字符串之间由一个转成另一个

所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字

符、插入一个字符、删除一个(江南博哥)字符。请设计并实现一个算法来计

算两个字符串的编辑距离，并计算其复杂度。在某些应用场景下，替换操作的

代价比较高，假设替换操作的代价是插入和删除的两倍，算法该如何调整？

正确答案：

本题可以使用动态规划的方法来解决，具体思路如下：

给定字符串si,s2,首先定义•个函数D(i,j)(OWiWstrlen(sl),0

WjWstrlen(s2)),用来表示第一个字符串si长度为i的子串与第二个字符串

s2长度为j的子串的编辑距离。从si变到s2可以通过如下三种操作完成：

⑴添加操作。假设已经计算出D(i,j-1)的值lsl[0…i]与s2[0…jT]的

编辑距离),则D(i,j)=D(i,j-l)+l(sl长度为i的字串后面添加s2[j]即

可)。

(2)删除操作。假设已经计算出D(iT,j)的值(sl[0…i-l]到s2[0…j]的

编辑距离)，则D(i,j)=D(i-l,j)+l(sl长度为i的字串删除最后的字符si[j]即

可).

(3)替换操作。假设已经计算出D(i-1,j-1)的值(sl[0…iT]与s2[0-j-l]

的编辑距离),如果sl[i]=s2[j],那么D(i,j)=D(iT,j-1),如果

sl[i]!=s2[j],那么D(i,j)=D(i-l,替换sl[i]为s2[j],或替换s2[j]

为sl[i])0

此外，D(0,j)=j且D(i,0)=i(一个字符串与空字符串的编辑距离为这个字

符串的长度)。

由此可以得出如下实现方式：对于给定的字符串si、s2,定义一个二维数

组D,则有以下几种可能性。

(1)如果i==0,那么D[i,j]=j(0^j<strlen(s2))o

(2)如果j==0,那么D[i,j]=i(O^i<strlen(sl))o

(3)如果i>0且j>0,

(a)如果sl[i]==s2[j],那么D(i,j)=min{edit(i-l,j)+l,edit(i,j-

1)+1,edit(i-l,j-l)}0

(b)如果si[i]!=s2[j],那么D(i,j)=min{edit(i-l,j)+l,edit(i,j-

1)+1,edit(i-l,j-l)+l}o

通过以上分析可以发现，对于第一个问题可以直接采用上述的方法来解

决。对于第一个问题，由于替换操作是插入或删除操作的两倍，只需要修改如

下条件即可：

如果sl[i]!=s2[j],那么D(i,j)=min{edit(i-l,j)+l,edit(i,

edit(i-l,j-l)+2)o

根据上述分析•，给出实现代码如下：

classEditDistance:

defmins(self,a,b,c):

tmp=aifa<belseb

returntmpiftmp<celsec

#参数replaceWight用来表示替换操作与插入删除操作相比的倍数

defedit(self,si,s2,replaceWight):

#两个空串的编辑距离为0

ifsl==Noneands2==None:

return0

并如果si为空串，那么编辑距离为s2的长度

ifsl==None:

returnlen(s2)

ifs2==None:

returnlen(sl)

lenl=len(sl)

Ien2=len(s2)

#申请一维数组来存储中间的计算结果

D=[([None]*(len2+1))foriinrange(lenl+1)]

i=0

whilei<lenl+l:

D[i][0]=i

i+=l

i=0

whilei<len2+l:

i+=l

i=l

whilei<lenl+l:

J=1

whilej<len2+l:

iflist(si)[i-l]==list(s2)[j-l]:

D[i][j]=self.mins(D[i-l][j]+l,D[i]\D[i-1][j-1])

else:

D[il[j]=min(D[i-l][j]+l,D[i]D[i-1][j-1]X+replaceWight)

j+=l

i+=l

・.〃〃

print--------------------

i二0

whilei<lenl+l:

j=0

whilej<len2+l:

printD[i][j],

j+=l

print'\n

i+=l

print〃----------

dis=D[lenl][len2]

returndis

ifname_二二〃main〃：

sl=〃bciln〃

s2二〃fciling”

ed=EditDistance()

print"第一问：“

print.”编辑距离:“+str(od.adit(s1,s2,1))

print"第二问：“

print”编辑距离:n+str(ed.edit(si,s2,2))

程序的运行结果为：

第一问：

01234567

11234567

22123456

33212345

44321234

55432223

编辑距离：3

第二问：

01234567

12345678

23234567

34323456

45432345

56543434

defgetMinPath2(arr):

ifarr==Noneorlen(arr)==0:

return0

returngetMinPath(arr,len(arr)-l,len(arr[0])-l)

if_name_=二〃_main_〃：

arr=[[l,4,3],[8,7,5],[2,1,5]]

printgetMinPath2(arr)

程序的运行结果为：

17

这种方法虽然能得到题目想要的结果，但是效率太低，主要是因为里面有

大量的重复计算过程，比如在计算f(iT,j)与f(jT,i)的过程中都会计算

j-l)o如果把第一次计算得到的f(iT,jT)缓存起来，那么就不需要额

外的计算了，而这也是典型的动态规划的思路，下面重点介绍动态规划方法。

方法二：动态规划法

动态规划法其实也是一种空间换时间的算法，通过缓存计算中间值，从而

减少重复计算的次数，从而提高算法的效率。方法一从arr[mT][n-l]开始逆向

通过递归来求解，而动态规划要求正向求解，以便利用前面计算出来的结果。

对于本题而言,显然f(i,0)=arr[0][0]+***+arr[i][0],

f[0,j]=arr[0][0]+--+arr[0][j]o根据递推公式：f(i,j)=min{f(i-1,j),

f(i,j-l)}+arr[i][j],从i=Lj=l开始顺序遍历二维数组,可以在遍历的过

程中求出所有的f(i,j)的值，同时把求出的值保存到另外一个二维数组中以供

后续使用。当然在遍历的过程中可以确定这个最小值对应的路线，在这种方法

中，除了求出最小值以外顺便还打印出了最小值的路线，实现代码如下：

defgetMinPath(arr):

ifarr==Noneorlen(arr)-0:

return0

row=len(arr)

col=len(arr[0])

#用来保存计算的中间值

cache=[([None]*col)foriinrange(row)]

cache[0][0]=arr[0][0]

i=l

whilei<col:

cache[0][i]=cache[0-[i-l]+arr[0][i]

i+=l

j=l

whilej<row:

cachefj][O]=cache[j-1][O]+arr[j][0]

j+=l

并在遍历二维数组的过程中不断把计算结果保存到cache中

print〃路径：〃，

i=l

whilei<row:

j=l

whilej<col:

并可以确定选择的路线为arr[i][j-l]

ifcache[i-l][j]>cache[i][j_l]:

cache[i][j]=cache[i-[j-l]+arr[i][j]

print〃[〃+str(i)+”,"+str(jT)+〃]〃，

并可以确定选择的路线为arr[i-l][j]

else:

cache[i][j]=cache[i-l][j]+arr[i][j]

print,”["+str(iT)+”,"+str(j)+”]〃，

j+=1

i+=l

print("[〃+str(rowT)+”,"+str(colT)+']”)

return〃最小值为：”+str(cache[rowT][colT])

if—name一二二〃—main—〃：

arr=[[l,4,3],[8,7,5],[2,1,5]]

printgetMinPath(arr)

程序的运行结果为：

路径：[0,1][0,2][2,0][2,1][2,2]

最小值为：17

算法性能分析：

这种方法对二维数组进行了一次遍历，因此其时间复杂度为0(m*n)。此外

由于这种方法同样申请了一个二维数组来保存中间结果，因此其空间复杂度也

为0(m*n)o

[考点]如何在二维数组中寻找最短路线

3.编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节

截取的字符串。但是要保证汉字不被截半个，例如〃人ABC〃4,应该截为〃人

AB〃，输入〃人ABC们DEF〃,6,应该输出为〃人ABC〃而不是〃人ABC+们的半个〃。

正确答案：

在Python2.7语言中，在开头声明encoding为utf8,一个中文占3个字节。本

题先将中文转成unicode编码，便于识别是否是中文，再根据字符长度进行截

取。根据这个思路，可以采用如下代码来满足题目的要求：

并判断字符c是否是中文字符，如果是返回True

defisChinese(c):

returnTrueifc>=u，\u4e00，andc<=u，\u9fa5，elseFalse

deftruncateStr(strs,lens):

if(strs==Noneorstrs=〃〃orlens==0):

〃〃

return

#chrArr=list(strs)

chrArr=strs

sb二〃〃

count=0#用来记录当前截取字符的长度

forccinchrArr:

if(count<lens):

#printsb,count.

if(isChinese(cc)):

#如果要求截取予串的长度只差1个或者2个字符，但是接下来的字符是

中文，

’#那么截取结果子串中不保存这个中文字符

ifcount+l<=lensandcount+3>lens:

returnsb

count=count+3

sb=sb+cc

else:

count=count+1

sb=sb+cc

else:

break

returnsb

if_name_二="_main_〃：

sb二〃人ABC们DEF"

sb_unicode=unicode(sb,'utf8')并转成unicode编码

printtruncateStr(sbunicode,6)

程序的运行结果为：

人ABC

［考点］如何截取包含中文的字符串

4.编写一个函数，根据两个文件的绝对路径算出其相对路径。例如

a=Vqihoo/app/a/b/c/d/new.c,b=，7qihoo/app/l/2/test.cz，,那么b相对于a

的相对路径是〃・・/・・/•・/・・〃/2/teSt.c〃

正确答案：

首先找近两个字符串相同的路径(/aihoo/app),然后处理不同的目录结构

(a="/a/b/c/d/new.c",b=71/2/test.c〃)。处理方法为：对于a中的每一个目

录结构，在b前面加“・./”，对于本题而言，除了相同的目录前缀外，a还有

四级目录a/b/c/d,因此只需要在b=Vl/2/test.c〃前面增加四个〃../〃得到的

〃/2/test.c〃就是b相对a的路径。实现代码如下：

defgetRelativePath(pathl,path2):

ifpath1二二Noneorpath2==None:

print〃参数不合法\n"

return

relativePath二〃〃

并用来指向两个路径中不同目录的起始路径

diff1=0

diff2=0

i=0

j=0

lenl=len(pathl)

Ien2=len(path2)

whilei<lenlandj<len2:

#如果目录相同，那么往后遍历

iflist(pathl)[i]==list(path2)[j]:

iflist(pathl)[i]==，/':

diffl=i

diff2=j

i+=l

j+=l

else:

#不同的目录

并把pathl非公共部分的目录转换为〃/

diffl+=l#跳过目录分隔符/

whilediff1<lenl:

并碰到下一级目录

iflist(pathl)[diff1]==，/":

relativePath+=z，../〃

diff1+=1

并把path2的非公共部分的路径加到后面

diff2+=l

relativePath+=path2[diff2:]

break

returnrelativePath

if_name_二二〃_main_〃：

pathl=z，/qihoo/app/a/b/c/d/new.c〃

path2=z7qihoo/app/1/2/test.c〃

printgetRelativePath(pathl,path2)

程序的运行结果为：

/1/2/test.c

算法性能分析：

这种方法的时间复杂度与空间复杂度都为O(max(m,n))(其中，m、n分别

为两个路径的长度)。

［考点］如何求相对路径

5.给定一个词典和两个长度相同的“开始”和“目标”的单词。找到从“开

始”到“目标”最小链的长度。如果它存在，那么这条链中的相邻单词只有一

个字符不同，而链中的每个单词都是有效的单词，即它存在于词典中。可以假

设词典中存在“目标”字，所有词典词的长度相同。

例如：

给定一个单词词典为：［pooN,pbcc,zamc,pole,pbea,pblc,poIN］

start=TooN

target=pbca

输出结果为：7

因为：TooN(start)-pooN-poIN-poIc-pblc-pbcc-pbca(target).

正确答案：

本题主要的解决方法为：使用BFS的方式从给定的字符串开始遍历所有相邻(两

个单词只有一个不同的字符)的单词，直到遍历找到目标单词或者遍历完所有的

单词为止。实现代码如下：

fromcollectionsimportdeque

并用来存储单词链的队列

classQltem:

def_init__(self,word,lens):

self,word=word

self.lens=lens

#判断两个字符串是否只有一个不同的字符

defisAdjacent(a,b):

diff=O

lens=len(a)

i=0

whilei<lens:

iflist(a)[i]!=list(