搜索
ProblemStatement:如果一个数字十进制表达时，不存在连续两位数字相等，则称之为“不重复数”。例如，105，1234和12121都是“不重复数”，而11，100和1225不算。给定一个long类型数字A，返回大于A的最小“不重复数”。Definition:Class:UnrepeatingNumbersMethod:nextParameters:longReturns:longMethodsignature:longnext(longA)(besureyourmethodispublic)Constraints:A取值范围是[0，10^17]，注意是闭区间。Examples:0)54returns：56大于54的最小数字是55，但55不是“不重复数”。下一个数字是56，它满足条件。1)10returns：122)9returns：103)98returns：10199和100都不是“不重复数”，101是。4)21099returns：21201解题报告:ThefirstsolutionthatonecouldthinkofistojustincreaseAuntilitbecomesaunrepeatingnumber.Verifyingthatanumberisunrepeatingrequirestodecomposeitintoalistofdigits,whichisasimpletask.Unfortunately,theconstraintsfortheproblemsaidthatAcanbeaslargeas10^17,wecannoticethatwithavalueofAequalto1and17zeros,ouralgorithmwouldtakealotoftimebeforethetwomostsignificantrepeateddigitsaredealtwith.However,theobservationaboutspendingtoomuchtimebeforedealingwithsignificantrepeateddigitscanbehelpful.Agoodideatooptimizethepreviousalgorithmwouldbetosimplyincreasethedigitsthatweneedtoincrease.Insteadofincreasingthewholenumberuntiltherepetitionishandledcorrectly.Thisisactuallyanideagoodenoughtosolvetheproblem.Unfortunatelyalotofcodersdidn'tconsiderspecialcaseswhenimplementingitwhichcausedplentyoffailedsolutions.Thiswasmostlyduetotheexamplesallhavingtherepeatednumbersintheleastsignificantdigits,whichmadeitchallengingtoanalyzetheproblemcorrectly.Let'sanalyzeagoodcaseinordertodesignanalgorithm,A=122055123,sincetheresultmustbegreaterthanA,wewillbeginwith122055124:Wefindafirstpairofrepeateddigits22,thenumberneedstobechangedwithinthesecond'2',wemightincreasetheleftsideofthenumberandleavetheothersideintact.Isthisagoodresult?Itprobablyisn't.Althoughwehavedealtwiththepairof'2's,therightsideofthenumbercouldactuallybesmaller(weneedtofindthesmallestunrepeatingnumbergreaterthanA).Somequickanalysiscouldshowthattheminimum9digitsunrepeatingnumberbeginningwith123wouldbe:123010101,althoughwecouldbaseoursolutiononaddingthisrepeating01..patterntotherightsideofthenumber,itisnotconvenientaswewillhavetodealwithspecialcases.(I.e:pairsof99mayaddnewrepeatingpairsinmoresignificantdigitpositions)Nothandlingthesespecialcasescorrectlycausedmanysolutionstofail.Amoreconvenientsolutionwouldbetoreplacetherightsideofthenumberwithzeros,andjustrepeatthisprocessgoingfromthemostsignificantdigittotheleastsignificantdigituntilthenumberbecomesunrepeating:AbignumbersclassorstringmanipulationwouldbehelpfulinImplementingthisalgorithmbutwasnotnecessary,itwaspossibletoimplementitusingarithmeticandpowersof10tohandlethedigits:longgetNext(longA){A++;booldone=true;do{longd=1;while(d*10A)//findthehigestpowerof10d*=10;//thatissmallerthanAdone=true;while(d1){//iteratevalidpowersof10fromhighesttolowest(10)longnd=d/10;if((A/d)%10==(A/nd)%10){//comparethedigitsatthesetwoconsecutivepositionsA/=nd;//incrementtheleftsideA++;A*=nd;//replacetherightsidewithzeros.done=false;}d=nd;}}while(!done);returnx;}题目:UnrepeatingNunbers(350points)ProblemStatement:“回文分数”游戏并不简单，游戏目标是修改最多maxChanges个字符使得一个字符串的回文分数最高。只允许修改，不许增加或者删除字符。一个字符串的回文分数定义如下：-如果字符串不是回文串，则分数为0。-如果字符串是回文串，且长度为奇数，则分数为1。-如果字符串是回文串，且长度为偶数，设它的一半子串的回文分数为K（两个一半子串得分一定相同），则分数为K+1。给定一个字符串word和一个int型数maxChanges，返回最多修改maxChanges个字符后最大可能的回文分数。Definition:Class:MaximumPalindromeScoreMethod:maximizeParameters:String,intReturns:intMethodsignature:intmaximize(Stringword,intmaxChanges)(besureyourmethodispublic)Notes回文串的定义是一个字符串从前向后读和从后向前读完全一样。Constraints-word包含1到50个字符。-word只包含小写字母('a'-'z')。-maxChanges取值范围是[0，50]，闭区间。Examples0)coder2returns：1把c改成r，把e改成o，得到“rodor”，这是一个奇数长度的回文串，所以得分为1。1)abcbxabcba1returns：2把x改成a，得到“abcbaabcba”，偶数长度，它的一半子串是“abcba”，该子串是一个奇数长度的回文串，所以子串分数为1，因而最后得分是2。2)abcdefghijklmnop15returns：5可以把这个字符串修改成“aaaaaaaaaaaaaaaa”，“eeeeeeeeeeeeeeee”等串，回文得分为5。3)ssssssssssssssss15returns：5无需做改变。4)vyyvvzzvvxxvvxxv4returns：35)a0returns：1解题报告:Afirstusefulobservationistonoticethatthepalindromescoreofawordcannotbecometoohigh,infact,themaximumscoreawordoflengthncouldhaveislog2(n).Thismeansthatevenforn=64,themaximumscorepossibleis6.ItwouldbepossibletomakeafunctionisPossible(word,S,maxChanges)thatverifiesapalindromescoreSispossibleforacertainwordaftermaxChangescharacterchanges.Thisalgorithmcanhelpussolvetheproblem,wecaniterateforallpossiblevaluesofSfromlargeronesto0.OncewefindavalueofSthatispossible,returnitsinceitisthemaximumpalindromescoreforthatcase.TheproblemisreducedtohowtocodetheisPossible()function.AwaytosolvethissubproblemistofirstcalculatetheminimumnumberofcharactersinthewordthathavetobemodifiedforthewordtohaveapalindromescoreofS.ForawordtohaveacertainscoreS,itneedscertaincharactersinspecificindexestobeequal.Let'sfirstverifythecaseforwhichS=1,inthiscase,wesimplyrequirethewordtobeapalindrome.Thismeansthatthecharactersinthefirsthalfofthewordmustbeequaltotheoppositecharactersinsecondhalfoftheword.Ifoneofthesepairsofcharacterscontainstwodifferentones,thenatleastoneofthemmustbemodified.Intheaboveexample,tothe'a'charactersdonotneedtobemodified,but'b'or'd'havetobechanged.Since'c'doesnothaveapairwedonotneedtochangeiteither.Largerva