算法学习

请设置文章作者

发布于：Nov 26, 2019

排序

冒泡排序

比较大小,如果符合条件(升序)就交换两个元素的位置
- 每次执行N-1次
- 严格大/小,保证了原序(稳定性)
- 没次能保证最大/最小的元素会在最后
如果全程无交换,则说明有序了,跳出即可
$T=O(x),x\in(N,N^2)$

插入排序

每次无序列首抽取一个元素,然后从有序列末尾开始进行比较(省空间)
查找插入位置，若符合条件,往后移位
然后插入元素

|----------------------|
|有序    |R| 无序      |
|----------------------|

将待插元素R 插入有序列中
有序列后移

// 从小到大序列
for(i=2;i<=n;i++){
    ar[0] = ar[i];   // 哨兵：保存待插入元素R
    for(j=i-1;j>=0&&ar[0]<ar[j];j--){  // 有序列后移腾空间
        ar[j+1] = ar[j];
    }
    ar[j+1] = ar[0];
}

优化：用二分法查找待插入元素的位置

希尔排序

对插入排序的改进,每次消除多个逆序对以达到加速的效果

按照一定增量序列,每次进行D排序 $D_N > D_{N-1}…>D_1$ ,这样一来一趟就有可能消除多个逆序对
- 按照$D_N > D_{N-1}…>D_1$进行排序,后一次会保持前一次的顺序,故可用
- 但最终都要进行1排序

for(D=N/2;D>0;D/=2){  // 希尔增量序列。Hibbard增量序列:Dk=2^k-1...等等
    for(p=D;p<N;p++){  // 插入排序
        Tmp = A[p];
        for(i=p;i>=D&&A[i-D]>Tmp;i-=D){
            A[i] = A[i-D];
        }
        A[i] = Tmp;
    }
}

堆排序

heap本质是一段连续的地址空间，堆排序则在连续空间的基础上加入完全二叉树的结构。即

Rn < R2n
Rn < R2n+1
或
Rn > R2n
Rn > R2n+1

即子节点比父节点小/大的二叉树叫做小/大顶堆，有时也称为最小堆/最大堆。

每次需要最大/小值时，将堆顶和堆尾(即地址为0和地址末尾)的元素交换，那么最大/小元素就在堆尾，取出，然后调整剩下部分再次满足小/大顶堆。交换后从末尾取出原因是可以不破坏原始树的结构，即仍然可以通过2n 2n+1等访问子节点

堆排序的主要问题有两个，一是初始化构建，二是取出后调整。

调整方法

调整也是一个上浮下沉的过程，以大顶堆为例，取出最大值后，较小值换到了根节点，使得大顶堆结构破坏。

1. 从导致结构破坏的根节点出发
1. 选取其孩子中的最大值，与根节点交换
1. 此时导致结构破坏的根节点来到了子树，又以子树开始重复步骤1

void HeapAdjust(HeapType &H, int s, int m){
    // 将堆s到m范围内调整成大顶堆
    RedType rc;
    rc = H.r[s];   // 寄存起来减少写入次数，H类是r用来储存堆
    for(j=2*s; j<=m; j*=2){
        if(j<m && H.r[j].key<H.r[j+1].key) j++; // j为key较大的下标
        if(rc.key >= H.r[j].key) break;  // 如果已经根节点已经较大，符合最大堆，则跳出
        H.r[s] = H.r[j];
        s = j;  // 从子树再次开始调整
    }
    H.r[s] = rc;  // rc应插入在位置s上
}

初始化构建方法

法一：利用上面的调整函数，有(大顶堆为例)

void HeapSort(HeapType &H){
    RedType temp;
    for(i=H.length/2; i>0; --i){    // 从底(叶子节点的父节点)向上，把1到H.length范围构建成大顶堆
        HeapAdjust(H, i, H.length);
    }
    // (UNUSED  TODO看书)
    // for(i=H.length; i>1; --i){
    //     temp = H.r[i];
    //     H.r[i] = H.r[1];
    //     H.r[1] = temp;
    //     HeapAdjust(H, 1, i-1);
    // }
}

法二：上浮下沉法(小顶堆为例)

// 从第一个非叶子节点开始，以它为子树，先自下而上把小的节点上浮，到达子树根节点后自上而下把大的节点下沉
// 知道根节点结束
void createHeap(int *heap,int len){
    for(int j=len/2-1;j>=0;j--){
        int t = j;
        while((t+1)*2<=len){
            int min = (t+1)*2-1;
            if(min+1<len){
                if(heap[min+1]<heap[min]){
                    min++; 
                }
            }
            if(heap[min]<heap[t]){
                swop(min,t,heap);
                t = min;
            }else{
                break;
            }
        }
    }
}

法三：插入法

// 从根节点出发，若父节点比插入元素大，则调整位置，如此循环，保证父节点小于子节点
void createHeap(int *heap,int len){
    heap[0] = -1000;
    int temp;
    for(int i=1;i<=len;i++){
        scanf("%d",&temp);
        int j;
        for(j=i;heap[j/2]>temp;j/=2){
            heap[j] = heap[j/2];
        }
        heap[j] = temp;
    }
}

利用小/大顶堆排序

根据小/大顶堆的性质，可以确定顶部一定是最大或最小的元素
交换根节点和最后一个节点，那么最后一个节点一定是最大/最小
把最后的节点排除，剩下节点构成的子树再调整成小/大顶堆，重复以上步骤

快速排序算法

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

先从数列中取出一个数作为主元
- 主元选不好会影响速度
- 法1.选头,中,尾三个数的中位数做主元
分区过程，交替移动，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
再对左右区间重复第二步，直到各区间只有一个数

