一道算法小题的分析过程

 理解题目

最近在看算法的道算问题比较多，希望能以一道小题，法小分析来记录算法分析的过程过程。题目是道算: Pig Latin

Pig Latin is a way of altering English Words. The rules are as follows: If a word begins with a consonant, take the first consonant or consonant cluster, move it to the end of the word, and add “ay” to it. If a word begins with a vowel, just add “way” at the end. 

 遇到这种描述比较少的题，第一反应是法小分析题目描述越简单，隐藏条件就会多。过程不慌先看维基百科 对于 Pig Latin 的道算解释： 猪拉丁 。我喜欢在看题目的法小分析时候，先看看维基百科，过程会了解下题目的道算背景和渊源，让自己更好的法小分析理解题目的同时，让解题也有些趣味性。过程简单解析下规则：当一个单词以辅音字母开头，道算将辅音字母移到最后，法小分析并添加 ay 比如

california → aliforniacay : c 移动到最后然后添加 ay paragraphs → aragraphspay：p 移动到最后然后添加 ay glove → oveglay：gl 移动到最后然后添加 ay ⚠️ 这里是过程找到第一个元音字母之前的所有辅音字母

元音字母： a、e、i、o、u

当单词以元音字母开头的时候直接在单词后面添加way 比如

algorithm → algorithmway : a 是元音字母所以在单词后添加 way eight → eightway : e 是元音字母所以在单词后添加 way

题目分析完了，服务器租用我们还需要通过阅读测试用例来检查是否有遗漏，看最后一条:

Should handle words without vowels. translatePigLatin(“rhythm”) should return “rhythmay”. 

这个规则其实满足第一种情况，当找不到元音的时候，直接在后面加 ay

分析过程

当我们拿到一道算法题目的时候，按照几个套路来「攻城」

1.算法分类，这道题是字符串题，对于字符串的操作无非有两种：

a.按索引遍历

b.replace，replace 中尤其以正则不讲武德。

2.由浅入深：

a.就是上来先根据给出的条件，按照暴力的方向去写伪代码

b.在根据逻辑找关键循环因子 和 优化手段

c.尝试优化

伪代码

先写伪代码，这部分代码比较糙，主要用于整理分析过程

VAR STR  VAR vowelLetters = [a,e,i,o,u] // 以元音开头 IF STR[0] in vowelLetters      return STR + way // 在STR中找到元音索引 FOR (S, INDEX) in STR      IF S IN vowelLetters          return STR.slice(INDEX) +  STR.slice(0,INDEX) + ay // 单词中没有元音      renturn STR + ay 复制代码 

分析过程有了我们可以写JavaScript代码了

function translatePigLatin(str) {      // 先准备需要的元音数组     const vowelLetters = [a,e,i,o,u]     // 特殊情况：如果以元音开头     if(vowelLetters.includes(str[0])) return `${ str}way`         // 正常情况     for (let i = 0; i < str.length; i++) {          if(vowelLetters.includes(str[i])) {              return `${ str.slice(i)}${ str.slice(0, i)}ay`         }     }     // 如果前面拦不住 说明没有元音     return `${ str}ay` } translatePigLatin("consonant"); 复制代码 

Review 上面👆代码，已经可以通过测试了，那么分析如何优化 。从代码中分析到整个核心的逻辑就落在 ${ str.slice(i)}${ str.slice(0, i)}ay 那么关键点在于找到 第一个元音的索引那么我们改代码

function translatePigLatin(str) {      // 直接找索引     let index = str.split().findIndex(s => /[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("consonant"); 复制代码 

代码简化一些，逻辑更清晰了

另一条路

从分析过程的路上来看，已经用循环遍历的方法完成了，那么另一条路(replace)应该如何实现?第一种方法的结果来看，需要用到正则分组的亿华云方法来调换位置。思路是分两组第一组是开头到元音，第二组是元音到结尾。然后将这两组顺序调换后，添加后缀。在开发和调试正则的时候，推荐 regex101.com/ 来调试正则表达式

通过调试器来完成这个正则：/([^aeiou]*)(\w*)/ 解释下

用两个括号，分成两组 ([^aeiou]*) 表示匹配不是(^)aeiou 的0到多个字符。 (\w*) 剩下字符是一组

完成代码

function translatePigLatin(str) {      return str.replace(/([^aeiou]*)(\w*)/, $2$1ay) } translatePigLatin("consonant"); 复制代码 

通过测试，👆上面的代码已经，除了元音在开头的情况没有覆盖，其他两种情况是包含的。元音在开头的时候，需要加的后缀为way, 也就是当 ([^aeiou]*) 匹配的不到的 $1 为空的时，后缀变成 ay 顺着这个思路完善，JavaScript 字符串 replace 方法第二个参数是高防服务器支持函数的 String.prototype.replace() - JavaScript | MDN

function translatePigLatin(str) {      return str.replace(/([^aeiou]*)(\w*)/, (_, p1, p2) => `${ p2}${ p1||w}ay`) } translatePigLatin("consonant"); 复制代码 

总结

总结下 当拿到一道算法题的基本套路是

分类，是那一类的题，分完类后基本上能确定方向，比如树的题大部分都要用到递归，如果你想刻意训练递归，可以在树分组下训练。 先分析题目逻辑，先用简单粗暴的方法把逻辑的伪代码写出来，然后再突破优化。 Review 其他方向上是否有更优解。

最后给个小建议：如果你是短期想突破面试，刷leetcode。同时推荐：https://www.codewars.com/，相比之下codewars 更注重当前编程语言的实操，而不是以最优算法为目的，里边有很多「意外惊喜」。会被很多「奇技淫巧|黑暗魔法」所折服。据坊间流传 codewars 的难度上限更高。

很赞哦!（93）