4 算法初步

4.2 散列

线性探查法：冲突后检查下一位。

平方探查法：冲突后依次检查 $H(key)+1^2, H(key)-1^2, H(key)+2^2, H(key)-2^2, H(key)+3^2, H(key)-3^2$ 。超出散列表长度，取余。
链地址法：每一位散列值上用链表存放数据。

字符串hash：26进制整数。

for(int i=0; i<len; i++){
    id = id*26 + (s[i] - 'A');
}

4.4 贪心

数学归纳地一步步推出最优解。 区间贪心

4.5 二分

4.5.1 二分查找 O(logn)

查找满足特定条件的值
求 $\sqrt{2}$ 的近似值
快速幂：幂指数为奇数时二分，幂指数为偶数时减1；快速傅里叶变换的思想。

PS：用位运算判断奇偶要快一点，(a & 1) 代替(a%2 == 1)

4.6 two pointers

2路归并排序：

递归实现：实现merge()和mergesort()两个函数。
非递归实现

归并

快排和随机快排：随机快排，不再像快排一样直接选取第一位为标准，而是随机选取一个位置的数与第一位交换，然后进行快排的partition()操作。

4.7 其他高效技巧和算法

打表：空间换时间，将所有可能的结果事先计算出来保存，后面需要用到时查表得到。

4.7.3 随机选择算法

求一数组里面第K大的数：利用随机快排算法，随机选择中值，每次partition后，中值前的数都比它小，中值后的数都比他大，判断中值下标是否为K。最坏情况 $O(n^2)$ ，最好情况 $O(n)$
对比第K个小或者大的数的顺序不关心，省到极致。

5 数学问题

5.2 最大公因数gcd(a,b)，辗转相除法。最小公倍数lcm(a,b) = a*b / gcd(a,b)

5.6 实现大整数加减乘除

struct保存大整数
减法注意去除高位的0，修改大整数的len
乘法一次进位可能有多位，注意最终的进位处理
先令商长度和被除数相等，最后删去商开头的0

6 STL库介绍

6.1 vector

1. 通过下标 或 迭代器访问
vector<int>::iterator it;

2. 常用操作
vec.push_back(val);
vec.pop_back(val); 
vec.size(); 
vec.clear(); 
vec.insert(iter, val);

3. erase可删除单个元素，或区间内元素（用iter指示）
vec.erase(iter);
vec.erase(vec.begin(), vec.end()); //不删除第二个参数指向的元素

6.2 set

1. 只能用迭代器访问
set<int>::iterator it;

2. 常用操作
st.insert(val);
iter = st.find(val); //返回一个迭代器
st.size(); 
vec.clear(); 

3. erase可删除单个元素，或区间内元素（用iter指示）
st.erase(value); //与vector不同
st.erase(st.begin(), st.end()); //不删除第二个参数指向的元素

6.3 string

1. 通过下标 或 迭代器访问
string::iterator it;

2. 可直接使用+，+=连接string

3. 可直接使用 >, <, ==等按字典序比较string

4. 常用操作
str.length();  str.size();
str.clear();
str.substr(pos, length);
str.replace(pos, length, str2);
str.replace(it1, it2, str2);

5. insert用法
str.insert(3, "pop"); //在str的下标3位置处插入字符串“pop”，其他字符顺序后移。
str.insert(it, it1, it2); //it为源字符串插入位置，it2、it3为待插入字符串首、尾+1（例如：str2.end()） 

6. erase可删除单个元素，或区间内元素（用iter指示）
str.erase(iter);
str.erase(str.begin(), str.end()); //不删除第二个参数指向的元素
str.erase(pos, length); //pos为下标

7. str.find(str2)返回子串在str中对应起始位置下标。失配时返回 string::npos

6.4 map

定义方式：map<char, int> mp;

1. 通过key 或 迭代器访问，用it->first, it->second访问key和value
mp['b'];
map<char, int>::iterator it;

2. 常用操作
it =  mp.find('b'); //返回迭代器
mp.size();
mp.clear();

3. erase可用迭代器或者key删除单个元素，或区间内元素（用iter指示）
mp.erase(iter);
mp.erase('b');
mp.erase(mp.begin(), mp.end()); //不删除第二个参数指向的元素

6.5 queue, 先进先出

1. 只能访问 队首 和 队尾 元素
q.front();
q.back();

2. 入队和出队
q.push();
q.pop();

3. 检测是否为空
q.empty(); // 返回bool值
q.size();

！！！front()或pop()前使用empty()检查是否有元素

6.6 priority queue

1. 只能访问 队首 元素，即为优先级最高的元素
pq.top();

2. 入队和出队
pq.push();
pq.pop();

3. 检测是否为空
q.empty(); // 返回bool值
q.size();

优先级设置

1. 最基本形式
priority_queue<int, vector<int>, less<int> > q; //数字大的优先级高
priority_queue<int, vector<int>, greater<int> > q; //数字小的优先级高

2. 结构体（or 类）优先级设置：重载<小于号（重载大于号会出错）
struct fruit{
    string name;
    int price;
    friend bool operator < (fruit f1, fruit f2){
        return f1.price < f2.price;
    }
}
priority_queue<fruit> pq; //正常定义的小于号，价格越高优先级越高

3. 在结构体中定义cmp，重载（）符号
struct cmp{
    bool operator () (fruit f1, fruit f2){
         return f1.price < f2.price;  // 优先队列为价格高优先级高
    }
};

重载运算符

调用作为类的成员函数的运算符重载函数时，类对象肯定已经被建立了，这时对象中对应的私有数据成员存在。

bool operator < (fruit f2){
    return this->price < f2.price;
}

调用作为类的友元函数的运算符重载函数时，类对象还未被建立，这时对象中对应私有数据成员不存在。

friend bool operator < (fruit f1, fruit f2){
    return f1.price < f2.price;
}

6.7 stack 栈：后进先出

类似优先队列
st.push();  st.pop();
st.top();

st.empty(); st.size();

6.8 pair

1. 只有两个元素
p.first; p.second; //注意没有括号

2. 可以直接使用比较算符，先比较first，再比较second

6.9 <algorithm>中常用函数

max(); min(); abs();
swap()
reverse(it1, it2)l; 将两迭代器之间的内容逆序，不包括it2所在位置元素
全排列 next_permutation(it1, it2); 或者使用指针作为参数。当已经达到全排列的最后一个（逆序时），则会返回false

int a[10] = {1,2,3};
do{
     printf("%d,%d,%d\n",a[0],a[1],a[2]);
}while(next_permutation(a, a+3));

fill(it1, it2, 233); 给数组或者容器复制233
sort(it1, it2, cmp);
it = lower_bound(it1, it2, val); 返回第一个大于等于val的元素的iter
it = upper_bound(it1, it2, val); 返回第一个大于val的元素的iter

7 数据结构专题

7.1 栈 stack

两个栈实现简单计算器：从头开始读表达式，遇到数字立即压入数字栈。遇到运算法与算符栈顶比较：

若比栈顶优先级高则入栈
若比栈顶算符优先级低，则算符栈栈顶出栈，与数字栈顶两位数字运算后压入数字栈。

7.3 链表

动态链表一般头部不保存数据，便于下面insert，del函数的编写。静态列表首部保存数据。

struct node{
    int data;
    node* next;
};

（1）动态分配内存：malloc 与 free

int* p = (int*)malloc(sizeof(int)); // 申请一块int32大小的32位内存，返回指针
free(p); //释放内存

（2）动态分配内存：new 与 delete

int* p = new int; // 同样返回一个指针
delete(p); // 与new对应的释放内存

for循环创建链表（表头也保存数据）

node* create(int A[ ], int n){
    node *p, *pre, *head;
    head = new node;
    head->next = NULL;
    pre = head;
    for(int i=0; i<n; ++i){
        p = new node;
        p->data = A[i];
        p->next = NULL;
        pre->next = p;
        pre = p;
    }
    return head;
}

