【41—Week03】学习总结

[mikejicken]

第三周总结
堆

1. 本身是一棵完全二叉树（除最后一层，其他层节点都是满的，最后一层如果只有一个节点，必须考左）
2. 一般用数组来存储，而且可以利用数组下标快速的方法定位父节点((i-1)/2)、左右子节点（l=2i*-1,r=2i*2）
3. 大顶堆，当前节点值，大于等于左右节点值。小顶堆，当前节点值，小于等于左右节点值。

字符串匹配

1. BF当然是最好理解，但是由于效率低。出现了RK算法。本质上是：RK利用哈希表，来提高字符串比较的效率。
2. BM/KMP,思路上主要也是，减少字符串比较的次数。有机会多滑动几位，就可以减少模式串和主串的比较次数。KMP的next数组还没看明白。