1、矩阵处理技巧
zigzag打印矩阵
转圈打印矩阵
原地旋转正方形矩阵
2、子数组问题
给定一个正数数组arr[]，一个参数sum，请返回数组中累加和等于sum的最长子数组
给定一个数组arr[]，数组中的数据有正有负有0，一个参数sum，请返回数组中累加和等于sum的最长子数组
给定一个数组arr[]，数组中的数据有正有负有0，一个参数sum，请返回数组中累加和小于等于sum的最长子数组
3、布隆过滤器
先了解什么是哈希函数:
1）输入参数data，假设是in类型，特征：可能无穷大，比如str类型的参数
2）输出参数类型out，特征：可能性可以很大，但一定是有穷尽的
3）哈希函数没有任何随机的机制，固定的输入一定是固定的输出
4）输入无穷多但输出值有限，所以不同输入也可能输出相同（哈希碰撞）
5）再相似的不同输入，得到的输出值，会几乎均匀的分布在out域上
布隆过滤器重要的三个公式：
1）假设数据量为n，预期失误率为p（布隆过滤器大小和每个样本的大小无关）
2）根据n和p，算出布隆过滤器一共需要多少个bit位，向上取整，记为m
3）根据m和n，算出布隆过滤器需要多少个哈希函数，向上取整，记为k
4）根据修正公式，算出真实的失误率p_true
m=-n*lnp/(ln2)^2
k=0.7*(m/n)
p_true=(1-e^(-nk/m))^k
怎么得到独立的k个哈希函数？
其实只需要两个即可，一个f()，一个g()
f()+1*g()
f()+2*g()
f()+3*g()
…
f()+k*g()
4、岛问题
一个只有0和1两种数字的二维矩阵中，上下左右能连成一片的1，就算一个岛。给定一个矩阵，返回矩阵中共有几个岛？
5、有序表
平衡搜索二叉树实现
SB树实现（SB树，任何一个叔节点拥有的节点数，不少于任何一个侄节点）
跳表
红黑树
1）每一个节点不是红就是黑
2）头节点和叶节点是黑
3）红节点的子一定不是红
4）从任何一个节点到它的每一个子，所有路径上黑节点数量一样多
不同于AVL树和SB树只有4中非平衡情况：LR/RL违规，让孙节点来到顶层即可（旋转两次）；LL/RR违规，子节点来到顶层即可（旋转一次）。红黑树足足共有13种违规的情况，插入5种，删除8种…..发明人殚精竭虑全部弄完以后来荼毒后人，哎…..
给定一个数组arr，两个整数a和b(a<=b)，求arr中有多少个子数组，累加和在[a,b]这个范围上，返回达标的子数组数量
6、AC自动机
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/111921.html