在第pos个位置插入数据val

void insert(node* head, int pos, int val){
    node* p = head;
    for(int i=0; i<pos-1; ++i) p = p->next;
    node* new_p = new node;
    new_p->data = val;
    new_p->next = p->next;
    p->next = new_p;
}

删除值为val的元素

void del(node* head, int val){
    node* p = head;
    node* pre = new node;;
    while(p != NULL){
        if(p->data == val){
            pre->next = p->next;
            delete(p);
            p = pre->next;
        }else{
            pre = p;
            p = p->next;
        }    
    };
}

8 搜索专题

8.1 DFS 深度优先

用一个栈的出栈入栈就能实现
一般用递归实现，递归的本质也是系统栈的入栈出栈。
程序见8.2后

8.2 BFS 广度优先

用一个先进先出队列能实现
不访问曾经访问过的节点
BFS与DFS程序差别极小

#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
using namespace std;

char graph[5][5] = {{'.','.','.','.','.'},
                    {'.','*','.','*','.'},
                    {'.','*','S','*','.'},
                    {'.','*','*','*','.'},
                    {'.','.','.','T','*'}};
int visited[5][5] = {0};
int move_x[5] = {1, -1, 0, 0}; 
int move_y[5] = {0, 0, 1, -1}; 

void plot_visited(){
    for(int i=0; i<5; ++i){
        for(int j=0; j<5; ++j){
            printf("%d ",visited[i][j]);
        }
        printf("\n");
    }
}

int judge(int x, int y){
    if(graph[x][y]=='*' || x < 0 || x > 4 || y < 0 || y > 4 || visited[x][y]) return 0;
    if(graph[x][y] == '.') return 1;
    if(graph[x][y] == 'T') return 2;
    return 0;
}

int BFS(){
    int sx, sy, tx, ty;
    for(int i=0; i<25; i++){
        if(graph[i/5][i%5] == 'S'){sx = i/5; sy = i%5;}
        if(graph[i/5][i%5] == 'T'){tx = i/5; ty = i%5;}
    }

    queue<vector<int> > q;
    vector<int> temp;
    int x, y;
    int dis = 0, min_dis = 65535;
    q.push({sx,sy, 0});
    visited[sx][sy] = 1;
    while(!q.empty())
    {
        x = q.front()[0]; y = q.front()[1];
        dis = q.front()[2];
        q.pop();
        int tempx, tempy;
        for(int i=0; i<4; i++){
            tempx = x + move_x[i]; tempy = y + move_y[i];
            int jud = judge(tempx,tempy);
            if(!jud){
                continue; //多此一举
            }else if(jud == 1){
                q.push({tempx, tempy, dis+1});
                visited[tempx][tempy] = 1;
            }else if(jud == 2){
                min_dis = dis + 1;
                return min_dis;
            }
        }
    }
    return -1; 
}

int DFS(){
    int sx, sy, tx, ty;
    for(int i=0; i<25; i++){
        if(graph[i/5][i%5] == 'S'){sx = i/5; sy = i%5;}
        if(graph[i/5][i%5] == 'T'){tx = i/5; ty = i%5;}
    }

    stack<vector<int> > st;
    vector<int> temp;
    int x, y;
    int dis = 0, min_dis = 65535;
    st.push({sx,sy, 0});
    visited[sx][sy] = 1;
    while(!st.empty())
    {
        x = st.top()[0]; y = st.top()[1];
        dis = st.top()[2];
        st.pop();
        int tempx, tempy;
        for(int i=0; i<4; i++){
            tempx = x + move_x[i]; tempy = y + move_y[i];
            int jud = judge(tempx,tempy);
            if(jud == 1){
                st.push({tempx, tempy, dis+1});
                visited[tempx][tempy] = 1;
            }else if(jud == 2 && min_dis > dis+1){
                min_dis = dis + 1;
            }
        }
    }
    if(min_dis == 65535) return -1; 
    return min_dis;
}

int main(){
    int min_dis = DFS();
    plot_visited();
    if(min_dis < 0){
        printf("Cannot find\n");
    }else{
        printf("%d\n",min_dis);
    }
    return 0;
}

9 数据结构专题

9.1 树与二叉树

定义：空树、层次（根节点为第一层）、度（节点子树的棵数）；n个节点的树有n-1条边；深度（自顶向下，根节点为1）、高度（自底向上，最底层子节点为1）
二叉树分类：满二叉树（E）、完全二叉树（D，E）

在这里插入图片描述

6.1.3 二叉树储存、查找、修改、插入

储存结构

struct node{
    int data;
    node* lchild;
    node* rchild;
};

生成新节点

node* newNode(int val){
    node* p = new node;
    p->data = val;
    p->lchild = p->rchild = NULL;
    return p;
}

根据二叉树类型不同有不同的插入方式，需要新建节点时直接引用root，注意&

void insert(node* &root, int val){
    if(root == NULL){
        root = newNode(val);
        return;
    }
    if(根据二叉树性质val应该插在左子树){
        insert(root->lchild, val);
    }else{
        insert(root->rchild, val);
    }
}

递归查找x，并修改为new_x。视情况修改查找方法

void search_and_modify(node* root, int x, int new_x){
    if(root == NULL) return;
    if(root->data == x) root->data = new_x;
    search_and_modify(root->lchild, x, new_x);
    search_and_modify(root->rchild, x, new_x);
}

注意root = NULL 与 *root == NULL的区别

9.2 二叉树的遍历

先序遍历：根节点->左子树->右子树（深度优先）
中序遍历：左子树->根节点->右子树（深度优先）
后序遍历：左子树->右子树->根节点（深度优先）
层次遍历（广度优先）

9.2.1 先序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)

void preorder(node* root){
    if(root == NULL) return;
    printf("%d ", root->data); \\ 根
    preorder(root->lchild); \\ 左
    preorder(root->rchild); \\右
}

利用先序序列（数组）和（中序序列）构建一棵二叉树

int pre_arr[20] = {1,2,4,5,3,6,7};
int in_arr[20] = {4,2,5,1,6,3,7};

node* create(int preL, int preR, int inL, int inR){
    if(preL > preR) return NULL;
    node* root = new node;
    root->data = pre_arr[preL];
    int k;
    for(k = inL; k<=inR; k++){
        if(in_arr[k] == pre_arr[preL]) break;
    }
    root->lchild = create(preL+1, preL+k-inL, inL, k-1);
    root->rchild = create(preL+k-inL+1, preR, k+1, inR);
    return root;
}

中序序列可以和先序序列、后序序列、层序序列中任意一个来构建唯一的二叉树。因为先序序列、后序序列、层序序列都可以确定root，而中序序列用于划分左子树和右子树。

9.2.4 层序遍历

类似广度优先算法，利用队列。可在node中加入深度信息 layer

void layerOrder(node* root){
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        node* now = q.front();
        q.pop();
        printf("&d ", now->data);
        if(now->lchild != NULL) q.push(now->lchild);
        if(now->rchild != NULL) q.push(now->rchild);
    }
}

9.2.5 二叉树静态实现

用一个node数组保存节点，用数组的下标来代替之前的指针，程序写法和前面的类似。引入全局变量index，nodes[index]

9.3 一般树的遍历

一般使用静态写法，用数组的下标代替指针，指向一棵子树。

struct node{
    int data;
    vector<int> child;
}Nodes[maxn];

int index = 0;
int NewNode(int x){
    Nodes[index].data = x;
    Nodes[index].child.clear();
    index++;
}

遍历方式：先根遍历（参考先序遍历），层序遍历（BFS）。

9.4 二叉查找树（BST）

对任意一个节点，左子树的数据都比根节点数据小，右子树的数据都比根节点数据大。

