2023年程序員編程藝術(shù)第二十八二十九章最大連續(xù)乘積子串字符串編輯距離

程序員編程藝術(shù)第二十八~二十九章:最大連續(xù)乘積子串、字符串編輯距離第二十八～二十九章：最大連續(xù)乘積子串、字符串編輯距離前言時(shí)間轉(zhuǎn)瞬即逝,一轉(zhuǎn)眼,又有4個(gè)多月沒來更新blog了,過去4個(gè)月都在干啥呢?對(duì)的，今２0２3年元旦和朋友一起搭了個(gè)方便朋友們找工作的編程面試算法論壇:為學(xué)論壇。最近則在負(fù)責(zé)一款在線編程挑戰(zhàn)平臺(tái)-－英雄會(huì)的產(chǎn)品運(yùn)營(yíng)，當(dāng)然拉，雖說是產(chǎn)品運(yùn)營(yíng)，事實(shí)上身兼“數(shù)職”:出題審題，寫代碼測(cè)試一個(gè)不落下。最近跟百度的幾個(gè)朋友線下閑聊，聽他們說,百度校招群內(nèi)的不少朋友在找工作的時(shí)候都看過我的blog，一聽當(dāng)即便激起了自己重寫更新此blog的欲望,恰巧眼下陽(yáng)春三月（雖說已是3月，奇妙的是，前兩天北京還下了一場(chǎng)大雪),又到了找工作的季節(jié)(相對(duì)于每年的９月份來說,3月則是一個(gè)小高潮）,那就從繼續(xù)更新專為找工作準(zhǔn)備筆試面試的程序員編程藝術(shù)開始吧。本文講兩個(gè)問題,第二十八章、最大連續(xù)乘積子串,第二十九章、字符串編輯距離,這兩個(gè)問題皆是各大IT公司最喜歡出的筆試面試題,比如說前者是小米２023年校招筆試原題,而后者則更是反復(fù)出現(xiàn),如去年9月２6日百度一二面試題，1０月9日騰訊面試題第1小題,１0月13日百度2０23校招北京站筆試題第二大道題第３小題，及去年10月１5日２０23年Google校招筆試最后一道大題。OK，歡迎朋友們?cè)诒疚南聟⑴c討論,假如用Jａva/C#的朋友想在線編譯自己的代碼，可以上英雄會(huì)提交你的代碼,有任何問題，歡迎隨時(shí)不吝批評(píng)或指正，感謝。第二十九章、最大連續(xù)乘積子串題目描述:給一個(gè)浮點(diǎn)數(shù)序列,取最大乘積連續(xù)子串的值，例如-2.５,4，0,３,０.5,8,-1,則取出的最大乘積連續(xù)子串為3,0.5，8。也就是說,上述數(shù)組中，3０.５８這3個(gè)數(shù)的乘積3＊0．５*８＝1２是最大的，并且是連續(xù)的。提醒：此最大乘積連續(xù)子串與最大乘積子序列不同,請(qǐng)勿混淆，前者子串規(guī)定連續(xù),后者子序列不規(guī)定連續(xù)。也就是說:最長(zhǎng)公共子串(ＬongestCommｏｎSubｓtrinｇ）和最長(zhǎng)公共子序列（LongeｓtCommonSｕｂseｑuｅnｃe，ＬCＳ)的區(qū)別:子串(Suｂstrｉｎg)是串的一個(gè)連續(xù)的部分，子序列（Suｂsequeｎce）則是從不改變序列的順序，而從序列中去掉任意的元素而獲得的新序列；更簡(jiǎn)略地說,前者(子串）的字符的位置必須連續(xù)，后者（子序列LCＳ）則不必。比如字符串a(chǎn)cdｆg同ａkdｆc的最長(zhǎng)公共子串為dｆ，而他們的最長(zhǎng)公共子序列是aｄf。LCS可以使用動(dòng)態(tài)規(guī)劃法解決。解答:解法一、兩個(gè)for循環(huán)直接輪詢或許,讀者初看此題,自然會(huì)想到最大乘積子序列問題類似于最大子數(shù)組和問題：,最簡(jiǎn)樸粗暴的方式便是用鏈兩個(gè)fｏr循環(huán)直接輪詢。for(inｔi＝0；i<nｕm;i++){ｄoublex=ａrｒs[i];foｒ(iｎtj=i+1;j<num;j++)｛ｘ＊=arrs[ｊ];iｆ(x＞mａx){max=x;sｔaｒt=arrs[i];end=arrs[j];}｝解法二、雖說類似于最大子數(shù)組和問題，可以用兩個(gè)fｏr循環(huán)直接輪詢搞定,但事實(shí)上具體解決起來諸多不同,為什么呢，由于乘積子序列中有正有負(fù)也還也許有0。我們可以把問題簡(jiǎn)化成這樣:數(shù)組中找一個(gè)子序列,使得它的乘積最大；同時(shí)找一個(gè)子序列，使得它的乘積最小(負(fù)數(shù)的情況）。由于雖然我們只要一個(gè)最大積,但由于負(fù)數(shù)的存在,我們同時(shí)找這兩個(gè)乘積做起來反而方便。也就是說，不僅記錄最大乘積,也要記錄最小乘積。So，我們讓mａxＣｕrrent表達(dá)當(dāng)前最大乘積的candidatｅ,minCurrｅｎt反之,表達(dá)當(dāng)前最小乘積的candiｄaｔe(用candidａt(yī)ｅ這個(gè)詞是由于只是也許成為新一輪的最大／最小乘積），而maxProduct則記錄到目前為止所有最大乘積candidａt(yī)es的最大值。由于空集的乘積定義為1,在搜索數(shù)組前,maxCurｒent,minCurｒeｎt，ｍａxProdｕｃt都賦為1。假設(shè)在任何時(shí)刻你已有了maxCurrenｔ和ｍｉnＣurｒｅｎt這兩個(gè)最大／最小乘積的candidates,新讀入數(shù)組的元素x（ｉ)后,新的最大乘積ｃanｄidaｔｅ只也許是maxCｕｒreｎt或者mｉnCuｒreｎｔ與ｘ(i)的乘積中的較大者,假如ｘ(ｉ)<0導(dǎo)致maxCuｒrent<ｍinCｕｒrｅnｔ，需要互換這兩個(gè)candiｄａt(yī)es的值。當(dāng)任何時(shí)候maxCuｒrｅnt<1,由于1（空集)是比ｍaxCｕrrenｔ更好的cａndidatｅ，所以更新maxCurｒeｎt為１，類似的可以更新minＣurrｅnｔ。任何時(shí)候maxCurrent假如比最佳的mａxＰroduct大,更新maxProｄｕct。具體代碼如下：templａｔe<ｔypｅnameCｏmparable>Cｏｍparablemaxprod(coｎsｔvector<Comｐａｒable>&v){inti;ＣoｍpaｒaｂlｅｍaｘＰroducｔ＝1;CｏmpaｒablｅminProducｔ=1;CompａrablemａxCurrｅnt=1;ＣｏmｐaraｂleminCurrent＝1;//Comparablet；foｒ(ｉ=０;ｉ＜ｖ.sｉｚe();ｉ+＋)｛mａｘCｕrｒeｎt＊＝v[i];ｍinCuｒｒｅnt*=v[i］;ｉｆ(maｘCurrent>maxＰrｏdｕｃt)maｘＰｒoduｃt=ｍaxＣurreｎt;ｉf(ｍinCurrｅnt>maxＰrodｕｃｔ)maｘProduct=mｉnCｕrrenｔ；if(maｘCurrｅnt<minＰroｄuct)minPrｏduct=maxCurrenｔ；if(minCuｒreｎt<minＰroduct）minProｄuct=mｉｎＣurｒent;ｉf（miｎCurrent>maxＣuｒreｎt)swap(ｍaxCuｒｒent,minCｕrｒent);if(maxCurｒent<1)mａxＣuｒｒeｎt＝１;/／ｉf(miｎCurｒenｔ>1)//minCurｒent＝1;｝ｒｅturnｍaxProdｕcｔ;}解法三、本題除了上述類似最大子數(shù)組和的解法,也可以直接用動(dòng)態(tài)規(guī)劃求解(其實(shí)，上述的解法一本質(zhì)上也是動(dòng)態(tài)規(guī)劃，只是解題所表現(xiàn)出來的具體形式與接下來的解法二不同罷了。這個(gè)不同就在于下面的解法二會(huì)寫出動(dòng)態(tài)規(guī)劃問題中經(jīng)典常見的狀態(tài)轉(zhuǎn)移方程，而解法一是直接求解)。具體解法如下：假設(shè)數(shù)組為a［]，直接運(yùn)用動(dòng)歸來求解,考慮到也許存在負(fù)數(shù)的情況,我們用Maｘ來表達(dá)以ａ結(jié)尾的最大連續(xù)子串的乘積值，用Min表達(dá)以a結(jié)尾的最小的子串的乘積值，那么狀態(tài)轉(zhuǎn)移方程為：Maｘ=max{a，Ｍaｘ[i-1]*a，Min[i-１]＊a}；Miｎ＝mｉn{a，Mａｘ[i－１]＊a,Min[i-１]*a};初始狀態(tài)為Max[1]＝Min[1]＝a[１]。代碼如下：/*給定一個(gè)整數(shù)數(shù)組,有正有負(fù)數(shù)，0，正數(shù)組成,數(shù)組下標(biāo)從１算起求最大連續(xù)子序列乘積,并輸出這個(gè)序列,假如最大子序列乘積為負(fù)數(shù),那么就輸出-1用Ｍax[i]表達(dá)以a［i]結(jié)尾乘積最大的連續(xù)子序列用Min[i]表達(dá)以a[i］結(jié)尾乘積最小的連續(xù)子序列由于有復(fù)數(shù)，所以保存這個(gè)是必須的*/voｉdlｏngest_ｍuｌｔiｐle(iｎt＊ａ,intn){int*Ｍin＝nｅwｉnｔ[ｎ＋1]();inｔ*Mａｘ=newint[ｎ+1](）;int*ｐ=nｅｗint［n+1］();//初始化for(ｉntｉ=0;i<=n；i+＋){p［i]=-1;｝Miｎ[1]=a[1];Max［1]=a［1];intmａx_vaｌ=Ｍax[１]；ｆor（ｉntｉ=2；i＜=n;i+＋){Max［ｉ]=ｍaｘ（Mａx[i-1]*a[i],Miｎ[i－1]＊ａ［i］,ａ［i]）;Mｉn[i］=min(Max[ｉ-1］*ａ[i],Min[i-1]*ａ［i］,ａ[i］)；if（ｍax_val<Ｍax［ｉ])max_vaｌ=Ｍax[ｉ];}if(max_val<0)prinｔｆ(＂％d",-1);elseprinｔf("%d＂，max_val)；//內(nèi)存釋放deｌetｅ[]Max;ｄelete[]Min；}提煉簡(jiǎn)化下上面的核心代碼為：ｄoublefunc(ｄoｕblｅ*a,constｉｎtn){douｂlｅ＊maｘA＝neｗdoubｌe[n］;doubｌe*mｉnA=nｅwdoｕble[n];maｘA[０]=miｎA(yù)[０］＝a[0];doｕbｌeｖalue=ｍaxA[0]；ｆｏｒ（inti＝1;ｉ＜n;+＋i){ｍaxA[i]=max(mａｘ(a[i],ｍaxA[i－1]*ａ[i］）,mｉnＡ[i－1]*ａ[i］）;minA[i]=min（min（a[ｉ］,mａｘＡ[i-1]*a[i］)，minA[i-1]*a[i])；vａlue=maｘ(ｖalue,mａｘＡ［i］)；}reｔurｎvalｕe;}變種此外,此題尚有此外的一個(gè)變種形式,即給定一個(gè)長(zhǎng)度為Ｎ的整數(shù)數(shù)組，只允許用乘法,不能用除法，計(jì)算任意(N－１）個(gè)數(shù)的組合中乘積最大的一組,并寫出算法的時(shí)間復(fù)雜度。我們可以把所有也許的（N-1）個(gè)數(shù)的組合找出來,分別計(jì)算它們的乘積,并比較大小。由于總共有N個(gè)(Ｎ-1)個(gè)數(shù)的組合,總的時(shí)間復(fù)雜度為Ｏ(N2）,顯然這不是最佳的解法。OK，以下解答來自編程之美解法1解法2此外,還可以通過度析，進(jìn)一步減少解答問題的計(jì)算量。假設(shè)N個(gè)整數(shù)的乘積為Ｐ，針對(duì)P的正負(fù)性進(jìn)行如下分析（其中，AN-1表達(dá)N-１個(gè)數(shù)的組合,ＰＮ-1表達(dá)Ｎ-1個(gè)數(shù)的組合的乘積）。1.P為0那么，數(shù)組中至少包具有一個(gè)０。假設(shè)除去一個(gè)0之外,其他N-１個(gè)數(shù)的乘積為Q,根據(jù)Q的正負(fù)性進(jìn)行討論:Ｑ為０說明數(shù)組中至少有兩個(gè)０,那么Ｎ-1個(gè)數(shù)的乘積只能為０，返回0;Q為正數(shù)返回Q，由于假如以０替換此時(shí)ＡN－１中的任一個(gè)數(shù),所得到的ＰＮ-1為0，必然小于Q；Q為負(fù)數(shù)假如以０替換此時(shí)AN－1中的任一個(gè)數(shù)，所得到的PN-1為0,大于Ｑ，乘積最大值為0。２.P為負(fù)數(shù)根據(jù)“負(fù)負(fù)得正”的乘法性質(zhì)，自然想到從N個(gè)整數(shù)中去掉一個(gè)負(fù)數(shù)，使得PN-1為一個(gè)正數(shù)。而要使這個(gè)正數(shù)最大，這個(gè)被去掉的負(fù)數(shù)的絕對(duì)值必須是數(shù)組中最小的。我們只需要掃描一遍數(shù)組,把絕對(duì)值最小的負(fù)數(shù)給去掉就可以了。3.P為正數(shù)類似地,假如數(shù)組中存在正數(shù)值，那么應(yīng)當(dāng)去掉最小的正數(shù)值,否則去掉絕對(duì)值最大的負(fù)數(shù)值。上面的解法采用了直接求Ｎ個(gè)整數(shù)的乘積P，進(jìn)而判斷P的正負(fù)性的辦法,但是直接求乘積在編譯環(huán)境下往往會(huì)有溢出的危險(xiǎn)(這也就是本題規(guī)定不使用除法的潛在用意），事實(shí)上可做一個(gè)小的轉(zhuǎn)變，不需要直接求乘積,而是求出數(shù)組中正數(shù)（+）、負(fù)數(shù)(-）和0的個(gè)數(shù),從而判斷Ｐ的正負(fù)性,其余部分與以上面的解法相同。在時(shí)間復(fù)雜度方面，由于只需要遍歷數(shù)組一次，在遍歷數(shù)組的同時(shí)就可得到數(shù)組中正數(shù)（+）、負(fù)數(shù)（-)和0的個(gè)數(shù)，以及數(shù)組中絕對(duì)值最小的正數(shù)和負(fù)數(shù),時(shí)間復(fù)雜度為O（N）。第二十九章、字符串編輯距離題目描述：給定一個(gè)源串和目的串,可以對(duì)源串進(jìn)行如下操作:１.在給定位置上插入一個(gè)字符２.替換任意字符3.刪除任意字符寫一個(gè)程序，返回最小操作數(shù)，使得對(duì)源串進(jìn)行這些操作后等于目的串，源串和目的串的長(zhǎng)度都小于２０2３。提醒：上文前言中已經(jīng)說過了,此題反復(fù)出現(xiàn),最近考的最多的是百度和Gooｇle的筆試面試經(jīng)?？疾臁Ｏ聢D則是2０2３年Gｏoｇｌｅ的校招試題原景重現(xiàn):解答：解法一、此題跟上面的最大連續(xù)乘積子串類似,常見的思緒是動(dòng)態(tài)規(guī)劃,下面是簡(jiǎn)樸的ＤP狀態(tài)方程：／/動(dòng)態(tài)規(guī)劃:／/f[i,j］表達(dá)s［0...ｉ］與ｔ[０.．.j］的最小編輯距離。f[i,j]＝miｎ{f[i-1,j]+1,f［i，j-1]+1,ｆ[i－1，j－１]+（s[i]==t［j]?0:1)}/／分別表達(dá)：添加1個(gè),刪除1個(gè),替換１個(gè)(相同就不用替換）。解法二、類似上述問題類似于編程之美上的下述一題「以下內(nèi)容摘自編程之美第3．３節(jié)」:許多程序會(huì)大量使用字符串。對(duì)于不同的字符串,我們希望可以有辦法判斷其相似限度。我們定義了一套操作方法來把兩個(gè)不相同的字符串變得相同，具體的操作方法為:修改一個(gè)字符(如把“a”替換為“b”）;增長(zhǎng)一個(gè)字符（如把“aｂｄd”變?yōu)椤癮ebdd”）;刪除一個(gè)字符(如把“ｔravelliｎg”變?yōu)椤埃簦颍幔鰁liｎg”）。比如,對(duì)于“aｂcdefｇ”和“ａbcdｅf”兩個(gè)字符串來說,我們認(rèn)為可以通過增長(zhǎng)/減少一個(gè)“g”的方式來達(dá)成目的。上面的兩種方案,都僅需要一次操作。把這個(gè)操作所需要的次數(shù)定義為兩個(gè)字符串的距離，而相似度等于“距離+1”的倒數(shù)。也就是說，“abｃｄeｆg”和“abｃｄeｆ”的距離為1,相似度為１/2=０．5。給定任意兩個(gè)字符串,你是否能寫出一個(gè)算法來計(jì)算出它們的相似度呢?這樣,不久就可以完畢一個(gè)遞歸程序，如下所示:IntCａlｃulaｔeＳｔringDｉsｔance(ｓtｒinｇstｒA,iｎtpABegin,intpAＥｎd，stｒｉｎgstrＢ,iｎtpＢBegiｎ，iｎtpBＥnｄ)｛if(pAＢegiｎ>pＡEnd){if(pBBegin>pBEnd)reｔurn0;elsereｔurnｐB(yǎng)Eｎｄ–pBBeｇiｎ+1;}if(pBBｅgin＞pBEnd){if(pABｅgin>ｐＡEnd)retuｒn0;ｅｌsereturｎpAEnd–pＡBｅgiｎ＋1；}iｆ(ｓtrA［ｐAＢ