查找

链表

如何判断链表中是否有环
补：
1、链表有环不代表头节点就在环中，应该考虑只有后半部分出现环的情况。对于后者，使用单指针进行遍历以判断是否有环会导致死循环，因为不知道环的入口点，应该使用两个指针。
2、计算环的长度应该由第一次相遇时开始，第二次相遇时结束。不能从一开始就计算，因为如果进入环之前的长度远大于环长度的话，计算出来的长度是环长度的N倍。
3、计算入口点思路：分别从碰撞点、头指针开始一步一步走，相遇的那个点就是连接点。
注意点1：当slow入环时，fast肯定在其前面或相遇，而fast每次1步的速度接近slow，所以在slow走完一圈前，fast肯定能碰上slow。即：首次相遇时，slow还没走完链表。
注意点2：假设链表长度L，头节点到入口点长度A，入口点到相遇点长度B，环长度R，相遇之时slow走了S步。
相遇之时，fast走了2S步，且fast走的2S步等于slow走的S步加上fast绕的N次环，即2S=S+N*R，即S=N*R，slow走的S步等于环长度Rfast绕的N次环。
相遇之时，slow走的S步=头节点到入口点长度A+入口点到相遇点长度B。头节点到入口点长度A+入口点到相遇点长度B=`环长度Rfast绕的N次环=(N-1)R+R=(N-1)R+链表长度L-头节点到入口点长度A，头节点到入口点长度A=(N-1)*R+链表长度L-头节点到入口点长度A-入口点到相遇点长度B。这说明从头节点到入口点长度等于从相遇点到入口点长度加上N-1次环长度`。
4、判断两个链表（不带环）是否相交：将其中的一个链表首尾相连，然后判断另一个链表是否带环即可。

排列/组合

n*m矩阵求长方形
 字符串的全排列和组合算法
 排列组合中的不相邻问题
补：
关注其中的容斥原理和集合算法。

设计模式

C++实现线程安全的单例模式
 设计模式六大原则
补：
从类的角度出发：单一职责原则、最少知道原则、里氏替换原则。
从接口的角度出发：依赖倒置原则、接口隔离原则。
最终达到：开闭原则，即用抽象构建框架，用实现扩展细节。因为抽象灵活性好，适应性广，只要抽象的合理，可以基本保持软件架构的稳定。而软件中易变的细节，我们用从抽象派生的实现类来进行扩展，当软件需要发生变化时，我们只需要根据需求重新派生一个实现类来扩展就可以了。

图

判断无向图和有向图是否有回路

树

补：
二叉树二度节点和叶子节点的数量关系：
二叉树节点的度等于子树数目，只能是0、1、2。公式1：总节点数=叶子结点数+1度节点数+2度节点数。公式2：总度数=总节点数-1=1度节点数 + 2度节点数*2。可推出叶子节点个数=2度节点+1。
二叉树前序、中序、后序遍历非递归写法的透彻解析
补：
已知二叉树前序遍历和后序遍历如何求中序遍历？
TLR的第一个和LRT的最后一个一定是树根
TLR的第二个不是左子树的根就是右子树的根
如果TLR第二个与LRT的倒数第二个相同
则他是根的右子树
否则是根的左子树
将上面的方法递归
一步一图一代码，一定要让你真正彻底明白红黑树
 从B 树、B+ 树、B* 树谈到R 树
补：
一棵含有N个总关键字数的m阶的B树的最大高度是log_ceil(m/2)[(N+1)/2] + 1。(以ceil(m/2)为底)
m阶B树中每个结点含有子树满足：[ceil(m/2),m]，含有关键字满足[ceil(m/2)-1,m-1]。
红黑树-算法导论
补：
一棵有n个内结点的红黑树的高度至少为log(n)，至多为2lg(n+1)。
关于STL使用红黑树而不是AVL树的几点考虑:

1
2
3

1. 如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。  
2. 其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。  
3. map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。