查找元素x，并返回其所在节点。

node* search(node* root, int x){
    if(root == NULL) return;
    if(root->data == x) return root;
    if(root->data > x) search(root->lchild, x);
    if(root->data < x) search(root->rchild, x);
}

不存在重复元素的插入

void insert(node* &root, int val){
    if(root == NULL){
        root = newNode(val);
        return;
    }
    if(root->data == val){
        return;
    }else if(root->data > val){
        insert(root->lchild, val);
    }else{
        insert(root->rchild, val);
    }
}

用数组建立二叉查找树

node* create(int data[], int n){
    node* root = NULL;
    for(int i=0; i<n; i++) insert(root, data[i]);
    return root;
}

若删除的节点下没有子树，则直接删除。若该节点有左子树，则寻找该结点的前驱代替它。若该节点没有左子树而有右子树，则寻找该结点的后继代替它。（比根节点data小的最大节点称为根节点的前驱，同理比根节点data大的最小节点成为该节点的后继）

node* findMax(node* root){
    while(root->rchild != NULL){root = root->rchild;}
    return root;
}

node* findMin(node* root){
    while(root->lchild != NULL){root = root->lchild;}
    return root;
}

void deleteNode(node* &root, int x){
    if(root == NULL) return;
    if(root->data == x){
        if(root->rchild == NULL && root->lchild == NULL){
            root == NULL;
        }else if(root->lchild != NULL){
            node* pre = findMax(root->lchild);
            root->data = pre->data;
            deleteNode(root->lchild, pre->data); //因为前驱或者后继不一定为空树，前驱可能有左子树，后继可能有右子树
        }else{
            node* pro = findMin(root->rchild);
            root->data = pro->data;
            deleteNode(root->rchild, pro->data);
        }
    }else if(x < root->data){
        deleteNode(root->lchild, x);
    }else{
        deleteNode(root->rchild, x);
    }
}

二叉查找树的中序遍历是从小到大排列的数

9.5 平衡二叉树（AVL树）

每次插入元素后树的高度仍保持O(logn)。要求每个节点左子树和右子树高度之差的绝对值不超过1
在结构体中增加保存高度的参数。·

struct node{
    int data, height;
    node *lchild, *rchild;
};

新建节点的函数也需稍作修改

node* newNode(int val){
    node* p = new node;
    p->data = val;
    p->height = 1;
    p->lchild = p->rchild = NULL;
    return p;
}

返回节点高度的函数，NULL节点返回高度0

int getHeight(node* root){
    if(root == NULL) return 0;
    return root->height;
}

更新节点高度的函数

void updateHeight(node* root){
    root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}

计算平衡因子的函数

int getBalanceFactor(node* root){
    return getHeight(root->lchild) - getHeight(root->rchild);
}

查找操作与二叉查找树相同
插入操作需掌握左旋、右旋操作。可以证明，然后把最靠近插入节点的失衡节点（平衡因子绝对值为2）调整到正常，路径上的所有节点都会平衡。调整分4种情况。

树型	判定条件	调整方法
LL	BF(root)=2, BF(左子树)=1	对root进行右旋
LR	BF(root)=2, BF(左子树)=-1	对lchild进行左旋，再对root进行右旋
RR	BF(root)=-2, BF(右子树)=-1	对root进行左旋
LL	BF(root)=-2, BF(右子树)=1	对rchild进行右旋，再对root进行左旋

插入操作需掌握左旋、右旋操作。可以证明，然后把最靠近插入节点的失衡节点（平衡因子绝对值为2）调整到正常，路径上的所有节点都会平衡。调整分4种情况。

void leftRotate(node* &root){
    node* temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}

void rightRotate(node* &root){
    node* temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}

void insert(node* &root, int val){
    if(root == NULL){
        root = newNode(val);
        return;
    }
    if(root->data > val){
        insert(root->lchild, val);
        updateHeight(root);
        if(getBalanceFactor(root) == 2){ //往左子树里插入元素，左子树高度增加,且左子树不可能平衡
            if(getBalanceFactor(root->lchild) == 1){
                rightRotate(root);
            }else if(getBalanceFactor(root->lchild) == -1){
                leftRotate(root->lchild);
                rightRotate(root);
            }
        } 
    }else{
        insert(root->rchild, val);
        updateHeight(root);
        if(getBalanceFactor(root) == -2){
            if(getBalanceFactor(root->rchild) == -1){
                leftRotate(root);
            }else if(getBalanceFactor(root->rchild) == 1){
                rightRotate(root->rchild);
                leftRotate(root);
            }
        }
    }
}

删除操作（笔者自行发挥）

删除节点分三种情况。
第1种被删除的节点是叶结点：直接删除，随着递归函数的系统栈的弹出，自底向上地更新祖先节点的高度，并检查祖先节点是否平衡。若不平衡，调整方案与插入操作时相同。
第2种被删的节点只有左子树或者右子树：用该节点唯一的子树代替该节点的位置。自底向上地更新祖先节点的高度，并检查祖先节点是否平衡并调整。
第3种被删的节点既有左子树又有右子树：将该节点的前驱或者后继（当左子树高度大于右子树时用前驱，当右子树高度大于等于左子树时用后继）的data与该节点交换（交换后，树还是平衡的），前驱或者后继的位置一定是第1种或第2种情况。然后对前驱或者后继节点进行删除操作（即调用deleteNode的函数进入第1种或第2种情况）。
在之前二叉查找树的deleteNode()代码基础上稍作修改得到以下

void deleteNode(node* &root, int x){
    if(root == NULL) return;
    if(root->data == x){
        if(root->lchild == NULL && root->rchild == NULL){ //情况1
            root == NULL;
        }else if(root->lchild != NULL && root->rchild != NULL){ //情况3
            if(getBalanceFactor(root) > 0){  //情况3:左子树高度大于右子树时用前驱
                node* pre = findMax(root->lchild);
                root->data = pre->data;
                deleteNode(root->lchild, pre->data); //因为前驱或者后继不一定为空树，前驱可能有左子树，后继可能有右子树
            }else{  //情况3:当右子树高度大于等于左子树时用后继
                node* pro = findMin(root->rchild);
                root->data = pro->data;
                deleteNode(root->rchild, pro->data);
            }      
        }else if(root->lchild != NULL){ //情况2
            root->data = root->lchild->data;
            // delete(root->lchild); 
            root->lchild = NULL;
        }else{ //情况2
            root->data = root->rchild->data;
            // delete(root->rchild); 
            root->rchild = NULL;
        }
    }else if(x < root->data){
        deleteNode(root->lchild, x); //删除左子树的节点，不平衡时只可能左子树比右子树低。
        updateHeight(root);
        if(getBalanceFactor(root) == -2){
            if(getBalanceFactor(root->rchild) == -1){
                leftRotate(root);
            }else if(getBalanceFactor(root->rchild) == 1){
                rightRotate(root->rchild);
                leftRotate(root);
            }
        }
    }else{
        deleteNode(root->rchild, x);
        updateHeight(root);
        if(getBalanceFactor(root) == 2){ //往左子树里插入元素，左子树高度增加,且左子树不可能平衡
            if(getBalanceFactor(root->lchild) == 1){
                rightRotate(root);
            }else if(getBalanceFactor(root->lchild) == -1){
                leftRotate(root->lchild);
                rightRotate(root);
            }
        } 
    }
}

9.6 并查集 Union-Find-Set

用一个数组即可实现 int father[N];
初始化: 令所有元素都是一个独立的集合，即父节点指向本身

for(int i=0; i<N; i++) father[i] = i;

查找根节点：可以用循环或者递归实现

int findFather(int x){
    if(father[x] == x) return x;
    else return findFather(father[x]);
}

合并

int union(int a, int b){
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA != faB) father[faA] = faB;
}