void quicksort(int *ar,int l,int r){
    int num = ar[l];   /* 做寄存，减少写入读出的次数 */
    int left = l,right = r;
    if(l<r){
        while(r>l){
            while(l<r&&ar[r]>num){
                r--;
            }
            ar[l] = ar[r];
            while(l<r&&ar[l]<=num){
                l++;
            }
            ar[r] = ar[l];
        }
        ar[l] = num;
        quicksort(ar,left,l-1);
        quicksort(ar,l+1,right);
    }
}

注意若选取的比较位是序列的首位或尾位，则当序列有序时使用快速排序，时间复杂度退化为$O(n^2)$。优化 :取首位、中位、尾位的中位数作为比较位。

擂台法

适用于找最值

归并法

把两个有序的序列合并
法1.递归的进行下去(有点类似快速排序)
法2.每个元素看成一段序列,合并合并…
$T=N\log{N}$
缺点:需要开额外一份空间

拓扑排序

AOV(activity on vertex)

节点代表事件，若v到w连通,则v一定在w的前面

有向图
有优先级限制

按照此法输出就是拓扑排序

Queuezero Q;   // 储存入度为零的,即前头没有限制了的

for(i=0;i<|V|;i++){    // 记录最先的入度为0的节点
    if(indegree[V]==0){
        Enqueue(V,Q);
    }
}
while(!isEmpty(Q)){
    V = Dequeue(Q);  //cnt++,记录或者输出什么的(拓扑排序)
    for(V的每个邻接点W){
        indegree(W)--;
        if(degree(w)==0){
            Enqueue(W,Q);
        }
    }
}
if(cnt!=|V|)
    图有回路,无法拓扑排序

AOE(activity on edge)

用边表示活动的带权无环网络；顶点表示事件，它之前的活动已经完成，它之后的活动才能开始。

应用
- 解决关键路径问题
- 推算工程需要的时间

关键路径

完成工程所需的时间取决于开始到结束的最长路径。因此要节省时间就要减小最长路径，这个最长路径就是 关键路径 ，关键路径上的活动就是 关键活动。

事件Vj的最早发生时间Ve(j)
- 顶点表示事件，V0到Vj的最长路径
事件Vj的最迟发生时间Vl(j)
- 保证终点在最早发生时间完成的前提下，表示能拖延多久
- 即从终止时间-终点倒推到j点的最长路径(时间)
活动Ai最早开始时间e(i)
- 边表示获得，即边起点最早开始时间Ve(j)
活动Ai最晚开始时间l(i)
- 在不引起延误的前提下，最迟开始时间
- 即边的权值(活动持续时间dur)因此可以变动
- l(i) = Vl(k)-dur
时间余量
- l(i)-e(i)

求解关键路径问题的步骤

1. 从起点开始找最早开始时间Ve(j)
1. 从终点倒推，求最晚开始时间Vl(j)
1. 此时得到活动的两点(即边的两点)，找出e(i)==l(i)，即时间余量为0的活动即为关键活动

    2    3    1
 a -- b -- d -- f
       \1      /1
        c -- e
           1

| event | a | b | c | d | e | f |
|-------|---|---|---|---|---|---|
| Ve    | 0 | 2 | 3 | 5 | 4 | 6 |
| Vl    | 0 | 2 | 4 | 5 | 5 | 6 |

表排序

当移动的成本很高时(如移动一部电影)就用表来储存他的顺序

table[N]指向N,故用table[N]进行访问\排序

桶排序

基本原理:假如有10个数分别是0~~9让你排序,那建立10个桶ar[10],根据情况0~~9放到对应的桶了,最后顺序输出桶就是有序的了

LSD(Least Significant Digit)次位优先

排10个在0~999的整数难道要建1000个桶吗？

根据低位到高位建通(实际情况肯更抽象)
- 这里是从个位到百位,没位置建10桶
- 个位桶建装好后再遍历桶,装十位的桶,以此类推
- 因为是遍历有序桶来填入新桶的,所以最后的桶只需按顺序输出就是有序了

BFPRT算法：求无序数组低k小/大的数

思路类似于partition快速排序，下标就能说明范围是第几，小于放左边大于放右边，然后范围只需要关注左边或者右边。

但是如果是简单的基于快速排序，随机选一个划分值，复杂度的变数就比较大，即如果每次选中的划分值都是最小或最大，那么剩下还得关注len-1的数。效率不高。

bfprt(vector<int> arr, int kf)
- 1. 整个数组先分组
    - BFPRT发明者是5个人，所以一般5个一组，不足5个就是单独一组
- 1. 每个小组中排序
- 1. 取出每个组的中位数，构成一个新的组，偶数个就取上中数或下中数，得到一个N/5长度的新数组
- 1. 递归调用num = bfprt(arr, k)拿到中位数，把上面得到的数组和new_arr.size()/2传入
- 1. 用上一步拿到的中位数进行划分

查找

散列(hash)查找

把关键词看成变量,通过哈希函数运算赋予地址

插入

关键词是数字时的常见方法

折叠法
平方取中法
数字分析法
除留余数法

关键词是字符时的常见方法

位移法(变成整数移位<<求余)

核心思想就是当一位改变时尽可能多的影响位数,避免浪费

处理冲突

产生冲突就添加偏移量到别的位置

线性探测
- 偏移量是一增量序列: 1.2.3.4…
- 容易产生聚集
平方探测
- 偏移量是一增量序列: 1^2.2^2.3^2.4^2…
- 容易产生死循环
  - 定理:散列表长是某个4k+3的素数时,一定能探测整个表
双散列探测
- $d_i = i\times h_2(kay)$
- $h_2(key)=p-(key mod p)$ 效果最好
再散列
- 装填因子太大是查找效率下降
- 那就扩大散列表,在把原来的元素搬进去
分离链接法
- 有冲突的关键字都放在(同一个关键字的)一个链表中

删除时不能直接删除,会影响后续的查找。正确的删除是标记为删除,新的元素来时再替换

