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

編輯距離又稱Levenshtein距離，是指兩個字符串之間由一個轉成另一個所需的最少編輯操作次數。許可的編輯操作包括將一個字符替換成另一個字符、插入一個字符、刪除一個（江南博哥）字符。請設計并實現一個算法來計算兩個字符串的編輯距離，并計算其復雜度。在某些應用場景下，替換操作的代價比較高，假設替換操作的代價是插入和刪除的兩倍，算法該如何調整?正確答案：本題可以使用動態規劃的方法來解決，具體思路如下：

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

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

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

(3)替換操作。假設已經計算出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(一個字符串與空字符串的編輯距離為這個字符串的長度)。

由此可以得出如下實現方式：對于給定的字符串s1、s2，定義一個二維數組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}。

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

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

根據上述分析，給出實現代碼如下：

classEditDistance:

defmins(self,a,b,c):

tmp=aifa＜belseb

returntmpiftmp＜celsec

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

defedit(self,s1,s2,replaceWight):

#兩個空串的編輯距離為0

ifs1==Noneands2==None:

return0

#如果s1為空串,那么編輯距離為s2的長度

ifs1==None:

returnlen(s2)

ifs2==None:

returnlen(s1)

len1=len(s1)

len2=len(s2)

#申請二維數組來存儲中間的計算結果

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

程序的運行結果為：

第一問：

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

01234567

11234567

22123456

33212345

44321234

55432223

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

編輯距離：3

第二問：

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

01234567

12345678

23234567

34323456

45432345

56543434

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

編輯距離：4

算法性能分析：

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

2.

尋找一條從左上角(arr[0][0])到右下角(arr[m-1][n-1])的路線，使得沿途經過的數組中的整數的和最小。正確答案：對于這道題，可以從右下角開始倒著來分析這個問題：最后一步到達arr[m-1][n-1]只有兩條路：通過arr[m-2][n-1]到達或通過arr[m-1][n-2]到達，假設從arr[0][0]到arr[m-2][n-1]沿途數組最小值為f(m-2，n-1)，到arr[m-1][n-2]沿途數組最小值為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]的路徑可以采用同樣的方式來確定。

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

方法一：遞歸法

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

defgetMinPath(arr,i,j):

#倒著走到了第一個結點,遞歸結束

ifi==0andj==0:

returnarr[i][j]

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

elifi＞0andj＞0:

returnarr[i][j]+\

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

#下面兩個條件只可選擇一個

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)

程序的運行結果為：

17

這種方法雖然能得到題目想要的結果，但是效率太低，主要是因為里面有大量的重復計算過程，比如在計算f(i-1,j)與f(j-1，i)的過程中都會計算f(i-1,j-1)。如果把第一次計算得到的f(i-1,j-1)緩存起來，那么就不需要額外的計算了，而這也是典型的動態規劃的思路，下面重點介紹動態規劃方法。

方法二：動態規劃法

動態規劃法其實也是一種空間換時間的算法，通過緩存計算中間值，從而減少重復計算的次數，從而提高算法的效率。方法一從arr[m-1][n-1]開始逆向通過遞歸來求解，而動態規劃要求正向求解，以便利用前面計算出來的結果。

對于本題而言，顯然f(i,0)=arr[0][0]+…+arr[i][0],f[0,j]=arr[0][0]+…+arr[0][j]。根據遞推公式：f(i,j)=min{f(i-1,j),f(i,j-1)}+arr[i][j]，從i=1，j=1開始順序遍歷二維數組，可以在遍歷的過程中求出所有的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=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

#在遍歷二維數組的過程中不斷把計算結果保存到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)

程序的運行結果為：

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

最小值為：17

算法性能分析：

這種方法對二維數組進行了一次遍歷，因此其時間復雜度為O(m*n)。此外由于這種方法同樣申請了一個二維數組來保存中間結果，因此其空間復雜度也為O(m*n)。[考點]如何在二維數組中尋找最短路線

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+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')#轉成unicode編碼

printtruncateStr(sb_unicode,6)

程序的運行結果為：

人ABC[考點]如何截取包含中文的字符串

4.

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

defgetRelativePath(path1,path2):

ifpath1==Noneorpath2==None:

print"參數不合法\n"

return

relativePath=""

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

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非公共部分的目錄轉換為"/

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

whilediff1＜len1:

#碰到下一級目錄

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)

程序的運行結果為：

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

算法性能分析：

這種方法的時間復雜度與空間復雜度都為O(max(m,n))(其中，m、n分別為兩個路徑的長度)。[考點]如何求相對路徑

5.

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

例如：

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

start=TooN

target=pbca

輸出結果為：7

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

fromcollectionsimportdeque

#用來存儲單詞鏈的隊列

classQItem:

def_init__(self,word,lens):

self.word=word

self.lens=lens

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

defisAdjacent(a,b):

diff=0