路径压缩：将所有节点都连接在根节点上，在查找时重连接

int findFather(int x){
    if(father[x] == x) return x;
    else{
         int Fa = findFather(father[x]);
         father[x] = Fa;
         return Fa;
     }
}

9.7 堆（完全二叉树）

以大顶堆为例
用一个数组从下标1开始保存。和下标为 i 的节点的子节点为 i 和 i+1
向下调整（下沉法）：将根节点与他的子结点对比，如果根节点子节点小，则与子节点中较大的一个交换位置，一直向下调整，直到不能调整。根结点的选取从下往上、从右往左。

int heap[1000];
void downAdjust(int low, int high){
    int root = low, child = low * 2;
    while(child <= high){
        if(child + 1 < high && heap[child] < heap[child+1]) child++;
        if(heap[root] < heap[child]){
            swap(heap[root], heap[child]);
            root = child;
            child = root * 2;
        }else{
            break;
        }
    }
}

建堆：对于有n个元素的堆，[1, floor(n/2)] 都是非叶子节点。从下往上、从右往左地调整

void create(int A[], int n){
    for(int i=0; i<n; i++) heap[i+1] = A[i];
    for(int i=n/2; i>=1; i--) downAdjust(i,n);
}

删除堆顶元素：用最后一个元素覆盖堆顶元素，堆的元素个数减1，然后向下调整堆顶元素

void deleteTop(int n){
    heap[1] = heap[n--];
    downAdjust(1,n);
}

增加新元素：将元素添加至最后，然后对他进行向上调整（上浮法） $O(logn)$

void upAdjust(int low, int high){
    int child = high, root = high/2;
    while(root >= 1){
        if(heap[child] > heap[root]){
            swap(heap[child], heap[root]);
            child = root;
            root = child/2;
        }else{
            break;
        }
    }
}

void insert(int x, int n){
    heap[++n] = x;
    upAdjust(1,n);
}

9.8 哈夫曼树

已知n个数，寻找一棵树，使得树的所有叶子节点的恰好为这n个数，并且使得这棵树的带权路径长度最小，这样的树被称为哈夫曼树。
构建过程：用一个优先队列保存所有的节点，每次选出权值最小的两个节点，将它们合并为父节点后送入优先队列。
哈夫曼编码：统计给定字符串中各个字符出现的次数，得到一段最短的01编码。
（以下代码为笔者自行发挥）

#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

struct node
{
    char chr;
    int times;
    string code = "";
    node *lchild, *rchild;
};

struct mycmp{
    bool operator () (node* a, node* b) {return a->times > b->times;}
};

node* newNode(char c, int val){
    node* p = new node;
    p->chr = c;
    p->times = val;
    p->lchild = NULL;
    p->rchild = NULL;
    return p;
}

vector<node*> Huffman_code;
bool cmp(node* a, node* b){return a->times > b->times;}
void Huffman_tree(string s){
    priority_queue<node*, vector<node*>, mycmp> q;
    map<char, int> alphas;
    for(int i=0; i<s.size(); i++) alphas[s[i]]++;
    for(auto it: alphas) q.push(newNode(it.first, it.second));
    
    while(q.size() != 1)
    {
        node* a = q.top(); q.pop();
        node* b = q.top(); q.pop();
        node* father = newNode((char)0, a->times + b->times);
        father->lchild = a;
        father->rchild = b;
        q.push(father);
    }
    queue<node*> q2;
    q2.push(q.top());
    while(q2.size() != 0){
        node* root = q2.front();
        q2.pop();
        if(root->lchild == NULL && root->rchild == NULL) Huffman_code.push_back(root);
        else{
            root->lchild->code = root->code + '0';
            root->rchild->code = root->code + '1';
            q2.push(root->lchild);
            q2.push(root->rchild);
        }
    }
    sort(Huffman_code.begin(),Huffman_code.end(),cmp); // 按出现次数降序排列
}


string Huffman_encode(string s){
    string str_code = "";
    for(auto it1: s){
        for(auto it2: Huffman_code){
            if(it2->chr == it1){
                str_code += it2->code;
                break;
            }
        }
    }
    return str_code;
}

string Huffman_decode(string s){
    string str = "";
    int p = 0;
    while(p < s.size()){
        string code;
        for(auto it : Huffman_code){
            if(it->code == s.substr(p,(it->code).size())){
                p += (it->code).size();
                str += it->chr;
                break;
            }
        }
    }
    return str;
}

int main(){
    string s;
    getline(cin,s);
    Huffman_tree(s); // 得到Huffman tree，编码关系保存在Huffman_code中
    for(auto it: Huffman_code) cout<<it->chr<<":"<<it->code<<endl;

    string encode = Huffman_encode(s); //编码 
    cout<<"After Encode: "<<encode<<endl;
    cout<<"After Decode: "<<Huffman_decode(encode)<<endl; //解码
    getchar();
    return 0;
}

10 图算法专题

10.1 图的相关定义

有向图和无向图
顶点的度，出度和入度
点和边的权值，点权和边权

10.2 图的储存

邻接矩阵：矩阵中保存权值
邻接表：每个点保存一个邻接表，用链表或 vector，每个元素包含指向的点和权值
无向图：连通分量；有向图：强连通分量

10.3 图的遍历

DFS：栈、递归函数
BFS：队列，可以用node作为元素，node中保存深度。

10.4 最短路径

Dijkstra算法

只能解决所有边的权重都是非负数的情况。如果边的权重出现负数，最好使用SPFA算法
处理无向边时，只需把无向边看作双向的有向边。
统计已访问的点(vis)到其他各个可到达点的最短距离d[i]，将最近的一个点设为已访问，并遍历更新该点直接连接的点到原点的最短距离。每重复一次这样的过程，已访问的点个数增加1，重复n次这样的过程即可访问到所有n个点
以邻接表图为例

struct node{int v, dis;};

const int inf = 0x3fffffff;
vector<node> Adj[1000];
int n; //点的个数
int d[1000]; // 到i的最短路径
int pre[1000]; // 记录前驱节点
bool vis[1000] = {false};

void Dijkstra(int s){
    fill(d, d+n, inf);
    for(int i=0; i<n; i++) pre[i] = i;
    d[s] = 0;
    for(int i=0; i<n; i++){
        int min_dis = inf, min_p = -1;
        for(int j=0; j<n; j++){
            if(!vis[j] && min_dis > d[j]){
                min_dis = d[j];
                min_p = j;      
            }  
        }
        if(min_p == -1) return;
        vis[min_p] = true;
        for(auto it: Adj[min_p]){
            int v = it.v;
            if(!vis[v] && d[min_p]+it.dis < d[v]){
                d[v] = d[min_p]+it.dis;
                pre[v] = min_p;
            }
        }
    }
}

用递归函数输出最短路径

void print_path(int s, int v){
    if(v == s){
        printf("%d",s);
        return;
    }
    print_path(s, pre[v]);
    printf("->%d",v);
}

在接受多条最短路径的情况下,记录前驱节点的pre数组可以改为vector<int> pre[1000];。遍历所有最短路径，可以找出一条使第二标尺最优的路径。

10.4.2 Bellman-Ford算法和 SPFA算法

零环、正环、负环：负环的存在会影响最短路径的求解，若遭遇负环BF算法返回false。
BF算法思路：每轮操作遍历所有u到v的边，如果走这条边，可以使v到原点的距离更短，则更新v到原点的距离d[v]，这样的一次更新称作松弛操作。可以证明进行n-1轮这样的操作一定能得到原点到所有点的最短路径。但是并不一定需要进行n-1轮操作，在某一轮操作后，发现所有的边都没有被松弛，则说明数组d中的所有的值都已经达到最优，不需要继续。

