Python程序員面試分類真題15

Python程序員面試分類真題151.

編輯距離又稱Levenshtein距離，是指兩個(gè)字符串之間由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符、插入一個(gè)字符、刪除一個(gè)（江南博哥）字符。請(qǐng)?jiān)O(shè)計(jì)并實(shí)現(xiàn)一個(gè)算法來計(jì)算兩個(gè)字符串的編輯距離，并計(jì)算其復(fù)雜度。在某些應(yīng)用場(chǎng)景下，替換操作的代價(jià)比較高，假設(shè)替換操作的代價(jià)是插入和刪除的兩倍，算法該如何調(diào)整?正確答案：本題可以使用動(dòng)態(tài)規(guī)劃的方法來解決，具體思路如下：

給定字符串s1，s2，首先定義一個(gè)函數(shù)D(i,j)(0≤i≤strlen(s1)，0≤j≤strlen(s2))，用來表示第一個(gè)字符串s1長(zhǎng)度為i的子串與第二個(gè)字符串s2長(zhǎng)度為j的子串的編輯距離。從s1變到s2可以通過如下三種操作完成：

(1)添加操作。假設(shè)已經(jīng)計(jì)算出D(i,j-1)的值(s1[0…i]與s2[0…j-1]的編輯距離)，則D(i,j)=D(i,j-1)+1(s1長(zhǎng)度為i的字串后面添加s2[j]即可)。

(2)刪除操作。假設(shè)已經(jīng)計(jì)算出D(i-1,j)的值(s1[0…i-1]到s2[0…j]的編輯距離)，則D(i,j)=D(i-1,j)+1(s1長(zhǎng)度為i的字串刪除最后的字符s1[j]即可)。

(3)替換操作。假設(shè)已經(jīng)計(jì)算出D(i-1,j-1)的值(s1[0…i-1]與s2[0…j-1]的編輯距離)，如果s1[i]=s2[j]，那么D(i,j)=D(i-1,j-1)，如果s1[i]!=s2[j]，那么D(i,j)=D(i-1,j-1)+1(替換s1[i]為s2[j]，或替換s2[j]為s1[i])。

此外，D(0,j)=j且D(i,0)=i(一個(gè)字符串與空字符串的編輯距離為這個(gè)字符串的長(zhǎng)度)。

由此可以得出如下實(shí)現(xiàn)方式：對(duì)于給定的字符串s1、s2，定義一個(gè)二維數(shù)組D，則有以下幾種可能性。

(1)如果i==0，那么D[i,j]=j(0≤j≤strlen(s2))。

(2)如果j==0，那么D[i,j]=i(0≤i≤strlen(s1))。

(3)如果i＞0且j＞0，

(a)如果s1[i]==s2[j]，那么D(i,j)=min{edit(i-1,j)+1,edit(i,j-1)+1,edit(i-1,j-1)}。

(b)如果s1[i]!=s2[j]，那么D(i,j)=min{edit(i-1,j)+1,edit(i,j-1)+1,edit(i-1,j-1)+1}。

通過以上分析可以發(fā)現(xiàn)，對(duì)于第一個(gè)問題可以直接采用上述的方法來解決。對(duì)于第二個(gè)問題，由于替換操作是插入或刪除操作的兩倍，只需要修改如下條件即可：

如果s1[i]!=s2[j]，那么D(i,j)=min{edit(i-1,j)+1,edit(i,j-1)+1,edit(i-1,j-1)+2}。

根據(jù)上述分析，給出實(shí)現(xiàn)代碼如下：

classEditDistance:

defmins(self,a,b,c):

tmp=aifa＜belseb

returntmpiftmp＜celsec

#參數(shù)replaceWight用來表示替換操作與插入刪除操作相比的倍數(shù)

defedit(self,s1,s2,replaceWight):

#兩個(gè)空串的編輯距離為0

ifs1==Noneands2==None:

return0

#如果s1為空串,那么編輯距離為s2的長(zhǎng)度

ifs1==None:

returnlen(s2)

ifs2==None:

returnlen(s1)

len1=len(s1)

len2=len(s2)