KMP算法

要点：

前缀表next(或者说match)函数的创建
动态规划

利用前缀表的原理：对于一个子串(如：ababc)，所有可能的前缀:

a
a b
a b a
a b a b
a b a b c

我们需要找出每种可能中最长的、非本身的公共前后缀，因为如果前后缀相同的话，当后缀失去匹配时，可从前缀结束的地方开始匹配，而不是从头开始。

a               null    0
a b             null    0
a b a           a       1
a b a b         ab      2
a b a b c       null    0  <一般剔除字符串本身,在开头填-1

这些最长公共前后缀的长度就构成了前缀表
 a b a b c
-1 0 0 1 2
这样就表示了当，str[j]失去匹配时，从match[j](前缀结束的地方)尝试匹配

前缀表如何创建

可将创建一个子串前缀表的问题划分为一系列子问题：
- 创建每种前缀的前缀表
- 为每种前缀构造前缀表又是一个个子串匹配问题：前1为是否匹配(是否有公共后缀)、前2位是否匹配，…，前n位是否
- 又因为从最短开始尝试，最短的又为次短的做了铺垫。最短串的KMP创建了次短所需的前缀表

对于ababc，可以划分为：

a
长的1,不需要前缀表辅助匹配。得到前缀表：
[-1]

a b
对于ab，找最长公共前后缀。找前1位(a)时，相当与在串ab中找匹配的子串a，而子串a的前缀表已经由上一步得出，前2位ab是它本身，结束匹配。得
[-1, 0]

a b a
对于aba，找最长公共前后缀。找前1位(a)时，相当与在串aba中找匹配的子串a，而子串a的前缀表已经由上一步得出，前2位同理。得
[-1 0 1]

a b a b
a b a b c

next数组

j = -1;
i = 0;
next[0] = -1;
while(i<n-1){
    if(j==-1||str[i]==str[j]){
        i++;
        j++;
        next[i] = j;
    }else{
        j = next[j];
    }
}

nextVal数组

j = -1;
i = 0;
next[0] = -1;
while(i<n-1){
    if(j==-1||str[i]==str[j]){
        i++;
        j++;
        if(str[i]!=str[j]) next[i] = j;
        else next[i] = next[j];
    }else{
        j = next[j];
    }
}

实战1：一颗树A是否是另一个树的子树B

序列化A和B树，然后就变成了用KMP找子串的问题了。

关于序列化和反序列化，如何序列化就如何反序列化。如使用先序遍历序列化，得到1 2 3 # #，那么也使用先序遍历反序列化得到

需要注意的是，一个节点的value表示完毕时，要给出特殊的字符序列化，否则序列化的结果可能会有歧义。

    12     1
  3      23
如果value表示完不给出特殊字符，那都是
123###

改进：
12!3!#!#!#!
1!23!#!#!#!

Manacher算法：最长回文子串

在中心扩展的基础上， 为了解决字符串长度奇偶的问题，在字符间插入#，这样一来保证找到的所有回文串都是奇数长度。