struct node{
    int v, dis;
    node(int _v, int _dis):v(_v), dis(_dis){}
};
const int inf = 0x3fffffff;
vector<node> Adj[1000];
int n; //点的个数
int d[1000]; // 到i的最短路径

bool Bellman(int s){
    fill(d, d+n, inf);
    d[s] = 0;
    for(int i=0; i<n-1; i++){
        bool flag = true;
        for(int u=0; u<n; u++){
            for(auto it: Adj[u]){
                if(d[it.v] > d[u] + it.dis){
                    d[it.v] = d[u] + it.dis;
                    flag = false;
                }
            }
        }
        if(flag) break;
    }
    // 检测是否存在负环
    for(int u=0; u<n; u++){
        for(auto it: Adj[u]){
            if(d[it.v] > d[u] + it.dis) return false;
        }
    }
    return true;
}

我们注意到只有当某个顶点u的d[u]值变化时，从它出发的边的邻接点v的d[v]值才有可能被改变。可以进行优化：建立一个队列，每次将队首的u取出，然后对从u出发的所有边进行松弛操作。如果成功松弛，使得d[v]获得更优的值，并且v不在当前队列中，则将v加入队列。
由每个点加入队列的次数(注意,不是松弛的次数)，可以判断是否存在负环。每个点加入队列的次数都不应超过n-1。

struct node{
    int v, dis;
    node(int _v, int _dis):v(_v), dis(_dis){}
};
const int inf = 0x3fffffff;
vector<node> Adj[1000];
int n; //点的个数
int d[1000]; // 到i的最短路径
int num[1000]; // 统计入队次数
bool inq[1000]; // 标志是否在队列中

bool SPFA(int s){
    fill(num, num+n, 0);
    fill(inq, inq+n, false);
    fill(d, d+n, inf);
    queue<int> Q;
    Q.push(s);
    d[s] = 0;
    inq[s] = true;
    num[s]++;
    while(!Q.empty()){
        int p = Q.front();
        Q.pop();
        inq[p] = false;
        for(auto it: Adj[p]){
            if(d[it.v] > d[p]+it.dis){
                d[it.v] = d[p]+it.dis;
                if(!inq[p]){
                    Q.push(it.v);
                    inq[it.v] = true;
                    num[it.v]++;
                    if(num[it.v] > n-1) return false;
                }
            }
        }
    }
    return true;
}

SPFA十分灵活，可以根据具体场景的不同进行调整。上述代码中的队列可以替换为优先队列，以加快速度。或者替换为双端队列（deque），使用SLF和LLL优化，提高至少50%效率。上述代码给出的是BFS版本，如果将队列替换成栈，则可以实现DFS版本的SPFA，对判断环有奇效。

10.4.3 Floyd算法 $O(n^3)$

用于解决全源最短路径问题。
如果以k为中介点，可以使顶点 i 到顶点 j 的当前最短距离缩短，则更新 i 到 j 的最短距离。对每个顶点都作为中介点检查一遍。
用邻接矩阵保存距离

const int inf = 0x3fffffff;
const int maxn = 200;
int n; //点的个数
int m; //边的条数
int dis[maxn][maxn]; // 到i的最短路径

void init_dis(){ // 测试用例子
    n = 6;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++) dis[i][j] = inf;
    }
    for(int i=0; i<n; i++) dis[i][i] = 0;
    dis[0][1] = 1; dis[0][3] = 4; dis[0][4] = 4;
    dis[1][3] = 2;
    dis[2][5] = 1;
    dis[3][4] = 3; dis[3][2] = 2;
    dis[4][5] = 3;
}

void Floyd(){
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(dis[i][k] != inf && dis[k][j] != inf && dis[i][k]+dis[k][j] < dis[i][j]){
                    dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
    }
}

10.5 最小生成树

性质：
1. 最小生成树中包含一张无向图中所有的点，树的边都来自于图的边，而且保证树中所有边的权重之和最小。
2. 最小生成树的边数等于顶点数减一，且树内一定不会有环。
3. 最小生成树可以不唯一，但其边权之和一定唯一。
4. 最小生成树是在无向图上生成的，因此其根节点可以是这棵树上的任意一个节点。

10.5.2 Prim算法

Prim算法和Dijkstra算法思路几乎完全相同，仅有d[i] 的含义不同。Dijkstra算法中 d 存放所有点到原点的当前最短距离，Prim算法中 d 存放所有点到已访问点集合 S 的最短距离。

struct node{
    int v, dis;
    node(int _v, int _dis):v(_v), dis(_dis){}
};

const int maxn = 1000; 
const int inf = 0x3fffffff;
vector<node> Adj[maxn];
int d[maxn];
bool vis[maxn];
int father[maxn];
int n = 6;

int Prim(int s){
    int weight = 0;
    fill(d, d+n, inf);
    fill(vis, vis+n, false);
    for(int i=0; i<n; i++) father[i] = i;
    d[s] = 0;
    for(int i=0; i<n; i++){
        int min_d = inf, min_p = -1; // 有可能找不到距离小于inf的点，因为剩下的点与现在的已访问集合不连通 
        for(int j=0; j<n; j++){
            if(!vis[j] && d[j] < min_d){
                min_d = d[j];
                min_p = j;
            }
        }
        if(min_p == -1) return -1;
        vis[min_p] = true;
        weight += min_d;
        for(auto it: Adj[min_p]){
            if(!vis[it.v] && d[it.v] > it.dis){
                d[it.v] = it.dis;
                father[it.v] = min_p;
            }
        }
    }
    return weight;
}

void print_tree(int s){
    for(int i=0; i<n; i++){
        if(father[i] != i) printf("%d -> %d\n", father[i], i);
    }
}

10.5.3 Kruskal算法

采用边贪心的策略
基本步骤：
1. 对所有边按权值从小到大排序
2. 从小到大的检测这些边，如果当前检测的边连接的两个顶点在两个不同的连通块中，则将这条边添加进最小生成树，否则舍弃
3. 重复执行步骤2，直到最小生成树的边数为n-1，若小于n-1则说明这张图不是全连通的
用并查集判断两个顶点是否在同一连通块中

const int maxn = 1000;
struct edge{
    int u, v, dis;
    edge(){}  // !!!数组提前分配空间时需要调用无参数的构造函数
    edge(int _u, int _v, int _dis): u(_u), v(_v), dis(_dis){}
}edges[maxn];
bool cmp(edge a, edge b){return a.dis < b.dis;}

int n;
int father[maxn];
int find_father(int a){
    if(father[a] == a) return a;
    return find_father(father[a]);
}

int kruskal(int n, int m){
    int ans = 0, num_edge = 0;
    for(int i=0; i<n; i++) father[i] = i;
    sort(edges, edges+m, cmp);
    for(int i=0; i<m; i++){
        int fa_u = find_father(edges[i].u), fa_v = find_father(edges[i].v);
        // printf("%d -- %d\n", edges[i].u, edges[i].v);
        if(fa_u != fa_v){
            ans += edges[i].dis;
            num_edge++;
            father[fa_v] = fa_u;
            tree_edge.push_back(edges[i]);
        }
        if(num_edge == n-1) break;
    }
    if(num_edge < n-1) return -1;  //这张图并非全连通
    else return ans;
}

PS: 为一个结构体提前分配数组空间，需要该结构体有一个无参数的构造函数

如果是稠密图（边多）选择Prim算法，如果是稀疏图（边少）选择Kruskal算法

10.6 拓扑排序

基本步骤：
1. 定义一个队列q，把所有入度为0的节点加入队列
2. 取出队首节点并输出，然后删去所有从它出发的边，并令这些边到达点的入度减1
3. 若到达点的入度减为0，则让该点进入队列。重复第2步操作直至对列元素个数为0

const int maxn = 1000;
vector<int> Adj[maxn];
int inDegree[maxn];
int n; // 顶点数
vector<int> sorted_series;

