算法
背包问题
const knapsack = (weights:number[], values:number[], total:number) => {
var n = weights.length;
var f = new Array(n);
f[-1] = new Array(total+1).fill(0);
for(var i = 0 ; i < n ; i++){ //注意边界，没有等号
f[i] = new Array(total).fill(0);
for(var j=0; j<=total; j++){//注意边界，有等号
if( j < weights[i] ){ //注意边界， 没有等号
f[i][j] = f[i-1][j];
}else{
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 3
}
}
}
return f[n-1][total]
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
Vue 的流程梳理
template
template -> AST render （compiler解析template）将其转换成一些指令，directive
AST render -> vNode (render方法运行)将指令转换成虚拟 DOM，虚拟 DOM 是做的类似 DOM 节点的属性的一些方法，少了一些静态的方法来提升性能，比如 DOM 的一些方法
vNode -> DOM (vdom.patch) 将 VDOM 通过 insertBefore 插入到 DOM 中。
diff vNode 时会有一个重要的方法是 patch，这个方法会进行新老 vNode 对比，diff 的更新 dom，整个是只做同级比较，patchVnode 时无非就是逐个 vNode 及子节点(递归调用 patchVnode)进行对比有没有变化，并且逐一进行更新，但是为了最大复用子节点除了删除和新增操作，还会有移位操作，会存在头尾索引，对比头尾进行移位达到移位复用的效果。
当 DOM 被操作时，directive 会调用 watcher 中的 dep，找到对应变化的数据，对数据进行修改和重新绑定双绑事件
observer
在初始化 data/props 时，会调用 observe 方法对数据进行双绑，在双绑时会生成一个 watcher 实例就是 dep，这个 dep 实例中绑定了该数据变动后的回调，当想要获取双绑对象的数据时，会触发 getter，getter 中调用的 dep.depend() 处理好 watcher 的依赖计算返回当前数据的值，当发生 set 调用时，先会重新绑定新的数据，然后会调用 dep.notify()，进行 watcher 的 update 方法，update 方法实质上是会调用当前这个数据绑定的 watcher 对应的回调中对应的指令，生成对应性的 Vnode 的节点，再次进行 diff，更新 DOM 节点。
整体流程： 数据初始化 数据代理到 _data observe data walk 数据，对数据进行 defineReactive 实例化 dep get：dep.depend -> 收集视图的 watcher set：dep.notify -> 遍历数据进行修改 $mount 视图 template -> AST render AST render -> vNode vNode -> vDOM vDOM -> DOM 通过 watcher 进行 insertBefore，实现new watcher(vm, updateComponent) 首次实例化 watcher 将上面的 updateComponent 赋值给 this.getter，以便视图更新时调用 执行 this.get 收集当前 watcher 的依赖，用于返回当前值。并且调用 this.getter this.getter 被调用 -> updateComponent 被调用 -> _update(生成 VDOM) -> insertBefore DOM 至此完成首次渲染
数据变化更新： 重新对数据进行 observe dep.notify 遍历当前 dep 中的相关依赖，调用对应的 subs.update queueWatcher 将 watcher push 到异步队列中 最终调用 watcher.run -> 调用 this.get -> this.getter 被调用 -> updateComponent 被调用 -> _update -> patch diff -> patchNode(进行 DOM 的增删改操作) -> 递归 patchChildNode
vue 数组数据双绑，纯数组操作数组的下标 DOM 不会发生改变，DOM 双绑只对对象有效，但是用 push 等方法是可以的，是因为重写了数组的 push 等方法
nextTick 实现： 如果支持 promise，实现是 promise.then 实现是延迟到当前函数调用栈的最末端。 MutationObserver，监听 DOM 节点的变动 setTimeout 延迟器