用f(i)来表示第i位为中心，可以拓展出的最大回文半径，那么f(i)-1就是以i为中心的最大回文串长度(有一半是#)。

Manacher依旧是穷举每一个位置，但是它会动态规划f(i)。遍历每个位置算出最右回文右边界，如01232101，最右回文右边界就是0处。当最右回文右边界发生变化时，记录回文中心，然后比较是否是新最大回文子串。

三种情况的处理方法
- 1. 当回文中心不在最右回文右边界中时，就暴力扩。
- 1. 当回文子串，中心在最大回文右边界内，且对称点的回文左右半径在最右回文边界对应的回文左右半径内
    - 那就可以通过对称点直接得出改点的回文半径
      1
      2
      [ ( o ) a ( o ) ]
      L i c i R
- 1. 当回文子串，中心在最大回文右边界内，且对称点的回文左右半径不在最右回文边界对应的回文左右半径内
    - 那到R回文，因为y!=Y，不然最大回文半径还会扩大
      1
      2
      ( y[ o ) a o ]Y
      L i c i R
- 1. 如果3的情况刚好压线，那就在半径到R的基础上在扩试试

Manacher模板

// 用#预处理好字符串m

// 用rs储存回文半径
// mr为最大回文半径的位置
// c为最大回文半径对应的回文中心
for(int i=1;i<len;i++){

    // 如果在最大回文半径内则取较小值，后面再调整
    // 当前点能到的最大回文半径：rm-i+1
    // 通过对称点得到的回文半径：rs[2*c - i]
    rs[i] = (i<=mr)? min(mr-i+1 , rs[2*c - i]):1;

    // 中心扩展试着找更大半径
    while(m[rs[i]+i] == m[i-rs[i]]) rs[i]++;

    // 更新最大边界及对应回文中心
    if(rs[i]+i-1 > mr){
        mr = rs[i] + i-1;
        c = i;
    }
}

窗口内最大值

窗口就是用L、R标记窗口的左右边界，而且都只能往右，不能回退。

使用一个队列储存下标和值
队列只能从大到小排列
- 当窗口右边界向右，在队列后面，如果队列后面的数小于等于待插入的数，则弹出，直到大于等于
- 当窗口左边界向右，检查队列前面的值的index是否过期，过期则弹出
这么一来，队列顶部的数就是当前窗口中的最大值

struct Node {
    val
    index
}

例题1

找出最大值减最小值小于num的所有子数组，且要求时间复杂度为O(n)

解：
- 1. 性质
    - 如果一个数组达标，那它里面的任何一个子数组一定达标
    - 如果一个子数组不达标，那它怎么往外扩都不达标
- 1. 利用上面的性质，创建一个最小队列和一个最大队列，让L=0，R外扩，直到下一个r不达标
    - 那么以L开头的所有子数组都达标，R-L+1个
    - ans += R-L+1
- 1. 然后L右缩小移位，如果R的下一个可以达标，那就外扩，然后回到第2步
- 这么就得到了所求

单调栈

单调栈：从底到顶是有顺序的，如大到小。

对数组中的每个元素找出它左边最近的大于它的值和右边最近大于它的值。要求时间复杂度O(n)。如：

3 5 2 4 6
    左      右
3   null    5
5   null    6
2   5       4
...

1. 建立一个单调栈
1. 如果满足单调的顺序要求，则可栈
1. 当要入栈的数不满足顺序要求，则开始弹出，并记录数据
  - 如下一个index的4，不满足顺序，那么index为3的数右边最近的比他大的数就是index4对应的数，那么左边最近的比他大的就是弹出后的栈顶
1. 弹出后插入是否有序，不满足则再次进行3的操作
1. 如果数组遍历完了栈还没空，则依次弹出，无右边最近的大于的数
如果两个相同的数相邻，则在栈中他们共用一个位置

例题1

给定一个没有重复元素的数组要求建立一棵树，其中的每一棵子树上，值最大的节点都是树的头部。如果数组长度为n，则时间复杂度要求为O(n)

解1. 使用大大根堆
解2. 使用单调栈
- 使用单调栈找出左右最近的大于的信息
- 若左右都找不到大于的节点，则说明该点最大，做根节点
- 当左右都有大于的节点时让当前节点成为较小的一个子节点

例题2

给定一个整形矩阵map，其中的值只有0和1两种，求其中全是1的所有矩形区域中，最大的矩形区域中1的数量

引子题：求组装它所包含的最大的矩形面积
- 如柱状图的高度分别为：5 2 3 1 4最大面积就是6(2往左往右)
- 这个题的解法就是建立从小到大的单调栈，找出每个元素最右最近的小于的值
- 然后更新面积信息
解
- 1. 从第一行开始，执行上面的操作找出最大的矩形，更新max值
- 1. 加上下一行，当以列的元素遇到零时归零
    - 这里加到最后会得到0 3 0 1
    - 然后就成为了引子题的问题
- 这么一个过程下来就记录的最大值

例题3

给一个数组表示一个环形的山，数组的值表示山的高度。每座山顶放烽火，相邻的山可以相互看见，高的山会挡住低的山的视线。求能互相看见的对数。

思路类似例2，中的柱状图，小的山峰找大的山峰，使用最大值打底作出单调栈，找出两边最近的大于的数，弹出时结算对数，一般情况下是2对。需要注意的是：

如果入栈的数和栈顶的数一样大，那就压在一起计数加一，如4, 44个4，当来了的大的值如5

结算4个4，则得到的对数为$C_4^2 + 4*2$，C42表示这4个4之间的对数，4x2表示每个4左右都能看到

如果遍历完了栈还非空

栈剩余2条以上的记录时，还是公式$C_k^2 + k*2$
栈剩2条记录时
- 如果最后一条记录的个数是大于1，则还是公式
- 如果最后一条记录的个数是1，则公式把k*2改为k*1
只剩一条记录是时$C^2_k$

字符串匹配

递归
- f(int i, int j)，表示str[i]之后的整个能不能被exp[j]之后的整个匹配
  - j+1是*
    - 如果i，j匹配
    - 如果i，j不匹配
  - j+1不是*
    - 如果i，j匹配
    - 如果i，j不匹配
暴力递归

bool process(string& str, string& exp, int i, int j){
    if(j == exp.size()){
        return i == str.size();
    }
    // j上面还有字符，考察j+1的情况
    if(j + 1 == exp.size() || exp[j+1] != '*'){
        return i != str.size() && (exp[j] == str[i] || exp[j] == '.')
            && process(str, exp, i+1, j+1);
    }
    // exp的j+1位置不仅有字符，而且字符是*
    while(i != str.size() && (exp[j] == str[i] || exp[j] == '.')){
        if(process(str, exp, i, j+2)){
            return true;
        }
        i++;
    }
    return process(str, exp, i, j+2);
}

动态规划

building…

树

Morris遍历

一般方法的遍历树，空间复杂读是O(h)，h是树的高度，因为需要用栈来储存父节点来实现回退。

Morris遍历是在空间复杂度为O(1)的情况下遍历树的方法。它利用了树上的空闲空间

1. 当前节点记位Cur，如果Cur无左孩子，Cur向右移动Cur = Cur.right
1. 如果Cur有左孩子，找到Cur左子树上最右的节点，记做mostright
  - 1. 如果mostright的右指针是空，让其指向Cur，然后cur向左移动
  - 1. 如果mostright的右指针指向cur，让cur右移，然后让其指向空
1. 没有右孩子遍历结束

void func(Node* head){
    if(head==nullptr){
        return
    }
    Node cur = head;
    Node mostRight = null;
    while(cur!=null){
        mostRight = cur.left;
        if(mostRight != nullptr){
            while(mostRight.right != nullptr && mostRight.right != cur){
                mostRight = mostRight.right;
            }
            if(mostRight.right == nullptr){
                mostRight.right = cur;
                cur = cur.left;
                continue;
            }else{  // 第二次来此节点
                mostRight.right = nullptr
                // cur = cur.right; //跳过or not
            }
        }
        cur = cur.right;
    }
}

Morris后序遍历

Morris遍历在遍历右子树时无法一步一步后退，这会导致需要回溯时不是全部都能单步回溯。

后序遍历获得左字节点后就可输出，但是要在根节点前输出右子节点，需要外的操作。可以将整个”右斜”的树记录然后逆序输出，就是后序的结果。

vector<int> postorderTraversal(TreeNode* root){
    vector<int> ans;
    TreeNode* mostRight;
    TreeNode* head = new TreeNode(0);
    head->left = root;
    while(head){
        mostRight = head->left;
        if(mostRight){
            while(mostRight->right && mostRight->right!=head){
                mostRight = mostRight->right;
            }
            if(mostRight->right == nullptr){
                mostRight->right = head;
                head = head->left;
                continue;
            }else{
                TreeNode* temp = head->left;
                vector<int> rtree;
                // 第二次访问节点时，其"孤立左节点"一定都已输出，且正是后序需要的在右节点前输出
                // 遍历整个右长树，然后reverse就是后序的右节点和根节点的输出
                while(temp!=mostRight){
                    rtree.push_back(temp->val);
                    temp = temp->right;
                }
                rtree.push_back(temp->val);
                reverse(rtree.begin(), rtree.end());
                for(auto i: rtree){
                    ans.push_back(i);
                }
                mostRight->right = nullptr;
            }
        }
        head = head->right;
    }
    return ans;
}

二叉搜索树

左边孩子比根节点小
右边孩子比根节点大

查找

左小右大，递归或循环

插入

左小右大，递归或循环

删除

没有孩子
- 直接插入
只有一个孩子
- 子承父业
有两个孩子
- 找到左子树的最大或右子树的最小(记为S)替换被删除节点，然后安顿好S的孩子。这里又相当于删除了S，可以递归一下。…有效降低树的高度

BinTree Delete( BinTree BST, ElementType X ) 
{ 
    Position Tmp; 
 
    if( !BST ) 
        printf("要删除的元素未找到"); 
    else {
        if( X < BST->Data ) 
            BST->Left = Delete( BST->Left, X );   /* 从左子树递归删除 */
        else if( X > BST->Data ) 
            BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
        else { /* BST就是要删除的结点 */
            /* 如果被删除结点有左右两个子结点 */ 
            if( BST->Left && BST->Right ) {
                /* 从右子树中找最小的元素填充删除结点 */
                Tmp = FindMin( BST->Right );
                BST->Data = Tmp->Data;
                /* 从右子树中删除最小元素 */
                BST->Right = Delete( BST->Right, BST->Data );
            }
            else { /* 被删除结点有一个或无子结点 */
                Tmp = BST; 
                if( !BST->Left )       /* 只有右孩子或无子结点 */
                    BST = BST->Right; 
                else                   /* 只有左孩子 */
                    BST = BST->Left;
                free( Tmp );
            }
        }
    }
    return BST;
}

BST的性质

1. BST的中序遍历是一个非递减的有序序列

平衡二叉树

节点左边都比该节点小，右边都比该节点大

不考虑平衡性的情况下

插入
- 左小右大，找到自己的位置
删除
- 当左右子树都非空时，用右子树的最左节点顶替，该节点的右子树交给它的父节点
  - 因为右子树最左节点是最小的比它大的数
  - 同理，也可选左子树的最右节点
如果考虑平衡性不同的平衡二差数动作的组合不同，但基本思想(动作)都是通过旋转来改变局部的平衡性
- 左旋：头节点变成了新头节点的左节点
  - 如果新头节点存在左孩子，则成为旧头节点的右孩子。因为对于左旋，新头节点本来是旧头节点的右孩子
- 右旋：头节点变成了新头节点的右节点
  - 如果新头节点存在右孩子，则成为旧头节点的左孩子。因为对于右旋，新头节点本来是旧头节点的左孩子

AVL树

AVL三个发明者名字的简写

发现不平衡
- 把左树高度和右树高度记录在节点中，当插入新节点时回溯，修改沿途的值，修改过程中将发现不平衡。删除节点同理
当发现不平衡时，找到最小不平衡子树 的根A，进行旋转，4种调整的组合(这插入节点为R)
- LL：左子树的左子树导致的不平衡
  - 单纯的右旋
  - A做B的右子，B的右子成A的左子
    1
    2
    3
    4
    5
    6
    右旋
    A B
    / / \
    B R A
    /
    R
- RR：右子树的右子树导致的不平衡
  - 单纯的左旋
  - A做B的左子，B的左子做A的右子
    1
    2
    3
    4
    5
    6
    左旋
    A B
    \ / \
    B A R
    \
    R
- LR：左子树的右子树导致的不平衡
  - 先左旋再右旋：
    - 先以头节点的左子节点为新头节点左旋
    - 然后就转化成了LL型的操作
  - 左旋：B做R的左子
  - 右旋：A做R的右子，R的左子做A的左子
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    A
    /
    B
    \
    R
    左旋:
    B R
    \ /
    R B
    右旋:
    A R
    / / \
    R B A
    /
    B
- RL：右子树的左子树导致的不平衡
  - 同理LR型

红黑树

为表述方便：C(current)表示针对的节点，P(parent), G(grandparent)，U(uncle)

特征
- 1. 根节点是黑色
- 1. 所有叶子(nil节点)都是黑色
- 1. 每个红色节点的两个字节点都是黑色(不存在两个连续的红色节点)
- 1. 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点
    - 黑色完美平衡

旋转：为例减小树的高度

红黑树最大高度$O(\log n)$

左旋：

C和它的右子节点交换
C右子节点的左子树成为C的右子树

右子变新爹，右子的左子变老爹的右子，老爹变新爹左子

# LEFT-ROTATE(T, x)
y = x.right
x.right = y.left
if y.left != nil
    y.left.p = x
y.p = x.p
if x.p == nil
    T.root == y
elseif x == x.p.left
    x.p.left = y
else x.p.right = y
y.left = x
x.p = y

右旋：
- C和它的左子节点交换
- C左子节点的右子树成为C的左子树
- 左子变新爹，左子的右子变老爹的左子，老爹变新爹右子

搜索
- 比节点小就找左子树，否则右子树
插入
- 每个新节点都是红色的，违规修复代价比较小
- 1. C=root，则把C变为黑色
- 1. P是黑色，直接插入
- 1. P是红色
    - I. U是红，则P和U都变黑，G变后，向上递归
    - II. U是黑
      - 三角型：GPC呈三角形
        
        对P旋转使得GPC一条直线，然后做直线型操作
      - 直线型：GPC一条直线
        
        对G旋转，然后交换G和P的颜色
删除
- building

哈夫曼树(Huffman)

两种编码方式

等长编码
- 使用固定长度的位来对所有信号进行编码
- 简单但并不是每个信号出现的频率是一样的，所有对于对于经常出现的信号，需要使用很多的资源
不等长编码
- 对于出现频率不同的信号可以采用不同长度的位进行编码
- 节省资源，但为保证译码唯一性需要进行复杂的操作

我们可以使用二叉树来进行01编码，为了保证译码唯一性，则需要每个编码不能是其他任意一个编码的前缀。所以编码的结果必须都是出现在叶子节点。

对于最优的编码，我们需要使得树的权值最小，那么权值大的节点应尽量靠近根节点，哈夫曼树就是为了解决最优编码问题产生的。

算法 :对于一组带权节点，每次选取最小和次小的的节点从原数组中删除，然后它们权值的和组成新的节点加入到原数组中，它们成为这个新节点的孩子。如此循环

数据结构：

typedef struct {
    int weight;
    int parent;
    int Lchild;
    int Rchild;
} HNode;

由于哈夫曼树的两两节点合并组成的树，所以不会存在出度为1的节点，故共有2n-1个节点。开辟一个2n-1的数组，然后根据算法填充。

Id	weight	parent	Lchild	Rchild
0
1
…
2n-2

从没有标记父节点的节点中选择最小和次小的节点，组成新的节点，放入队尾

// 初始化等操作
for(int i=rear; i<2*n-1; i++){ 
    findNodes(nodes, min, cmin); // 从没有parent的节点中找出最小和次小的节点
    nodes[min].parent = i;
    nodes[cmin].parent = i;

    // 插入尾部
    nodes[i].weight = nodes[min].weight + nodes[cmin].weight;
    nodes[i].Lchild = min;
    nodes[i].Rchild = cmin;
}

void findNodes(HNode* arr, int& min, int& cmin){
    int min=MAXINT;
    int cmin=MAXINT;
    for(int i=0; i<arr.size; i++){
        if(arr[i].parent == EMPTY){
            if(arr[i].weight < min){
                cmin = min;
                min = arr[i].weight;
            }else if(arr[i].weight < cmin){
                cmin = arr[i].weight;
            }
        }
    }
}

构造好哈夫曼树后，译码和编码操作就简单了。

译码:
- 从根节点开始，0找左节点，1找右节点(与具体怎么建立的哈夫曼树有关)
- 遇到叶子节点则得到译码结果
编码：
- 从叶子节点开始，向上寻找其父节点，如果节点是父节点的左孩子，则编码0，否则编码1，从尾向前填充
- 如***010\0
- 找到根节点则将编码传出即可

图

DFS深度优先搜索

从一节点出发
- 非连通图分而治之
依次从访问邻接点,直至所有邻接点都被访问
- 例:迷宫

BFS广度优先搜索

从一节点出发
把他所有的邻接点入队列,并检测目标节点
依次把节点出队列,并递归的把他的邻接点入队列,直到访问所有点
- 例:树的层序遍历

并查集

若存在两点在同一个连通集合中，则这两点存在回路

Find() 找根节点
Union() 合并成集合

最短路问题

Dijkstra算法

解决单源路非递减顺序(没有负)最短路径问题

初始化
- 对所有未检索的点进行标记:collected[v] = false
- 使用dist[i]=INF记录源点到节点i的最短距离
  - dist[src]=0
- 使用path[i]记录节点i的前驱节点，则从终点开始查找则得到最短路径
从未收录的顶点中选择最dist最小者V(贪心),对于V的所有未收录的邻接点W,若以V为中间节点到W的路径更短，则更新dist[W]
- 可用 最小堆优化 选择dist最小者的过程。cpp中可以使用priority_queue<T>
所有邻接点访问完后collected[v]=true,重复第2步，直到所有节点都访问
原理
- TODO:为何要选dist最小者加入

如此一来这条路径也一定是源点到这些中途节点的最短路径。

void Dijkstra(Vertex s){
    while(1){
        V = 未收录顶点中dist最小者;   // 非常重要的一步
        if(V未找到){
            break;
        }
        collected[V] = true;
        for(V的每个邻接点 W){
            if(collected[W] == false){
                if(dist[V]+E<V,W> < dist[W]){
                    dist[W] = dist[V] + E<V,W>;
                    path[W] = V;
                }
            }
        }
    }
}

Floyd算法

解决多源路非递减顺序最短路径问题

稠密图有优势

$T=O(V^3)$

// 核心
// 顶点i到顶点j,顶点间的最短路就在矩阵显示出来了
for(k = 0;k<N;k++){
    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            if(D[i][k]+D[k][j]<D[i][j]){
                D[i][j] = D[i][k]+D[k][j];
                path[i][j] = k;
            }
        }
    }
}