bool topologialSort(){
    fill(inDegree, inDegree+n, 0);
    for(int i=0; i<n; i++){
        for(auto it: Adj[i]) inDegree[it]++;
    }
    int num = 0;
    queue<int> q;
    for(int i=0; i<n; i++){
        if(!inDegree[i]) q.push(i);
    }
    while(!q.empty()){
        int now = q.front();
        q.pop();
        sorted_series.push_back(now);
        num++;
        for(auto it: Adj[now]){
            inDegree[it]--;
            if(!inDegree[it]) q.push(it);
        }
    }
    if(num != n) return false;
    else return true;
}

void print_sorted(){
    for(auto it: sorted_series) printf("%d ->",it);
}

10.7 关键路径

10.7.1 AOV网和 AOE网

顶点活动AOV：Activity on vertex, 用顶点表示活动, 用边表示顶点及优先级关系的有向图
边活动AOE：Activity on edge，用代权的边集表示活动，用顶点表示“事件“（这里的事件仅代表一种中介状态）的有向图。
AOE图有多个源点和汇点时，可以引入超级源点和超级汇点，超级源点和超级汇点到源点和汇点的边的权值为0。
将AOV网中每个顶点拆成两个顶点，两个顶点由带权值的边连接，可将AOV网转化为AOE网。
定义：AOE网中的最长路径被称为关键路径，把关键路径上的活动称为关键活动，显然关键活动会影响整个工程的进度。

10.7.2 最长路径

将所有边权乘- 1 后用最短路径中的Bellman-Ford的算法或SPFA算法求最短路径。图中如果有正环，那么最长路径不存在。

10.7.3 关键路径

求解有向无环图中最长路径的方法
算法思路：
1. 活动的最早开始时间和最迟开始时间可以由活动两侧的事件（节点）的最早发生时间和最迟发生时间确定。
2. 而事件 j 的最早发生时间由它的一个或多个前驱节点 i 的最早发生时间加上事件 i 的时长决定（取最大值）。
3. 使用拓扑排序可以保证在访问某个节点时，它的前驱节点都已经访问完毕。
4. 因为由前驱节点找到后继节点容易，而反之很难。所以一个比较好的策略是：在拓扑排序访问到某个节点时，去更新其所有后继节点的最早发生时间。
5. 同理，为了得到事件的最迟发生时间，需要由下一事件推出前一事件的最迟发生时间。在访问某个节点时需要保证，它的后继节点都已经访问完毕，利用逆拓扑序来保证（具体实现方式是：在求拓扑序时入栈，一个个出栈得到逆拓扑序）。
6. 事件最早发生时间数组 ve[ ] 用0初始化，事件最迟发生时间数组 vl[ ] 用 ve[ ] 中的最大值初始化。

struct edge{
    int v, w;
    edge();
    edge(int _v, int _w): v(_v), w(_w){}
};

const int maxn = 1000;
vector<edge> Adj[maxn];
int inDegree[maxn];
int n; // 顶点数
vector<int> sorted_series;

int ve[maxn];
int vl[maxn];
stack<int> TopoOrder; // 为了方便得到逆拓扑序

bool topologicalSort(){
    fill(inDegree, inDegree+n, 0);
    fill(ve, ve+n, 0);
    queue<int> q;
    for(int i=0; i<n; i++){
        for(auto it: Adj[i]) inDegree[it.v]++;
    }
    for(int i=0; i<n; i++){
        if(!inDegree[i]) q.push(i);
    }
    while(!q.empty()){
        int p = q.front();
        q.pop();
        TopoOrder.push(p);
        for(auto it: Adj[p]){
            inDegree[it.v]--;
            if(!inDegree[it.v]) q.push(it.v);
            if(ve[it.v] < ve[p] + it.w) ve[it.v] = ve[p] + it.w;
        }
    }
    if(TopoOrder.size() != n) return false;
    else return true;
}

int critical_path(){
    if(!topologicalSort()) return -1;

    // 对于多个汇点的图，栈顶事件不一定是最晚发生的事件
    int maxve = 0;
    for(int i=0; i<n; i++) if(ve[i] > maxve) maxve = ve[i];
    fill(vl, vl+n, maxve); //用最后一个事件的最早发生时间初始化所有事件的最迟发生时间
    while(!TopoOrder.empty()){
        int u = TopoOrder.top();
        TopoOrder.pop();
        for(auto it: Adj[u]){
            if(vl[it.v] - it.w < vl[u]) vl[u] = vl[it.v] - it.w;
        }
    }

    for(int u=0; u<n; u++){
        for(auto it: Adj[u]){
            int v = it.v, w = it.w;
            int earliest = ve[u], last = vl[v] - w;
            if(earliest == last) printf("%d -> %d\n", u, v); 
        }
    }
    return maxve;
}

11 动态规划专题（Dynamic programming）

定义：用来解决一类最优化问题的算法思想
递归写法：又称作记忆化搜索，当下次再碰到需要计算相同的内容时，就直接使用上次计算的结果。
递推写法：从边界开始向上寻找问题的解，通过状态转移方程将边界量扩散到整个子问题集。
1. 分治与动态规划：分解出的子问题是不重叠的，动态规划分解出的子问题有重叠。分治法解决的问题不一定是最优化问题，而动态规划解决的问题一定是对话问题。
2. 贪心与动态规划：都要求原问题必须拥有最优子结构。贪心并不等待子问题求解完毕后再选择使用哪一个，而是通过一种策略直接选择一个子问题去求解，没被选择的子问题就直接放弃，总是在上一步选择的基础上继续选择；这种局部最优选择的正确性需要用归纳法证明。动态规划从边界开始向上得到目标问题的解，总是会考虑所有子问题，并选择继承能得到最优结果的那个，对暂时没被继承的子问题，后期可能会再次考虑到他们。

10.2 最大连续子序列和 $O(n)$

给定一个数字序列 a[n]，输出连续子序列的最大和。
考虑以 a[i] 结尾的连续序列的最大和（记为dp[i]），只有以下两种情况：
1. 这个最大和的连续序列只有一个元素，就是 a[i]
2. 以 a[i-1] 为结尾的子序列的最大和，加上 a[i]。dp[i-1] + a[i]
n次计算max(a[i], dp[i-1]+a[i])即可得到完整的dp序列，其中最大值是我们想要的连续子序列的最大和

const int maxn = 10000;
int sequence[maxn];
int n;

int max_subsequence(){
    int dp[maxn];
    dp[0] = sequence[0];
    for(int i=1; i<n; i++) dp[i] = max(sequence[i], dp[i-1]+sequence[i]);
    int max_sub = dp[0];
    for(int i=1; i<n; i++) if(dp[i] > max_sub) max_sub = dp[i];
    return max_sub;
}

10.3 最长不下降子序列（LIS） $O(n^2)$

在一个数字序列中找到一个最长子序列（可以不连续）使得这个子序列也是不下降的
考虑以 a[i] 结尾的最长不下降子序列元素个数（记为dp[i]），只有以下两种情况：
1. a[i] 之前的元素都比他大，则dp[i] = 1
2. a[i] 之前存在比他小的元素 a[j]，则 dp[i] 至少为 dp[j] + 1

const int maxn = 10000;
int sequence[maxn];
int n;

int LIS(){
    int dp[maxn];
    fill(dp, dp+n, 1);
    for(int i=1; i<n; i++){
        for(int j=0; j<i; j++){
            if(sequence[j] <= sequence[i] && dp[j]+1 > dp[i]) dp[i] = dp[j]+1;
        }
    }
    return dp[n-1];
}

10.4 最长公共子序列（LCS） $O(mn)$

