求根号 #
-
牛顿迭代法（切线逼近）
$x_{n+1}=x_n-\frac{f(x_n)}{f’(x_n)}$
double Sqr(double k) { double x = k; // 当前迭代的x double y = 0.0; // 上一次的迭代结果 // 两次迭代的差值非常小时，便接近结果了 while (fabs(x - y) > 0.00001) { // 保存上一次迭代的结果 y = x; // 求解新的x x = (x * x + k) / (2 * x); } return x; } -
二分
double MySqrt(double n) { //此处一定为浮点数，不要用整数 double _max = n; double _min = 0.0; //此处为精度，当满足该精度时，返回该近似值 double p = 1e-5; double mid = (_max + _min) / 2.0; //此处是浮点数之差的绝对值与精度进行比较 while(fabs(mid * mid - n) > p) { if(mid * mid < n) _min = mid; else if(mid * mid > n) _max = mid; else return mid; mid = (_max + _min) / 2.0; } return mid; }
背包问题 #
01背包问题
每个物品选或不选
完全背包问题
每个物品选择次数无上限
多重背包问题
不同物品不同选择次数上限
混合背包问题
物品不同属性，混合背包下最大价值
二维费用的背包问题
体积+重量限制
分组背包问题
物品分为若干组，每组选一件
背包问题求方案数
求背包问题方案
有依赖的背包问题
排序 #
快速排序 #
时间复杂度 O(nlgn)
最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度 -1。这样，长度为n的数据表的快速排序需要经过 n 趟划分，使得整个排序算法的时间复杂度为 O(n^2^)。
堆排序 #
最坏、最好、平均时间复杂度均为 O(nlgn)
平衡树 #
红黑树 #
特性：
- 每个节点或者是黑色，或者是红色
- 根节点是黑色
- 每个叶子（NIL）节点是黑色（叶子节点指为空的叶子节点）
- 如果一个节点是红色的，则它的子节点必须是黑色的
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
左旋、右旋 #
AVL 树 #
任何节点的左右子树高度相差最多为 1
AVL 与 红黑树的区别 #
- 红黑树不是完全平衡，只要求部分达到平衡，用非严格的平衡来换取增删节点时旋转次数的降低，任何不平衡都会在三次旋转之内解决；而 AVL 是严格平衡树，因此在增加或者删除节点的时候，旋转次数可能要比红黑树要多。由于AVL高度平衡，因此AVL的Search效率更高一些。
- 就插入节点导致树失衡的情况，AVL 和 RB-Tree 都是最多两次树旋转来实现复衡 rebalance，旋转的量级是O(1) 删除节点导致失衡，AVL 需要维护从被删除节点到根节点 root 这条路径上所有节点的平衡，旋转的量级为 O(logN)，而 RB-Tree 最多只需要旋转 3 次实现复衡，只需 O(1)，所以说 RB-Tree 删除节点的 rebalance 的效率更高，开销更小
- AVL更平衡，结构上更加直观，时间效能针对读取而言稍高；维护稍慢，空间开销较大。 红黑树，读取略逊于 AVL，维护强于 AVL，空间开销与 AVL 类似，内容极多时略优于 AVL，维护优于 AVL。
总结：实际应用中，若搜索的次数远远大于插入和删除，那么选择 AVL，如果搜索，插入删除次数几乎差不多，应该选择 RB。
哈希 #
散列冲突 #
-
链接法
将同一槽位的元素放到链表中
处理简单，无堆积现象，平均查找时间较短，删除易实现
-
开放寻址法
删除元素比较困难，可以在删除的槽中置一个 delete 元素来标记
-
线性探测法
位置被占用时，依次往后查找，直到找到空闲位置为止
**缺点：**容易发生一次群集，群集现象越严重，平均查找时间越大，最坏情况时间复杂度 O(n)
-
二次探测法
$h(k,i)=(h^\prime(k)+c_1i+c_2i^2)\ mod\ m$
存在二次群集问题（两个关键字探查位置相同则探查序列也相同）
-
双重散列
$h(k,i)=(h_1(k)+ih_2(k))\ mod\ m$
$h_1$ 和 $h_2$ 均为辅助散列函数
$h_2$必须与m互素，可取m为2的幂，并设计总产生奇数的 $h_2$,或者取 m 为素数，设计总返回较 m 小的正整数的函数 $h_2$。 如$h_1(k)=k\ mod\ m$， $h_2(k)=1+(k\ mod\ m^\prime)$，$m^\prime$略小于$m$。
-
-
链表法
散列表 #
直接寻址表 #
每一个槽slot对应一个关键字为k的元，不存在具有相同关键字的元素
适用于关键字的全域较小的情况
DIRECT-ADDRESS-SEARCH(T,k) //查找
return T[k]
INSERT(T,x) //插入
T[x.key]=x
DELETE[T,x] //删除
T[x.key]=NIL
每一个操作都需要O(1)
散列表 #
关键字k的元素储存在槽h(k)中，h(k)为散列函数
以下两种方法解决槽位冲突
-
链接法 #
将同一槽位的元素放到链表中
CHAINED-HASH-INSERT(T,x) insert x at the head of list T[h(x.key)] SEARCH(T,x) search for an element with k in the list DELETE(T,x) delete x from the list装载因子：$\alpha$=n/m (n个元素，m个槽位)
$n\geqslant m$
简单均匀单列假设，不成功查找或成功查找都为 期望$\Theta$(1+$\alpha$)
散列函数： #
如果关键字不是自然数，找到一种方法将其转换为自然数
- **除法散列法** $$ h(k)=k \ mod\ m $$ 避免选择m的某些值，如2的幂 一个不太接近2的整数幂的素数 最好-
乘法散列法
- 关键字k乘常数A(o<A<1),取小数部分
- 乘m并向下取整
$$ h(k)=\llcorner\ m(kA\ mod\ 1)\ \lrcorner\ \ \ \ 即\ kA-\llcorner kA\lrcorner $$
一般选m为2的幂
-
全域散列法
-
-
开放寻址法 #
一个槽位对应一个元素
装载因子：$\alpha$=n/m (n个元素，m个槽位) $n\leqslant m$
假设均匀散列，一次不成功查找，期望探测数至多为1/(1-$\alpha$)
一次成功查找，期望探测书最多为$\frac{1}{\alpha}ln\frac{1}{1-\alpha}$
平均情况下，插入一个元素需要做$\frac{1}{1-\alpha}$次探测
insert
HARSH-INSERT(T,k) i=0 repeat j=h(k,i) if T[j]==NIL T[j]=k return j else i=i+1 until i==m error "hash table overflow"search
HARSH-SEARCH(T,k) i=0 repeat j=h(k,i) if T[j]==k return j ++i until T[j]=NIL or i==m return NIL删除元素比较困难（可以在删除的槽中置一个DELETE元素来标记该槽，此时insert需修改）
必须删除关键字时用链表法
-
线性探查 $$ h(k,i)=(h^\prime(k)+i)\ mod\ m $$ $h^\prime(k)$辅助散列函数
存在问题 一次群集，群集现象越严重，平均查找时间越大
-
二次探查 $$ h(k,i)=(h^\prime(k)+c_1i+c_2i^2)\ mod\ m~ $$ $c_1$和$c_2$都为正的辅助常数
存在问题 二次群集（两个关键字探查位置相同则探查序列也相同）
-
双重散列
最好方法之一 $$ h(k,i)=(h_1(k)+ih_2(k))\ mod\ m $$ $h_1$和$h_2$均为辅助散列函数
$h_2$必须与m互素，可取m为2的幂，并设计总产生奇数的$h_2$,或者取m为素数，设计总返回较m小的正整数的函数$h_2$。 如$h_1(k)=k\ mod\ m$，$h_2(k)=1+(k\ mod\ m^\prime)$，$m^\prime$略小于$m$。
-
完全散列
-