课程内容：
- 3个常见算法思想：指针思想、递归缓存和栈
- AST的形成算法
- 手写AST及优化
AST抽象语法树：
1、本质上是个JS对象，作用是为了让模板语法变成正常的HTML语法
2、用js来表现HTML结构的东西实际上就是AST（抽象语法树）
虚拟节点和AST有什么关系？
1、vue底层（vue-loader)是在用字符串的视角来识别html标签
2、整个流程如下：
模板语法 => AST抽象语法树 => 渲染函数（h函数）=> 虚拟节点 => 经过diff和patch => 渲染成界面
AST的实现函数parse函数
parse函数的主函数，实现输入一个模板结构 转换成包含dom信息的层级对象结构
parse函数的作用
算法储备
1、指针思想
JS中的指针就是下标位置，指正就是偏移量，第一个数的偏移量是0
算法题一： 试图寻找字符串当中连续重复次数最多的字符
let str = 'aaaaaaabbbbbbbccccccccccccccccccddddddddddddd'
// 定义指针
let i = 0
let j = 1
// 寻找最多的次数与字符
let maxRepeat = 0
let maxRepeatStr = ''
// 进入循环
while (i <= str.length - 1) {
if (str[i] !== str[j]) {
// 与当前重复次数最多的进行比较 和赋值
if (j - i > maxRepeat) {
maxRepeat = j - i
maxRepeatStr = str[i]
}
// 让指针i 追上指针J
i = j
}
j++
}
console.log(maxRepeatStr + '重复了' +maxRepeat +'次');
2、递归深入-菲波那契数列
// 算法题二：递归深入，试着输出菲波那契数列的前十项 [1、1、2、3、5、8、13、21]
// 1. 简单实现
// 创建一个函数，返回功能下标为N的这项的数字
function feb1(n) {
console.count('触发次数') // 触发次数: 99
return n == 0 || n ==1 ? 1 : feb1(n-1) + feb1(n-2)
}
// 2. 利用缓存
// cache思想，利用缓存对象，解决大量重复计算的问题
let cache = {}
function feb2(n) {
console.count('触发次数') // 触发次数: 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、递归深入-高维数组
小技巧：只要出现了规则复现，就可以使用递归。tips：规则复现
// 算法题三：将高维数组 变成一个key:value 和 children：arr的数组对象
// 1. 循环实现
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实现 item可能是数组也可能是数字
// 注意：写法一的递归次数要大大小于写法二
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、栈
- 词法分析的时候 需要经常要用到栈这个结构，是非常著名的数据结构，可以辅助来解决算法题目
- JS中的栈，可以用数组模拟，只能使用push 和 pop 方法操作进栈和出栈。注意：栈是后进先出！
// 题目：smartRepeat函数
// 试编写“智能重复” 实现：将3[abc]变为abcabcabc、将3[2[a]2[b]]变为aabbaabbaabb