Prim算法

解决稠密图的最小生成树问题

从任意点出发
寻找与这个整体相邻,且不构成回路的权最小点
加入该整体,继续搜索,直至所有点都收录(生成树必须包含所有点)

Kruskal算法

解决稀疏图的最小生成树问题

$T=E\log{E}$

核心思想,每个顶点都是一棵树,把森林连成树
找最短且不构成回路的边,又因为每个顶点都是一棵树,每个边都把森林连成树

MST={};  // 最小生成树
E;   // 边集
while(没够V-1条边&&E没空){
    findmin();  // 找最小边  用最小堆
    delet(E(v,w));  // 把该边移除边集E
    if(E(v,w)加入MST不构成回路)   // 并查集
        join(E(v,w));  // 加入并查集
    else
        单纯的删除
}
if(MST中边不够V-1条)
    生成树不存在

A星寻路算法

启发性搜索：f = g + h
- f：当前点到终点的代价
- g：起点到当前点的代价
- h：当前点到终点的 预估代价
  - 忽略障碍，只算直线距离，但是移动时只走无障碍的路
过程
- 使用一个OPEN列表保存能走且未走过的路
- 使用一个CLOSED列表保存走过的路
- 将起点放入OPEN列表
- 循环
  - 1. current=OPEN列表中f最小的点
  - 1. OPEN中移出current放入CLOSED
  - 1. 如果current是终点，则循环结束
  - 1. 遍历current的所有邻居(其中的邻居不能是CLOSED中、不能是障碍物)
  - 1. 计算邻居的f
  - 1. 将邻居的parent设为current
  - 1. 将邻居放入OPEN列表