#申請(qǐng)二維數(shù)組來存儲(chǔ)中間的計(jì)算結(jié)果

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

i=0

whilei＜len1+1:

D[i][0]=i

i+=1

i=0

whilei＜len2+1:

D[0][i]=i

i+=1

i=1

whilei＜len1+1:

j=1

whilej＜len2+1:

iflist(s1)[i-1]==list(s2)[j-1]:

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

else:

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

j+=1

i+=1

print"--------------------"

i=0

whilei＜len1+1:

j=0

whilej＜len2+1:

printD[i][j],

j+=1

print'\n'

i+=1

print"--------------------"

dis=D[len1][len2]

returndis

if__name__=="__main__":

s1="bciln"

s2="fciling"

ed=EditDistance()

print”第一問：”

print”編輯距離：”+str(ed.edit(s1,s2,1))

print”第二問：”

print”編輯距離：”+str(ed.edit(s1,s2,2))

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

第一問：

-----------------------------------------

01234567

11234567

22123456

33212345

44321234

55432223

-----------------------------------------

編輯距離：3

第二問：

-----------------------------------------

01234567

12345678

23234567

34323456

45432345

56543434

-----------------------------------------

編輯距離：4

算法性能分析：

這種方法的時(shí)間復(fù)雜度與空間復(fù)雜度都為O(m*n)(其中，m、n分別為兩個(gè)字符串的長(zhǎng)度)。[考點(diǎn)]如何求字符串的編輯距離

2.

尋找一條從左上角(arr[0][0])到右下角(arr[m-1][n-1])的路線，使得沿途經(jīng)過的數(shù)組中的整數(shù)的和最小。正確答案：對(duì)于這道題，可以從右下角開始倒著來分析這個(gè)問題：最后一步到達(dá)arr[m-1][n-1]只有兩條路：通過arr[m-2][n-1]到達(dá)或通過arr[m-1][n-2]到達(dá)，假設(shè)從arr[0][0]到arr[m-2][n-1]沿途數(shù)組最小值為f(m-2，n-1)，到arr[m-1][n-2]沿途數(shù)組最小值為f(m-1，n-2)。因此，最后一步選擇的路線為min{f(m-2,n-1),f(m-1,n-2)}。同理，選擇到arr[m-2][n-1]或arr[m-1][n-2]的路徑可以采用同樣的方式來確定。

由此可以推廣到一般的情況。假設(shè)到arr[i-1][j]與arr[i][j-1]的最短路徑的和為f(i-1,j)和f(i,j-1)，那么到達(dá)arr[i][j]的路徑上的所有數(shù)字和的最小值為：f(i,j)=min{f(i-1,j),f(i,j-1)}+arr[i][j]。

方法一：遞歸法

根據(jù)這個(gè)遞歸公式可知，可以采用遞歸的方法來實(shí)現(xiàn)，遞歸的結(jié)束條件為遍歷到arr[0][0]。在求解的過程中還需要考慮另外一種特殊情況：遍歷到arr[i][j](當(dāng)i=0或j=0)的時(shí)候只能沿著一條固定的路徑倒著往回走直到arr[0][0]。根據(jù)這個(gè)遞歸公式與遞歸結(jié)束條件可以給出實(shí)現(xiàn)代碼如下：

defgetMinPath(arr,i,j):

#倒著走到了第一個(gè)結(jié)點(diǎn),遞歸結(jié)束

ifi==0andj==0:

returnarr[i][j]

#選取兩條可能路徑上的最小值

elifi＞0andj＞0:

returnarr[i][j]+\

min(getMinPath(arr,i-1,j),getMinPath(arr,i,j-1))

#下面兩個(gè)條件只可選擇一個(gè)

elifi＞0andj==0:

returnarr[i][j]+getMinPath(arr,i-1,j)

#j＞0&&i==0

else:

returnarr[i][j]+getMinPath(arr,i,j-1)

defgetMinPath2(arr):

ifarr==Noneorlen(arr)==0:

return0

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

if__name__=="__main__":

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

printgetMinPath2(arr)

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

17

