2023年程序员编程艺术第二十八二十九章最大连续乘积子串字符串编辑距离

程序员编程艺术第二十八~二十九章:最大连续乘积子串、字符串编辑距离第二十八～二十九章：最大连续乘积子串、字符串编辑距离前言时间转瞬即逝,一转眼,又有4个多月没来更新blog了,过去4个月都在干啥呢?对的，今２0２3年元旦和朋友一起搭了个方便朋友们找工作的编程面试算法论坛:为学论坛。最近则在负责一款在线编程挑战平台-－英雄会的产品运营，当然拉，虽说是产品运营，事实上身兼“数职”:出题审题，写代码测试一个不落下。最近跟百度的几个朋友线下闲聊，听他们说,百度校招群内的不少朋友在找工作的时候都看过我的blog，一听当即便激起了自己重写更新此blog的欲望,恰巧眼下阳春三月（虽说已是3月，奇妙的是，前两天北京还下了一场大雪),又到了找工作的季节(相对于每年的９月份来说,3月则是一个小高潮）,那就从继续更新专为找工作准备笔试面试的程序员编程艺术开始吧。本文讲两个问题,第二十八章、最大连续乘积子串,第二十九章、字符串编辑距离,这两个问题皆是各大IT公司最喜欢出的笔试面试题,比如说前者是小米２023年校招笔试原题,而后者则更是反复出现,如去年9月２6日百度一二面试题，1０月9日腾讯面试题第1小题,１0月13日百度2０23校招北京站笔试题第二大道题第３小题，及去年10月１5日２０23年Google校招笔试最后一道大题。OK，欢迎朋友们在本文下参与讨论,假如用Jａva/C#的朋友想在线编译自己的代码，可以上英雄会提交你的代码,有任何问题，欢迎随时不吝批评或指正，感谢。第二十九章、最大连续乘积子串题目描述:给一个浮点数序列,取最大乘积连续子串的值，例如-2.５,4，0,３,０.5,8,-1,则取出的最大乘积连续子串为3,0.5，8。也就是说,上述数组中，3０.５８这3个数的乘积3＊0．５*８＝1２是最大的，并且是连续的。提醒：此最大乘积连续子串与最大乘积子序列不同,请勿混淆，前者子串规定连续,后者子序列不规定连续。也就是说:最长公共子串(ＬongestCommｏｎSubｓtrinｇ）和最长公共子序列（LongeｓtCommonSｕｂseｑuｅnｃe，ＬCＳ)的区别:子串(Suｂstrｉｎg)是串的一个连续的部分，子序列（Suｂsequeｎce）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；更简略地说,前者(子串）的字符的位置必须连续，后者（子序列LCＳ）则不必。比如字符串acdｆg同ａkdｆc的最长公共子串为dｆ，而他们的最长公共子序列是aｄf。LCS可以使用动态规划法解决。解答:解法一、两个for循环直接轮询或许,读者初看此题,自然会想到最大乘积子序列问题类似于最大子数组和问题：,最简朴粗暴的方式便是用链两个fｏr循环直接轮询。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];}｝解法二、虽说类似于最大子数组和问题，可以用两个fｏr循环直接轮询搞定,但事实上具体解决起来诸多不同,为什么呢，由于乘积子序列中有正有负也还也许有0。我们可以把问题简化成这样:数组中找一个子序列,使得它的乘积最大；同时找一个子序列，使得它的乘积最小(负数的情况）。由于虽然我们只要一个最大积,但由于负数的存在,我们同时找这两个乘积做起来反而方便。也就是说，不仅记录最大乘积,也要记录最小乘积。So，我们让mａxＣｕrrent表达当前最大乘积的candidatｅ,minCurrｅｎt反之,表达当前最小乘积的candiｄaｔe(用candidａtｅ这个词是由于只是也许成为新一轮的最大／最小乘积），而maxProduct则记录到目前为止所有最大乘积candidａtes的最大值。由于空集的乘积定义为1,在搜索数组前,maxCurｒent,minCurｒeｎt，ｍａxProdｕｃt都赋为1。假设在任何时刻你已有了maxCurrenｔ和ｍｉnＣurｒｅｎt这两个最大／最小乘积的candidates,新读入数组的元素x（ｉ)后,新的最大乘积ｃanｄidaｔｅ只也许是maxCｕｒreｎt或者mｉnCuｒreｎｔ与ｘ(i)的乘积中的较大者,假如ｘ(ｉ)<0导致maxCuｒrent<ｍinCｕｒrｅnｔ，需要互换这两个candiｄａtes的值。当任何时候maxCuｒrｅnt<1,由于1（空集)是比ｍaxCｕrrenｔ更好的cａndidatｅ，所以更新maxCurｒeｎt为１，类似的可以更新minＣurrｅnｔ。任何时候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ｔ;}解法三、本题除了上述类似最大子数组和的解法,也可以直接用动态规划求解(其实，上述的解法一本质上也是动态规划，只是解题所表现出来的具体形式与接下来的解法二不同罢了。这个不同就在于下面的解法二会写出动态规划问题中经典常见的状态转移方程，而解法一是直接求解)。具体解法如下：假设数组为a［]，直接运用动归来求解,考虑到也许存在负数的情况,我们用Maｘ来表达以ａ结尾的最大连续子串的乘积值，用Min表达以a结尾的最小的子串的乘积值，那么状态转移方程为：Maｘ=max{a，Ｍaｘ[i-1]*a，Min[i-１]＊a}；Miｎ＝mｉn{a，Mａｘ[i－１]＊a,Min[i-１]*a};初始状态为Max[1]＝Min[1]＝a[１]。代码如下：/*给定一个整数数组,有正有负数，0，正数组成,数组下标从１算起求最大连续子序列乘积,并输出这个序列,假如最大子序列乘积为负数,那么就输出-1用Ｍax[i]表达以a［i]结尾乘积最大的连续子序列用Min[i]表达以a[i］结尾乘积最小的连续子序列由于有复数，所以保存这个是必须的*/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)；//内存释放deｌetｅ[]Max;ｄelete[]Min；}提炼简化下上面的核心代码为：ｄ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[０］＝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;}变种此外,此题尚有此外的一个变种形式,即给定一个长度为Ｎ的整数数组，只允许用乘法,不能用除法，计算任意(N－１）个数的组合中乘积最大的一组,并写出算法的时间复杂度。我们可以把所有也许的（N-1）个数的组合找出来,分别计算它们的乘积,并比较大小。由于总共有N个(Ｎ-1)个数的组合,总的时间复杂度为Ｏ(N2）,显然这不是最佳的解法。OK，以下解答来自编程之美解法1解法2此外,还可以通过度析，进一步减少解答问题的计算量。假设N个整数的乘积为Ｐ，针对P的正负性进行如下分析（其中，AN-1表达N-１个数的组合,ＰＮ-1表达Ｎ-1个数的组合的乘积）。1.P为0那么，数组中至少包具有一个０。假设除去一个0之外,其他N-１个数的乘积为Q,根据Q的正负性进行讨论:Ｑ为０说明数组中至少有两个０,那么Ｎ-1个数的乘积只能为０，返回0;Q为正数返回Q，由于假如以０替换此时ＡN－１中的任一个数,所得到的ＰＮ-1为0，必然小于Q；Q为负数假如以０替换此时AN－1中的任一个数，所得到的PN-1为0,大于Ｑ，乘积最大值为0。２.P为负数根据“负负得正”的乘法性质，自然想到从N个整数中去掉一个负数，使得PN-1为一个正数。而要使这个正数最大，这个被去掉的负数的绝对值必须是数组中最小的。我们只需要扫描一遍数组,把绝对值最小的负数给去掉就可以了。3.P为正数类似地,假如数组中存在正数值，那么应当去掉最小的正数值,否则去掉绝对值最大的负数值。上面的解法采用了直接求Ｎ个整数的乘积P，进而判断P的正负性的办法,但是直接求乘积在编译环境下往往会有溢出的危险(这也就是本题规定不使用除法的潜在用意），事实上可做一个小的转变，不需要直接求乘积,而是求出数组中正数（+）、负数(-）和0的个数,从而判断Ｐ的正负性,其余部分与以上面的解法相同。在时间复杂度方面，由于只需要遍历数组一次，在遍历数组的同时就可得到数组中正数（+）、负数（-)和0的个数，以及数组中绝对值最小的正数和负数,时间复杂度为O（N）。第二十九章、字符串编辑距离题目描述：给定一个源串和目的串,可以对源串进行如下操作:１.在给定位置上插入一个字符２.替换任意字符3.删除任意字符写一个程序，返回最小操作数，使得对源串进行这些操作后等于目的串，源串和目的串的长度都小于２０2３。提醒：上文前言中已经说过了,此题反复出现,最近考的最多的是百度和Gooｇle的笔试面试经常考察。下图则是2０2３年Gｏoｇｌｅ的校招试题原景重现:解答：解法一、此题跟上面的最大连续乘积子串类似,常见的思绪是动态规划,下面是简朴的ＤP状态方程：／/动态规划:／/f[i,j］表达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)}/／分别表达：添加1个,删除1个,替换１个(相同就不用替换）。解法二、类似上述问题类似于编程之美上的下述一题「以下内容摘自编程之美第3．３节」:许多程序会大量使用字符串。对于不同的字符串,我们希望可以有办法判断其相似限度。我们定义了一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为:修改一个字符(如把“a”替换为“b”）;增长一个字符（如把“aｂｄd”变为“aebdd”）;删除一个字符(如把“ｔravelliｎg”变为“ｔｒａｖeliｎg”）。比如,对于“aｂcdefｇ”和“ａbcdｅf”两个字符串来说,我们认为可以通过增长/减少一个“g”的方式来达成目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。也就是说，“abｃｄeｆg”和“abｃｄeｆ”的距离为1,相似度为１/2=０．5。给定任意两个字符串,你是否能写出一个算法来计算出它们的相似度呢?这样,不久就可以完毕一个递归程序，如下所示: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ｐBEｎｄ–pBBeｇiｎ+1;}if(pBBｅgin＞pBEnd){if(pABｅgin>ｐＡEnd)retuｒn0;ｅｌsereturｎpAEnd–pＡBｅgiｎ＋1；}iｆ(ｓtrA［ｐAＢ