- 最后从终点一直沿着父节点走就找到了最短路径

效率问题

联机算法

在任意时刻，算法对要操作的数据只读入（扫描）一次，一旦被读入并处理，它就不需要在被记忆了。而在此处理过程中算法能对它已经读入的数据立即给出相应子序列问题的正确答案。具有这种特性的算法叫做联机算法（on-line algorithm。

分治算法

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

该问题的规模缩小到一定的程度就可以容易地解决
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
利用该问题分解出的子问题的解可以合并为该问题的解
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题

回溯

全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路，可以模拟全排列的过程，一个一个插入。只是不同的方法优劣程度不同
- 妙：通过交换位置维护已选数，回溯时再换回来
  - 1. 优化空间，不需要而外空间保存已选
  - 1. 优化未选数查询，交换后已选的数都排在了前头，未选的数从剩余长度开始就是

void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
    // 所有数都填完了
    if (first == len) {
        res.emplace_back(output);
        return;
    }
    for (int i = first; i < len; ++i) {  // first表示要插入的位置，i表示要选择插入的对象
        // 使用交换来维护已选数组
        swap(output[i], output[first]);
        // 继续递归填下一个数
        backtrack(res, output, first + 1, len);
        // 撤销操作
        swap(output[i], output[first]);
    }
}