這種方法雖然能得到題目想要的結(jié)果，但是效率太低，主要是因?yàn)槔锩嬗写罅康闹貜?fù)計(jì)算過程，比如在計(jì)算f(i-1,j)與f(j-1，i)的過程中都會(huì)計(jì)算f(i-1,j-1)。如果把第一次計(jì)算得到的f(i-1,j-1)緩存起來，那么就不需要額外的計(jì)算了，而這也是典型的動(dòng)態(tài)規(guī)劃的思路，下面重點(diǎn)介紹動(dòng)態(tài)規(guī)劃方法。

方法二：動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃法其實(shí)也是一種空間換時(shí)間的算法，通過緩存計(jì)算中間值，從而減少重復(fù)計(jì)算的次數(shù)，從而提高算法的效率。方法一從arr[m-1][n-1]開始逆向通過遞歸來求解，而動(dòng)態(tài)規(guī)劃要求正向求解，以便利用前面計(jì)算出來的結(jié)果。

對(duì)于本題而言，顯然f(i,0)=arr[0][0]+…+arr[i][0],f[0,j]=arr[0][0]+…+arr[0][j]。根據(jù)遞推公式：f(i,j)=min{f(i-1,j),f(i,j-1)}+arr[i][j]，從i=1，j=1開始順序遍歷二維數(shù)組，可以在遍歷的過程中求出所有的f(i,j)的值，同時(shí)把求出的值保存到另外一個(gè)二維數(shù)組中以供后續(xù)使用。當(dāng)然在遍歷的過程中可以確定這個(gè)最小值對(duì)應(yīng)的路線，在這種方法中，除了求出最小值以外順便還打印出了最小值的路線，實(shí)現(xiàn)代碼如下：

defgetMinPath(arr):

ifarr==Noneorlen(arr)==0:

return0

row=len(arr)

col=len(arr[0])

#用來保存計(jì)算的中間值

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

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

i=1

whilei＜col:

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

i+=1

j=1

whilej＜row:

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

j+=1

#在遍歷二維數(shù)組的過程中不斷把計(jì)算結(jié)果保存到cache中

print"路徑:",

i=1

whilei＜row:

j=1

whilej＜col:

#可以確定選擇的路線為arr[i][j-1]

ifcache[i-1][j]＞cache[i][j-1]:

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

print"["+str(i)+","+str(j-1)+"]",

#可以確定選擇的路線為arr[i-1][j]

else:

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

print"["+str(i-1)+","+str(j)+"]",

j+=1

i+=1

print("["+str(row-1)+","+str(col-1)+"]")

return"最小值為:"+str(cache[row-1][col-1])

if__name__=="__main__":

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

printgetMinPath(arr)

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

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

最小值為：17

算法性能分析：

這種方法對(duì)二維數(shù)組進(jìn)行了一次遍歷，因此其時(shí)間復(fù)雜度為O(m*n)。此外由于這種方法同樣申請(qǐng)了一個(gè)二維數(shù)組來保存中間結(jié)果，因此其空間復(fù)雜度也為O(m*n)。[考點(diǎn)]如何在二維數(shù)組中尋找最短路線

3.

編寫一個(gè)截取字符串的函數(shù)，輸入為一個(gè)字符串和字節(jié)數(shù)，輸出為按字節(jié)截取的字符串。但是要保證漢字不被截半個(gè)，例如"人ABC"4，應(yīng)該截為"人AB"，輸入"人ABC們DEF"，6，應(yīng)該輸出為"人ABC"而不是"人ABC+們的半個(gè)"。正確答案：在Python2.7語言中，在開頭聲明encoding為utf8，一個(gè)中文占3個(gè)字節(jié)。本題先將中文轉(zhuǎn)成unicode編碼，便于識(shí)別是否是中文，再根據(jù)字符長(zhǎng)度進(jìn)行截取。根據(jù)這個(gè)思路，可以采用如下代碼來滿足題目的要求：

#判斷字符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#用來記錄當(dāng)前截取字符的長(zhǎng)度

forccinchrArr:

if(count＜lens):

#printsb,count

if(isChinese(cc)):

#如果要求截取予串的長(zhǎng)度只差1個(gè)或者2個(gè)字符,但是接下來的字符是中文,

