課程內(nèi)容：

• 3個常見算法思想：指針思想、遞歸緩存和棧
• AST的形成算法
• 手寫AST及優(yōu)化

AST抽象語法樹：

1、本質上是個JS對象，作用是為了讓模板語法變成正常的HTML語法
2、用js來表現(xiàn)HTML結構的東西實際上就是AST（抽象語法樹）

虛擬節(jié)點和AST有什么關系？

1、vue底層（vue-loader)是在用字符串的視角來識別html標簽
2、整個流程如下：
模板語法 => AST抽象語法樹 => 渲染函數(shù)（h函數(shù)）=> 虛擬節(jié)點 => 經(jīng)過diff和patch => 渲染成界面

AST的實現(xiàn)函數(shù)parse函數(shù)

parse函數(shù)的主函數(shù)，實現(xiàn)輸入一個模板結構 轉換成包含dom信息的層級對象結構

parse函數(shù)的作用

算法儲備

1、指針思想

JS中的指針就是下標位置，指正就是偏移量，第一個數(shù)的偏移量是0

算法題一： 試圖尋找字符串當中連續(xù)重復次數(shù)最多的字符
let str = 'aaaaaaabbbbbbbccccccccccccccccccddddddddddddd'
// 定義指針
let i = 0
let j = 1
// 尋找最多的次數(shù)與字符
let maxRepeat = 0
let maxRepeatStr = ''
// 進入循環(huán) 
while (i <= str.length - 1) {
    if (str[i] !== str[j]) {
        // 與當前重復次數(shù)最多的進行比較 和賦值
        if (j - i > maxRepeat) {
            maxRepeat = j - i
            maxRepeatStr = str[i]
        }
        // 讓指針i 追上指針J
        i = j
    }
    j++
}
console.log(maxRepeatStr + '重復了' +maxRepeat +'次');

2、遞歸深入-菲波那契數(shù)列

// 算法題二：遞歸深入，試著輸出菲波那契數(shù)列的前十項 [1、1、2、3、5、8、13、21]

// 1. 簡單實現(xiàn)
// 創(chuàng)建一個函數(shù)，返回功能下標為N的這項的數(shù)字
function feb1(n) {
    console.count('觸發(fā)次數(shù)') // 觸發(fā)次數(shù): 99
    return n == 0 || n ==1 ? 1 : feb1(n-1) + feb1(n-2)
}

// 2. 利用緩存
// cache思想，利用緩存對象，解決大量重復計算的問題
let cache = {}
function feb2(n) {
    console.count('觸發(fā)次數(shù)') // 觸發(fā)次數(shù): 19
    if (n in cache) {
        return cache[n]
    }
    let val = n == 0 || n ==1 ? 1 : feb2(n-1) + feb2(n-2)
    cache[n] = val
    return val
}

// 測試
let n = 0
while (n <= 6) {
    console.log(feb2(n));
    n++
}

3、遞歸深入-高維數(shù)組

小技巧：只要出現(xiàn)了規(guī)則復現(xiàn)，就可以使用遞歸。tips：規(guī)則復現(xiàn)

// 算法題三：將高維數(shù)組 變成一個key:value 和 children：arr的數(shù)組對象

// 1. 循環(huán)實現(xiàn)
let myArr = [1, 2, 3, [4, 5, [6, 7, 8, [9, 10]]]]
function fn(arr) {
    let resultArr = []
    for (let i = 0; i < arr.length; i++) {
        if (typeof arr[i] == 'number') {
            resultArr.push({
                'value': arr[i]
            })
        } else if (Array.isArray(arr[i])) {
            resultArr.push({
                'children': fn(arr[i])
            })
        }
    }
    return resultArr
}
// console.log(fn(myArr));

// 2. 使用映射map實現(xiàn) item可能是數(shù)組也可能是數(shù)字
// 注意：寫法一的遞歸次數(shù)要大大小于寫法二
let myArr2 = [1, 2, 3, [4, 5, [6, 7, 8, [9, 10]]]]
function convert(item) {
    if (typeof item == 'number') {
        return {
            'value': item
        }
    } else if (Array.isArray(item)) {
        return {
            children: item.map(_item => convert(_item))
        }
    }
}
console.log(convert(myArr2));

4、棧

• 詞法分析的時候 需要經(jīng)常要用到棧這個結構，是非常著名的數(shù)據(jù)結構，可以輔助來解決算法題目
• JS中的棧，可以用數(shù)組模擬，只能使用push 和 pop 方法操作進棧和出棧。注意：棧是后進先出！

// 題目：smartRepeat函數(shù)
// 試編寫“智能重復” 實現(xiàn)：將3[abc]變?yōu)閍bcabcabc、將3[2[a]2[b]]變?yōu)閍abbaabbaabb