位运算

布隆过滤器

设有100亿个黑名单网页，每个网页URL占用64字节，想要实现一种网页过滤系统，过滤黑名单，允许有万分之一的判断失误，且而外空间不超过30G。

如果用哈希表存入数据库，但是至少需要640G空间。这样对空间要求比较严格，但允许一定失误的过滤系统，往往是 布隆过滤器：使用很少的空间就能把正确率做到很高的程度

布隆过滤器可以精确的代表一个集合，可精确到判断某一元素是否在集合中，但100%的精确是不可能的。

加入布隆过滤器
- 一个长度为m的bit类型的数组bitarray，每个位置只有0(白)和1(黑)
- 有k个哈希函数，这些哈希函数都足够优秀，且输出域都大于等于m
- 对于一个对象，如64字节的URL通过k个哈希函数
  - 哈希的结果对m取余，取余的结果在bitarray上将相应的位置设为1(涂黑)
- 使用该方法处理所有的对象，如果遇到已经涂黑的位置，则让其保持黑
检查
- 将对象通过这k个哈希函数，取余等操作，找到bitarray上对应的位置
- 如果得到的位置都为黑色，则就是黑名单中，否则不是
- 但是也有可能误判，将白的判为黑的

bitarray和k大小的确定

bitarray大小m由样本数量n和能容忍的驶入率p决定。上题中$m=100亿，p=0.01%$

$$
m = - \frac{n \times lnp}{(ln2)^2} \
k = ln2 \times \frac mn = 0.7 \times \frac mn
$$

不用额外空间交换量整数的值

a = a0;
b = b0;
a = a^b;  // a=a0^b0, b=b0
b = a^b;  // a=a0^b0, b=a0^b0^b0=a0
a = a^b;  // a=a0^b0^a0=b0, b=a0

奇数次偶数次

1. 假设一个数组中只有一个数出现了奇数次，其他数都出现了偶数次，要求在时间复杂度0(1)的情况下找出这个数。
  - 使用一个数a=0，与arr中的每一个数[c, b, a, c, b, a, d]异或，结果就是这个数
  - 因为异或运算满足交换率和结合率，异或的次序就可以是[aabbccd]，所以得到d
1. 第一题小小改进，有两个数出现奇数次
  - 先与每个数异或最后剩下a=b^c
  - 因为b和c是不同的数，所以a不为0，找到为1的一位，假设是第k位
  - 因为低k位为1，说明a和b的第k位一定不一样
  - 第二次遍历让a2=0只与与第k位为1的数异或，则异或的结果就是a和b中的一个
  - a^a2的结果就是a和b中的另一个

动态规划

从暴力搜索推导出动态规划，然后优化

动态规划与记忆搜索的关系

给定一个集合，{1, 5, 10, 15, 25}，求组合得到一个数target是所有组合数。

递归
- 遍历数组，取一个值后，用剩下target继续递归执行
- 大量重复计算，对于一个target值，组合数是相同的，不需要每次都从头计算
记忆搜索
- 使用一个map记录某个状态下target对应的组合数，如果没计算过才算，否则直接取值
- 区别于动态规划 ，记忆搜索”不规定计算顺序”，遇到无记忆的就算
动态规划
- 生成行数为N，列数位aim+1的矩阵dp(dynamic programming)，dp[i][j]表示使用arr[0...i]货币的情况下，组成钱数j有多少种方法
- 动态规划规定每一种递归状态下的计算顺序，依次进行计算
- 动态规划严格规定计算顺序，存在进一步优化的可能

building…

大数据

Map-Reduce

