一道算法题的分析过程

理解题目最近算法题比较多。希望用一个小问题记录下算法分析的过程。题目是：PigLatinPigLatiniisawayofalteringEnglishWords.Therulesareasfollows:Ifawordbeginswithaconsonant,takethefirstconsonantorconsonantcluster,moveittotheendoftheword,andadd“ay”toit.Ifawordbeginswithavowel,justadd“way”attheend.遇到这种描述比较少的题，第一反应就是题目描述越简单，隐藏条件就越多。不要慌，先看看维基百科对PigLatin的解释：PigLatin。看题目喜欢先看维基百科，了解题目的背景和出处，这样才能更好的理解题目，让解题更有趣。简单分析一下规则：单词以辅音开头时，将辅音移到末尾加ay如california→aliforniacay:c移到末尾再加ay段→aragraphspay:p移到末尾加ayglove→oveglay:gl移到末尾加上ay??这里是找出第一个元音前的所有辅音元音：a,e,i,o,u当单词以元音开头时，直接在单词后面加上way例如,algorithm→algorithmway:a是元音字母，所以在单词eight后面加way→eightway:e是元音字母，所以在单词后面加way。一：Shouldhandlewordswithoutvowels.translatePigLatin(“rhythm”)应该返回“rhythmay”。这条规则实际上满足了第一种情况。找不到元音时，后面直接加上ay解析过程。当我们拿到一道算法题时，按照几个套路来“围攻”1.算法分类，这道题是字符串题，对字符串的操作无外乎两种：a．根据索引遍历b。.2.由浅入深：根据给定的条件，暴力方向编写伪代码。b.根据逻辑找到关键的周期因素和优化方法。C。尝试优化伪代码并先编写伪代码。这部分代码比较粗糙，主要用来整理分析过程VARSTRVARvowelLetters=['a','e','i','o','u']//以元音开头IFSTR[0]invowelLettersreturnSTR+'way'//在STRIFSINvowelLetters中查找STR中的元音索引FOR(S,INDEX)returnSTR.slice(INDEX)+STR.slice(0,INDEX)+'ay'//单词中没有元音returnSTR+ay复制代码解析过程我们可以写JavaScript代码functiontranslatePigLatin(str){//准备需要的元音数组constvowelLetters=['a','e','i','o','u']//特殊情况：如果以元音开头if(vowelLetters.includes(str[0]))return`${str}way`//正常情况for(leti=0;i/[aeiou]/.test(s))if（index<0）return`${str}ay`if(index===0)return`${str}way`return`${str.slice(index)}${str.slice(0,index)}ay`}translatePigLatin("辅音");简化一点，逻辑更清晰。从分析过程来看，另一条路径已经通过循环遍历完成，那么另一条路径（replace）应该如何实现呢？从第一种方法的结果来看，需要使用Regular分组的方法来调换位置。这个想法是分成两组。第一组是从头到元音，第二组是从元音到末尾。然后这两组的顺序颠倒后，再加一个后缀。在开发调试正则表达式的时候，推荐regex101.com/调试正则表达式，使用调试器来完成这个正则表达式：/([^aeiou]*)(\w*)/用两个括号说明，分为两组([^aeiou]*)表示匹配0个或多个不是(^)aeiou的字符。(\w*)其余字符为一组补全码函数translatePigLatin(str){returnstr.replace(/([^aeiou]*)(\w*)/,'$2$1ay')}translatePigLatin("辅音");复制代码测试通过，👆上面的代码已经过了，除了元音在开头的情况没有覆盖，其他两种情况都包括在内。当元音在开头时，需要加的后缀为way，即([^aeiou]*)匹配不到的$1为空时，后缀变为ay。遵循这个想法，JavaScript字符串替换方法第二个参数是String.prototype.replace()支持函数-JavaScript|MDNfunctiontranslatePigLatin(str){returnstr.replace(/([^aeiou]*)(\w*)/,(_,p1,p2)=>`${p2}${p1||'w'}ay`)}translatePigLatin("辅音");复制代码进行归纳归纳。分类之后，基本就可以确定方向了。例如，大多数树问题都使用递归。如果要刻意训练递归，可以在树分组下训练。先分析题目的逻辑，先把逻辑的伪代码简单粗暴的写出来，再在优化上突破。回顾其他方向是否有更好的解决方案。最后给个小建议：如果想在短期内突破面试，就用Leetcode吧。另外推荐：https://www.codewars.com/。相比之下，codewars更注重当前编程语言的实际操作，而不是瞄准最优算法。这里面有很多“惊喜”。你会被许多“诡计|黑魔法”弄得不知所措。据传闻，codewars有更高的难度上限。