给定两个字符串 A 和 B，求一个字符串使得这个字符串是 A 和 B 的最长公共部分（可以不连续，但顺序不变）
算法思路：递推思想
1. 用dp[i][j]表示字符串A的0到 i 的子串和字符串B的0到 j 的子串的最长公共子序列
2. 若A[i] == B[i]，则最长公共子序列加一dp[i][j] = dp[i-1][j-1] + 1
3. 若A[i] != B[i]，则dp[i][j]取max(dp[i-1][j], dp[i][j-1])
4. 两字符串第一位是边界，dp[0][0]前面再没有元素，所以我们做了个padding，将A、B都向后移一位，设定任意的dp[0][i]、dp[i][0]都为0，现在两字符串首位是dp[1][1]

const int maxn = 100; 
string A, B;
int LCS(){
    int dp[maxn][maxn]; //小心爆栈，2MB，最多开721*721个int，2MB/4B = 2^19 = 524288个int
    A = " " + A; // padding
    B = " " + B;
    int m = A.size(), n = B.size();
    // 设置边界条件
    for(int i=0; i<n; i++) dp[0][i] = 0;
    for(int j=0; j<m; j++) dp[j][0] = 0;
    for(int i=1; i<m; i++){
        for(int j=1; j<n; j++){
            if(A[i] == B[j]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m-1][n-1];
}

11.5 最长回文子串

给定一个字符串s，求s的最长回文子串长度。
书上给的代码，两重循环，第1层循环是子串的长度从3开始，第2层循环在原字符串内按子串长度扫描。

const int maxn = 1000; 
string s;
bool dp[maxn][maxn];

int max_Palindrome(){
    int max_len = 1;
    int len = s.size();
    for(int i=0; i<len; i++){
        for(int j=0; j<=i; j++) dp[i][j] = false;
    }
    //设置边界
    for(int i=0; i<len; i++){
        dp[i][i] = true;
        if(i < len-1){
            dp[i][i+1] = 1;
            max_len = 2;
        }
    }
    for(int L=3; L<len; L++){
        for(int i=0; i+L-1 < len; i++){
            int j = i+L-1;
            if(s[i] == s[j] && dp[i+1][j-1]){
                dp[i][j] = true;
                max_len = L;
            }
        }
    }
    return max_len;
}

10.6 DAG（有向无环图）最长路

用数组dp[i] 保存从 i 号顶点出发能获得的最长路径长度
需要按照逆拓扑序的顺序求解dp数组，或者使用递归的方法
不妨初始化整个dp数组为0

struct node{
    int v, dis;
    node(int _v, int _dis):v(_v), dis(_dis){}
};

vector<node> Adj[1000];
int n; //点的个数
int dp[1000];
int choice[1000]; 

int DP(int i){
    if(dp[i] > 0) return dp[i];
    for(auto it: Adj[i]){
        int temp = DP(it.v) + it.dis;
        if(temp > dp[i]){
            dp[i] = temp;
            choice[i] = it.v;
        }
    }
    return dp[i];
}

void print_path(int i){
    printf("%d",i);
    while (choice[i] != -1)
    {   
        i = choice[i];
        printf(" -> %d", i);
    } 
}

固定终点,求最长路径长度。

int dp[1000];
bool vis[1000]; 

int DP(int i){
    if(vis[i]) return dp[i];
    vis[i] = true;
    for(auto it: Adj[i]) dp[i] = max(dp[i], DP(it.v)+it.dis);
    return dp[i];
}

11.7.2 01背包问题

分治

dp[i][v] 保存在背包容量剩余v时装入前 i 件物品时，所能获得的最大价值。
边界条件是 i = 0 或 v = 0，此时dp为0
思路：
1. 不放第 i 件物品时，问题转化为前 i-1 件物品恰好装入容量为v的背包中所能获得的最大价值
2. 若放第 i 件物品，那么问题转化为前 i-1 件物品恰好装入容量为 v - w[i] 的背包中所能获得的最大价值。
状态转移方程：dp[i][v] = max(dp[i-1][v], dp[i-1][v-w[i]] + c[i]);

const int maxi = 100, maxv = 100;
int dp[maxi][maxv];
int c[maxi], w[maxi];
int totali, totalw;

int bag01(){
    for(int i=0; i<=totali; i++) dp[i][0] = 0;
    for(int v=0; v<=totalw; v++) dp[0][v] = 0;
    for(int i=1; i<=totali; i++){
        for(int v=w[i]; v<=totalw; v++){
            dp[i][v] = max(dp[i-1][v], dp[i-1][v-w[i]] + c[i]);
        }
    }
    return dp[totali][totalw];
}

int bag01_optimized(){  // 用滚动数组优化减少空间复杂度
    int dp_optimized[maxv];
    for(int v=0; v<=totalw; v++) dp_optimized[v] = 0;
    for(int i=1; i<=totali; i++){
        for(int v=totalw; v>=w[i]; v--) dp_optimized[v] = max(dp_optimized[v], dp_optimized[v-w[i]] + c[i]);
    }
    return dp_optimized[totalw];
}

11.7.3 完全背包问题

与01背包的区别在于每种物体有无穷多件。
这个问题之前是用贪心算法做的，总是先放入单位重量价值更高的物品
同样，dp[i][v] 保存在背包容量剩余v时装入前 i 件物品时，所能获得的最大价值。
边界条件是 i = 0 或 v = 0，此时dp为0
思路：
1. 不放第 i 件物品时，问题转化为前 i-1 件物品恰好装入容量为v的背包中所能获得的最大价值
2. 若放第 i 件物品，而第 i 件物品可以放任意件，那么问题转化为前 i 件物品恰好装入容量为 v - w[i] 的背包中所能获得的最大价值。因为可能存在这样的过程 dp[i][v-w[i]] -> dp[i][v]，因为又装入了一件 i 物品
完全背包状态转移方程：dp[i][v] = max(dp[i-1][v], dp[i][v-w[i]] + c[i]);
相比01背包问题代码只需稍作修改，从逆向枚举改为正向枚举。因为可以保证计算 dp[i][v] 时，已经完成 dp[i][v-w[i]] 的计算

const int maxi = 100, maxv = 100;
int dp[maxi][maxv];
int c[maxi], w[maxi];
int totali, totalw;

int bag01(){
    for(int i=0; i<=totali; i++) dp[i][0] = 0;
    for(int v=0; v<=totalw; v++) dp[0][v] = 0;
    for(int i=1; i<=totali; i++){
        for(int v=w[i]; v<=totalw; v++){
            dp[i][v] = max(dp[i-1][v], dp[i][v-w[i]] + c[i]);
        }
    }
    return dp[totali][totalw];
}

int bag01_optimized(){  // 用滚动数组优化减少空间复杂度
    int dp_optimized[maxv];
    for(int v=0; v<=totalw; v++) dp_optimized[v] = 0;
    for(int i=1; i<=totali; i++){
        for(int v=w[i]; v<=totalw; v++) dp_optimized[v] = max(dp_optimized[v], dp_optimized[v-w[i]] + c[i]);
    }
    return dp_optimized[totalw];
}

12 字符串专题

12. 1 字符串hash进阶

最简单的方法是将只包含大写字母的字符串直接转化为26进制，一个字符串对应一个整数 $H[i] = H[i-1]\times26+index(str[i])$
为了避免产生的整数过大的问题，一般我们会舍弃一些唯一性，对产生的结果取模。可以证明把进制数p设置为 $10^7$ 级别的素数(10000019)，把 $mod$ 设置为 $10^9$ 级别的素数(1000000007)，很少发生唯一性冲突。

const int p = 10000019;
const int MOD = 1000000007;
const int max_len = 1000;
long long all_H[max_len];
long long StrHash(string s){
    long long H = 0;
    for(int i=0; i<s.size(); i++){
        H = (H * p + (int)s[i] - (int)'A') % MOD; //(int)s[i] - (int)'A'可能是负数
        all_H[i] = H;
    }
    return H;
}

字符串s的从 i 到 j 位的子串的hash值，可以由从0到 j 位和 0 到 i-1 位的子串的哈希值推导出来，在一些问题中可以避免重复计算。因为小括号内计算结果可能为负数，所以需要进行一系列的取余计算
$H[i...j] = ((H[j]-H[i-1]*p^{j-i+1})\%MOD+MOD)\%MOD$

long long powP[max_len];
void init(int len){
    powP[0] = 1;
    for(int i=1; i<=len; i++) powP[i] = (powP[i-1]*p) % MOD;
}
long long SubStrHash(int i, int j){
    if(!i) return ((all_H[j] - all_H[i-1] * powP[j-1+1]) % MOD + MOD)% MOD;
    else return all_H[j];
}

用字符串hash + 二分的思路解决最长回文子串问题：
1. 若回文串长度是奇数：枚举回文中心 i 和二分子串的半径k，判断[i-k, i] 和 [i, i+k] 子串是否相反（左子串，反向求hash）
2. 若回文串长度是偶数：枚举回文中心 i 和二分子串的半径k，判断[i-k+1, i] 和 [i+1, i+k] 子串是否相反（左子串，反向求hash）

12.2 KMP算法

字符串的匹配问题，text 文本串和 pattern 模式串。判断pattern是否是text的子串。

12.2.1 next数组

next[i] 表示子串 s[0..i] 的前缀 s[0..k] 等于后缀 s[i-k..i] 的最大k
next[i]可以由递推的方法由 next[0]~next[i-1] 求出
引用：关于递推式理解

套娃：增长一位后如何比较

const int maxn = 1000;
int Next[maxn];
void getNext(string s){
    int n = s.size();
    Next[0] = -1;
    int j = -1;
    for(int i=1; i<n; i++){
        while(j != -1 && s[i] != s[j+1]) j = Next[j];
        if(s[i] == s[j+1]) j++; // 第一位与倒数第一位相等时，若不等则不存在相同前后缀
        Next[i] = j;
    }    
}

10.2.2 KMP算法 $O(m+n)$

i 指向text文本串中的一个位置，j 指向pattern模式串中的一个位置
next数组的含义就是当 j+1 位匹配失败时，j 应该退回到的位置
算法思路：
1. 初始化 j = -1，表示pattern当前已被匹配的最后位
2. 让i 遍历文本串text，对每个 i 执行③④步来试图匹配 text[i] 和 pattern[j+1]
3. 不断令 j = Next[j]，直到 j 回退到 -1 或 text[i] = pattern[j+1] 成立
4. 如果 text[i] = pattern[j+1] ，则令 j++。如果 j 达到 m-1，则说明pattern是text的子串

bool KMP(string text, string pattern){
    int n = text.size(), m = pattern.size();
    getNext(pattern);
    int j = -1;
    for(int i=0; i<n; i++){
        while(j != -1 && text[i] != pattern[j+1]) j = Next[j];
        if(text[i] == pattern[j+1]) j++;
        if(j == m-1) return true;
    }
    return false;
}

还可以实现统计 text 字符串中 pattern 出现的次数

int num_KMP(string text, string pattern){
    int n = text.size(), m = pattern.size();
    getNext(pattern);
    int j = -1, ans = 0;
    for(int i=0; i<n; i++){
        while(j != -1 && text[i] != pattern[j+1]) j = Next[j];
        if(text[i] == pattern[j+1]) j++;
        if(j == m-1){
            ans++;
            j = Next[j];
        }
    }
    return ans;
}

然而kmp算法还可以优化，因为我们发现如果回退后的对应位置（next[j]）上的字符与回退前对应位置（j）的字符相同时，即 pattern[j] == pattern[Next[j]]，必然还会失配。所以我们优化next数组为nextval数组，它的含义可以理解为当前模式串pattern的 j+1 位发生失配时，j 应当退回到最佳位置，对next生成函数操作修改

int nextval[maxn];
void getNextval(string s){
    int n = s.size();
    nextval[0] = -1;
    int j = -1;
    for(int i=1; i<n; i++){
        while(j != -1 && s[i] != s[j+1]) j = nextval[j];
        if(s[i] == s[j+1]) j++;
        if(j == -1 || s[i+1] != s[j+1]){
            nextval[i] = j;
        }else{
            nextval[i] = nextval[j];
        }
    }    
}
bool fast_KMP(string text, string pattern){
    int n = text.size(), m = pattern.size();
    getNextval(pattern);
    int j = -1;
    for(int i=0; i<n; i++){
        while(j != -1 && text[i] != pattern[j+1]) j = nextval[j];
        if(text[i] == pattern[j+1]) j++;
        if(j == m-1) return true;
    }
    return false;
}

13 专题扩展

13.1 分块思想

给定一个整数序列，查询序列中第K大的元素
类似储存管理系统中的页表思想，分级查询。将有n个元素的序列分为块，每一块中有个元素。
举例说明: 对一个拥有个不超过的非负整数的序列，可划分为317块，每一块中有316个元素。定义一个统计数组block[317]，和一个hash数组table[100001]
1. 新增元素 x 时，block[x/316]++, hash[x]++
2. 查询第K大的元素时，从小到大枚举块号，利用block数组累加得到前 i-1 块中存在元素的总个数，若再加上block[i] 恰好大于等于K，则进入第 i 块，逐个累加，直至第K大个数，时间复杂度是 $O(\sqrt{n}+\sqrt{n})$

13.2 树状数组(BIT)

13.2.1 lowbit运算

lowbit(x) = x & (-x) 表示取x的二进制最右边的1和它右边所有0。也可以理解为能整除x的最大2的次幂

13.2.2 树状数组及其应用

树状树组BIT与sum[]数组类似，不过它的第 i 位存放的是在整数序列 i 号位之前的lowbit(i)个整数之和

树状数组定义图
构建树状数组的函数、返回前x个整数之和的函数、将第x个整数加v后更新树状数组的函数：

const int maxn = 10000;
int c[maxn];
vector<int> A;
#define lowbit(i) ((i)&(-i))

void get_c(){
    int n = A.size(); //A的第0位保留，设为-1
    for(int i=1; i<n; i++){
        for(int j=i; j>i-lowbit(i); j--) c[i] += A[j];
    }
}

int getsum(int x){
    int sum = 0;
    for(int i=x; i>0; i-=lowbit(i)) sum += c[i];
    return sum;
}

// 将第x个整数加v后。
void update(int x, int v){
    int n = A.size();
    for(int i=x; i<=n; i+=lowbit(i)) c[i] += v;
}

树状数组可以解决如下问题：给定一个有n个正整数的序列A，对序列中每个数求出序列中它左边比它小的数的个数

#include<cstdlib>
#include<vector>
#include<ctime>
using namespace std;

const int maxn = 10000;
int c[maxn];
vector<int> A;
#define lowbit(i) ((i)&(-i))

int getsum(int x){
    int sum = 0;
    for(int i=x; i>0; i-=lowbit(i)) sum += c[i];
    return sum;
}

// 将第x个整数加v后。
void update(int x, int v){
    int n = maxn;
    for(int i=x; i<=n; i+=lowbit(i)) c[i] += v;
}

int main(){
    int n;
    srand(time(NULL));
    for(int i=0; i<10; i++) A.push_back(rand()%100);
    n = A.size();
    memset(c, 0, sizeof(c)); // from <cstring>
    for(int i=0; i<n; i++){
        update(A[i], 1);
        printf("%d: %d\n",i, getsum(A[i]-1));
    }
    for(auto it: A) printf("%d ",it);
}

当A[i]非常大时，可以用到离散化的技巧，将原始元素映射为一个符合要求的序号

完结撒花

李方楠
2020年8月14日

《算法笔记》（胡凡 编）学习笔记