Map
- 通过哈希函数把大任务分成子任务
Reduce
- 把子任务并发处理，然后合并结果
注意点
- 备份的考虑，分布式存储的设计细节(多少备份合适)
- 任务分配策略与任务进度跟踪
- 多用户权限控制

以下的经典用map-reduce解决问题的方案

例题

统计一篇文章中每个单词出现次数

文章预处理，抓取有效单词
- 去除标点，去除连字符，处理缩写等
map阶段
- 对每个单词生成词频为一的记录，如(dog, 1), (cat, 1)
- 通过哈希函数将所有单词分成若干个子任务
  - 每个子任务会包含若干种单词，但同一种单词不会被分配到不同子任务中
  - 这样一来相同的都能被统计到
reduce阶段
- 所有子任务记录合并

海量数据处理

1. 分治，通过哈希函数将大任务分流
  - 难点在于通讯、时间和空间的估算
1. 分流，通过哈希函数将大文件文流到小文件
  - 解决局部问题从而解决整体问题

例题1

对10亿个ip地址排序，已知每个ip地址只会出现一次

普通方法
- 每个ip转换成无符号整数
- 10亿个整数约占4G空间
bitmap
- 每个ip转换成无符号整数
- 申请一个$2^32$的bit类型的数组，空间约128m
- 如果整数k出现则把第k-1位bit描黑
- 从0位置遍历，把ip通过位置还原即可

例题2

一个包含20亿个全是整数的大文件，在其中找出出现次数最多的数。但是内存只有2G

普通方法：HashMap
- key：具体一种数，整型4字节
- value：出现次数，整型4字节
- 一条记录8字节，如果产生20亿条记录将会溢出，但是如果记录条数比较少可能也不会溢出
哈希函数分流
- 将大文件的数分配到小文件中
  - 同一个数肯定在同一个文件
  - 而且分配均匀，每个文件用到的内存相当
- 找出小文件中各自最高，比较即可

数据缓存

一般使用集群来实现数据缓存，因此需要优秀的哈希函数在做负载均衡。如果使用简单是哈希函数，如取余哈希，将会面临以下问题。

问题
- 增加或删除机器时代价很高，机器数改变所有数据需要重新哈希
- 因此还需要大规模的数据迁移
改进方案
- 一致性哈希算法
  - 数据id哈希计算的结果范围是 0～2^32
  - 将id组哈希组织成首尾相连的环形结构
  - 机器均匀的分配在其中的机器点
  - 数据计算哈希后，找到距离最近(规定只能一个方向找)的机器，则这个数据由该机器管理
  - 添加删除机器只会改变环的一部分

字符串

字符串拷贝和替换

给定一个字符串str，将其中空格替换成”%20”，假设str后面有足够的空间

算出替换后的长度
从后向前拷贝，经常是这种操作

括号匹配

给定一个字符串str，判断是不是整体有效的括号字符串，最优解时间复杂度O(n), 空间复杂度O(1)

用一个num记录一种括号，以下假设只有一种括号出现
左括号num++，右括号num–
如果num<0，return false
如果遍历完后num==0,return true

最长无重复子字符串

给定一个字符串str找出它的最长无重复子字符串，最优解O(n), O(n)

假设s[i]表示i位置为结尾，能到达(符合不重复字符)的最左的位置
map，统计每种字符最后一次出现的位置
int pre，s[i-1]结尾的情况下，能到达的最左位置
1. map[str[i]]找到之前str[i]结尾的位置，记为A
1. 使用pre，找到str[i-1]最左位置，记为B
1. 比较A和B，选择当前位置间A或B较短的一方，更新最大无重复字符字串长度
1. 更新，map和pre
原理:
- 从左到右都是取最长无重复，再多一个就重复的操作

字符串旋转/逆序的妙用

旋转题

给定两个字符串str1，str2，判断是否互为旋转词，要求时间复杂度O(N)

1
2
3

a = "cdab", b = "abcd", true
a = "1ab2", b = "ab12", false
a = "2ab1", b = "ab12", true

KMP(str1+str1, str2)
- str和str拼接后，以长度为4的字符串为例，则[0~~3]，[1-4], [2~~5]…各是一种旋转次，因此拼接后的字符串包含所有可能的旋转词

逆序妙用

给定一个字符串，在单词间做逆序调整，如: I’m a student. => student. a I’m
- 全局逆序，再每个单词每个单词的逆序
给定一个字符串str，和一个整数i，i将str[0:i]移到右侧，str[i+1:n-1]移到左侧。如：str = “abcde”, i=2 => “deabc”，要求:时O(N)，空O(1)
- 整体逆序，再每段逆序([0,2]逆序，[3,n-1]逆序)

排列组合

卡特兰数公式

公式之一

假设有n对左右括号，求合法的排列组合有多少种？

n对括号，则总排列数为 C_{2n}^n 。把左括号记为1，右括号记为-1
当第一次出现-1个数大于1时(即不合法)，把所以1变为-1,所有-1变为1。于是得到一个有n+1个1和n-1个-1的排列
利用证明结论：每一个非法的排列通过如上方式变换，可以得到n+1个1和n-1个-1组成的排列
则所有不合法排列数 = n+1个1和n-1个-1组成的排列数 = $C_{2n}^{n+1}或C_{2n}^{n-1}$
所以合法排列数 = $\frac1{n+1} \times C_{2n}^n $ 。_
- 即 卡特兰数公式 之一

building(数学问题)

算法

c/c++

c/cpp语言碎片知识

c读写读取字符串读取单个字符 getchar()是scanf("%c", c)的简化版本，除了更简介无其他优势 getche()，没有缓冲区，输入一个字符后立即读取，不等待...

Tensorflow

基本操作图片读取展示1234import cv2 # 引入OpenCVimg = cv2.imread('path',1) # 读取图片，0是灰图，1是彩图cv2.imshow('image...