#那么截取結(jié)果子串中不保存這個(gè)中文字符

ifcount+1＜=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')#轉(zhuǎn)成unicode編碼

printtruncateStr(sb_unicode,6)

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

人ABC[考點(diǎn)]如何截取包含中文的字符串

4.

編寫一個(gè)函數(shù)，根據(jù)兩個(gè)文件的絕對(duì)路徑算出其相對(duì)路徑。例如a="/qihoo/app/a/b/c/d/new.c",b="/qihoo/app/1/2/test.c"，那么b相對(duì)于a的相對(duì)路徑是"../../../../1/2/teSt.c"正確答案：首先找到兩個(gè)字符串相同的路徑(/aihoo/app)，然后處理不同的目錄結(jié)構(gòu)(a="/a/b/c/d/new.c",b="/1/2/test.c")。處理方法為：對(duì)于a中的每一個(gè)目錄結(jié)構(gòu)，在b前面加“../”，對(duì)于本題而言，除了相同的目錄前綴外，a還有四級(jí)目錄a/b/c/d，因此只需要在b="/1/2/test.c"前面增加四個(gè)"../"得到的"../../"/../1/2/test.c"就是b相對(duì)a的路徑。實(shí)現(xiàn)代碼如下：

defgetRelativePath(path1,path2):

ifpath1==Noneorpath2==None:

print"參數(shù)不合法\n"

return

relativePath=""

#用來指向兩個(gè)路徑中不同目錄的起始路徑

diff1=0

diff2=0

i=0

j=0

len1=len(path1)

len2=len(path2)

whilei＜len1andj＜len2:

#如果目錄相同,那么往后遍歷

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

iflist(path1)[i]=='/':

diff1=i

diff2=j

i+=1

j+=1

else:

#不同的目錄

#把path1非公共部分的目錄轉(zhuǎn)換為"/

diff1+=1#跳過目錄分隔符/

whilediff1＜len1:

#碰到下一級(jí)目錄

iflist(path1)[diff1]=='/':

relativePath+="../"

diff1+=1

#把path2的非公共部分的路徑加到后面

diff2+=1

relativePath+=path2[diff2:]

break

returnrelativePath

if__name__=="__main__":

path1="/qihoo/app/a/b/c/d/new.c"

path2="/qihoo/app/1/2/test.c"

printgetRelativePath(path1,path2)

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

../../../../1/2/test.c

算法性能分析：

這種方法的時(shí)間復(fù)雜度與空間復(fù)雜度都為O(max(m,n))(其中，m、n分別為兩個(gè)路徑的長(zhǎng)度)。[考點(diǎn)]如何求相對(duì)路徑

5.

給定一個(gè)詞典和兩個(gè)長(zhǎng)度相同的“開始”和“目標(biāo)”的單詞。找到從“開始”到“目標(biāo)”最小鏈的長(zhǎng)度。如果它存在，那么這條鏈中的相鄰單詞只有一個(gè)字符不同，而鏈中的每個(gè)單詞都是有效的單詞，即它存在于詞典中。可以假設(shè)詞典中存在“目標(biāo)”字，所有詞典詞的長(zhǎng)度相同。

例如：

給定一個(gè)單詞詞典為:[pooN,pbcc,zamc,poIc,pbca,pbIc,poIN]

start=TooN

target=pbca

輸出結(jié)果為：7

因?yàn)椋篢ooN(start)-pooN-poIN-poIc-pbIc-pbcc-pbca(target).正確答案：本題主要的解決方法為：使用BFS的方式從給定的字符串開始遍歷所有相鄰(兩個(gè)單詞只有一個(gè)不同的字符)的單詞，直到遍歷找到目標(biāo)單詞或者遍歷完所有的單詞為止。實(shí)現(xiàn)代碼如下：

fromcollectionsimportdeque

#用來存儲(chǔ)單詞鏈的隊(duì)列

classQItem:

def_init__(self,word,lens):

self.word=word

self.lens=lens

#判斷兩個(gè)字符串是否只有一個(gè)不同的字符

defisAdjacent(a,b):

diff=0