[[384555]]

 理解題目

最近在看算法的問題比較多，希望能以一道小題，來記錄算法分析的過程。題目是: 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. 

 遇到這種描述比較少的題，第一反應(yīng)是題目描述越簡(jiǎn)單，隱藏條件就會(huì)多。不慌先看維基百科 對(duì)于 Pig Latin 的解釋： 豬拉丁 。我喜歡在看題目的時(shí)候，先看看維基百科，會(huì)了解下題目的背景和淵源，讓自己更好的理解題目的同時(shí)，讓解題也有些趣味性。簡(jiǎn)單解析下規(guī)則：當(dāng)一個(gè)單詞以輔音字母開頭，將輔音字母移到最后，并添加 ay 比如

• california → aliforniacay : c 移動(dòng)到最后然后添加 ay
• paragraphs → aragraphspay：p 移動(dòng)到最后然后添加 ay
• glove → oveglay：gl 移動(dòng)到最后然后添加 ay ⚠️ 這里是找到第一個(gè)元音字母之前的所有輔音字母

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

當(dāng)單詞以元音字母開頭的時(shí)候直接在單詞后面添加way 比如

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

題目分析完了，我們還需要通過閱讀測(cè)試用例來檢查是否有遺漏，看最后一條:

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

這個(gè)規(guī)則其實(shí)滿足第一種情況，當(dāng)找不到元音的時(shí)候，直接在后面加 ay

分析過程

當(dāng)我們拿到一道算法題目的時(shí)候，按照幾個(gè)套路來「攻城」

1.算法分類，這道題是字符串題，對(duì)于字符串的操作無非有兩種：

a.按索引遍歷

b.replace，replace 中尤其以正則不講武德。

2.由淺入深：

a.就是上來先根據(jù)給出的條件，按照暴力的方向去寫偽代碼

b.在根據(jù)邏輯找關(guān)鍵循環(huán)因子 和 優(yōu)化手段

c.嘗試優(yōu)化

偽代碼

先寫偽代碼，這部分代碼比較糙，主要用于整理分析過程

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 
復(fù)制代碼 

分析過程有了我們可以寫JavaScript代碼了

function translatePigLatin(str) { 
    // 先準(zhǔn)備需要的元音數(shù)組 
    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"); 
復(fù)制代碼 

Review 上面👆代碼，已經(jīng)可以通過測(cè)試了，那么分析如何優(yōu)化 。從代碼中分析到整個(gè)核心的邏輯就落在 ${str.slice(i)}${str.slice(0, i)}ay 那么關(guān)鍵點(diǎn)在于找到 第一個(gè)元音的索引那么我們改代碼

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"); 
復(fù)制代碼 

代碼簡(jiǎn)化一些，邏輯更清晰了

另一條路

從分析過程的路上來看，已經(jīng)用循環(huán)遍歷的方法完成了，那么另一條路(replace)應(yīng)該如何實(shí)現(xiàn)?第一種方法的結(jié)果來看，需要用到正則分組的方法來調(diào)換位置。思路是分兩組第一組是開頭到元音，第二組是元音到結(jié)尾。然后將這兩組順序調(diào)換后，添加后綴。在開發(fā)和調(diào)試正則的時(shí)候，推薦 regex101.com/ 來調(diào)試正則表達(dá)式

通過調(diào)試器來完成這個(gè)正則：/([^aeiou]*)(\w*)/ 解釋下

1. 用兩個(gè)括號(hào)，分成兩組
2. ([^aeiou]*) 表示匹配不是(^)aeiou 的0到多個(gè)字符。
3. (\w*) 剩下字符是一組

完成代碼

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

通過測(cè)試，👆上面的代碼已經(jīng)，除了元音在開頭的情況沒有覆蓋，其他兩種情況是包含的。元音在開頭的時(shí)候，需要加的后綴為way, 也就是當(dāng) ([^aeiou]*) 匹配的不到的 $1 為空的時(shí)，后綴變成 ay 順著這個(gè)思路完善，JavaScript 字符串 replace 方法第二個(gè)參數(shù)是支持函數(shù)的 String.prototype.replace() - JavaScript | MDN

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

總結(jié)

總結(jié)下 當(dāng)拿到一道算法題的基本套路是

1. 分類，是那一類的題，分完類后基本上能確定方向，比如樹的題大部分都要用到遞歸，如果你想刻意訓(xùn)練遞歸，可以在樹分組下訓(xùn)練。
2. 先分析題目邏輯，先用簡(jiǎn)單粗暴的方法把邏輯的偽代碼寫出來，然后再突破優(yōu)化。
3. Review 其他方向上是否有更優(yōu)解。

最后給個(gè)小建議：如果你是短期想突破面試，刷leetcode。同時(shí)推薦：https://www.codewars.com/，相比之下codewars 更注重當(dāng)前編程語言的實(shí)操，而不是以最優(yōu)算法為目的，里邊有很多「意外驚喜」。會(huì)被很多「奇技淫巧|黑暗魔法」所折服。據(jù)坊間流傳 codewars 的難度上限更高。