【每日算法Day 61】七月回顾总结

技术

七月不知不觉就过去了，完成了Spring框架的入门学习，并整合Spring MVC、MyBatis完整实现了一套管理系统的开发。另外，回顾了数据库相关的知识。但目前仍存在两点问题：1. 对SSM底层原理和细节理解还不够透彻，需要深入学习；2. 管理系统目前已不能满足互联网系统高并发的需要，如果可能还是要和Redis结合。

算法

按照cspiration的顺序完成了栈、优先队列（堆）、位操作、拓扑排序、位操作、图以及一些特殊数据结构（前缀树、并查集、红黑树、LRU缓存以及跳表）的学习，之后按照某人的算法小抄做重点问题。

• 栈：常用于DFS及回溯以及树的前中后序遍历，还可以用于处理括号匹配、逆波兰表达式，单调栈的使用场景也值得注意。
• 堆：最大堆堆的任意节点总是大于其孩子节点。每当插入一个新节点时我们把它放到数组最后的位置，并对其采用上浮操作。每当删除堆顶元素时，我们把堆顶元素和最后一个元素交换位置并对新的堆顶元素采取下沉操作。控制堆的容量为K，使用最小堆可以快速得到输入数据中第K大的元素（最大堆得到第K小的元素）。堆是一棵完全二叉树，可以用数组实现，核心操作是上浮和下沉。
• 位操作：一次异或可以实现信息的渗透，同一个元素异或两次就相当于没有操作。基础数据类型如整形、字符型都可以直接参与异或。此外某些场合下使用掩码可以用于快速比较。
• 拓扑排序：用于有向无环图，一般建立入度统计表和邻接表，结合队列处理入度为0的节点，元素出队列的顺序就是拓扑排序的结果。如果存在环则队列为空后一定有节点入度始终不为0。
• 随机：一般各编程语言都提供了生成伪随机数的函数。使用随机可以解决一类蓄水池抽样的等概率问题：对于第i个出现的元素，我们只需要以1/i的概率选择它就可以保证全部i个元素被选中的概率是相同的，这在不确定符合条件的目标的数量时就要做选择时非常有用。
• 字典树：前缀树，用于快速搜索单词是否存在，是否匹配前缀，也可以设计支持正则表达式，同时也很节约空间。
• 红黑树：是局部平衡的BST，任意节点子树的高度不会超过另一子树2倍。从任意节点到到其所有叶子节点的路径上的黑色节点数相同。插入时默认为红色，通过限制红色节点的孩子必须是黑色节点以及发现冲突时作出相应调整可以保持红黑树的局部平衡。
• LRU缓存：结合哈希和双向链表可以实现LRU缓存，设计的双向链表的节点除了指向前后的指针外还包含哈希表中应该有的key和value。我们在插入新节点（或访问已有节点）时，如果已经存在节点，则把该节点移动到双向链表的尾部（移除+添加到尾部），否则就创建新节点并在插入到链表的尾部的同时也要向哈希表中添加该元素。我们也可以继承LinkedHashMap并重写removeEldestEntry方法来实现LRU缓存。
• 并查集：并查集的核心是使用数组来表示森林，主要用来表示连通性关系。核心在于find方法中寻找根节点时的路径压缩和union方法中合并两棵树时按照根节点的秩（树的高度）来合并。
• 跳表：其本质是同时维护了多个分层的链表，近似实现了有序链表的二分查找。JDK中的ConcurrentSkipListMap底层就是跳表。在查找时从顶级链表开始查找，根据索引的范围转入下一层查找，整个过程是跳跃式的。在插入节点时要根据概率生成其层数，越高的层数生成概率越低。确定了层数x后，所有小于等于该层数的链表中都要建立该节点的索引。