4 算法初步

4.2 散列

1. 線性探查法：沖突后檢查下一位。

2. 平方探查法：沖突后依次檢查 。超出散列表長度，取余。

3. 鏈地址法：每一位散列值上用鏈表存放數(shù)據(jù)。

字符串hash：26進(jìn)制整數(shù)。

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

4.4 貪心

數(shù)學(xué)歸納地一步步推出最優(yōu)解。 區(qū)間貪心

4.5 二分

4.5.1 二分查找 O(logn)

• 查找滿足特定條件的值
• 求的近似值
• 快速冪：冪指數(shù)為奇數(shù)時(shí)二分，冪指數(shù)為偶數(shù)時(shí)減1；快速傅里葉變換的思想。

PS：用位運(yùn)算判斷奇偶要快一點(diǎn)，(a & 1) 代替(a%2 == 1)

4.6 two pointers

1. 2路歸并排序：

• 遞歸實(shí)現(xiàn)：實(shí)現(xiàn)merge()和mergesort()兩個(gè)函數(shù)。

• 非遞歸實(shí)現(xiàn)

  
  
  歸并

2. 快排 和 隨機(jī)快排：隨機(jī)快排，不再像快排一樣直接選取第一位為標(biāo)準(zhǔn)，而是隨機(jī)選取一個(gè)位置的數(shù)與第一位交換，然后進(jìn)行快排的partition()操作。

4.7 其他高效技巧和算法

打表：空間換時(shí)間，將所有可能的結(jié)果事先計(jì)算出來保存，后面需要用到時(shí)查表得到。

4.7.3 隨機(jī)選擇算法

• 求一數(shù)組里面第K大的數(shù)：利用隨機(jī)快排算法，隨機(jī)選擇中值，每次partition后，中值前的數(shù)都比它小，中值后的數(shù)都比他大，判斷中值下標(biāo)是否為K。最壞情況，最好情況
• 對比第K個(gè)小或者大的數(shù)的順序不關(guān)心，省到極致。

5 數(shù)學(xué)問題

5.2 最大公因數(shù)gcd(a,b)，輾轉(zhuǎn)相除法。最小公倍數(shù)lcm(a,b) = a*b / gcd(a,b)

5.6 實(shí)現(xiàn)大整數(shù)加減乘除

• struct保存大整數(shù)
• 減法注意去除高位的0，修改大整數(shù)的len
• 乘法一次進(jìn)位可能有多位，注意最終的進(jìn)位處理
• 先令商長度和被除數(shù)相等，最后刪去商開頭的0

6 STL庫介紹

6.1 vector

1. 通過下標(biāo) 或 迭代器訪問
vector<int>::iterator it;

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

3. erase可刪除單個(gè)元素，或區(qū)間內(nèi)元素（用iter指示）
vec.erase(iter);
vec.erase(vec.begin(), vec.end()); //不刪除第二個(gè)參數(shù)指向的元素

6.2 set

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

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

3. erase可刪除單個(gè)元素，或區(qū)間內(nèi)元素（用iter指示）
st.erase(value); //與vector不同
st.erase(st.begin(), st.end()); //不刪除第二個(gè)參數(shù)指向的元素

6.3 string

1. 通過下標(biāo) 或 迭代器訪問
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的下標(biāo)3位置處插入字符串“pop”，其他字符順序后移。
str.insert(it, it1, it2); //it為源字符串插入位置，it2、it3為待插入字符串首、尾+1（例如：str2.end()） 

6. erase可刪除單個(gè)元素，或區(qū)間內(nèi)元素（用iter指示）
str.erase(iter);
str.erase(str.begin(), str.end()); //不刪除第二個(gè)參數(shù)指向的元素
str.erase(pos, length); //pos為下標(biāo)

7. str.find(str2)返回子串在str中對應(yīng)起始位置下標(biāo)。失配時(shí)返回 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刪除單個(gè)元素，或區(qū)間內(nèi)元素（用iter指示）
mp.erase(iter);
mp.erase('b');
mp.erase(mp.begin(), mp.end()); //不刪除第二個(gè)參數(shù)指向的元素

6.5 queue, 先進(jìn)先出

1. 只能訪問 隊(duì)首 和 隊(duì)尾 元素
q.front();
q.back();

2. 入隊(duì)和出隊(duì)
q.push();
q.pop();

3. 檢測是否為空
q.empty(); // 返回bool值
q.size();

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

6.6 priority queue

1. 只能訪問 隊(duì)首 元素，即為優(yōu)先級最高的元素
pq.top();

2. 入隊(duì)和出隊(duì)
pq.push();
pq.pop();

3. 檢測是否為空
q.empty(); // 返回bool值
q.size();

• 優(yōu)先級設(shè)置

1. 最基本形式
priority_queue<int, vector<int>, less<int> > q; //數(shù)字大的優(yōu)先級高
priority_queue<int, vector<int>, greater<int> > q; //數(shù)字小的優(yōu)先級高

2. 結(jié)構(gòu)體（or 類）優(yōu)先級設(shè)置：重載<小于號(hào)（重載大于號(hào)會(huì)出錯(cuò)）
struct fruit{
    string name;
    int price;
    friend bool operator < (fruit f1, fruit f2){
        return f1.price < f2.price;
    }
}
priority_queue<fruit> pq; //正常定義的小于號(hào)，價(jià)格越高優(yōu)先級越高

3. 在結(jié)構(gòu)體中定義cmp，重載（）符號(hào)
struct cmp{
    bool operator () (fruit f1, fruit f2){
         return f1.price < f2.price;  // 優(yōu)先隊(duì)列為價(jià)格高優(yōu)先級高
    }
};

• 重載運(yùn)算符

1. 調(diào)用作為類的成員函數(shù)的運(yùn)算符重載函數(shù)時(shí)，類對象肯定已經(jīng)被建立了，這時(shí)對象中對應(yīng)的私有數(shù)據(jù)成員存在。

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

2. 調(diào)用作為類的友元函數(shù)的運(yùn)算符重載函數(shù)時(shí)，類對象還未被建立，這時(shí)對象中對應(yīng)私有數(shù)據(jù)成員不存在。

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

6.7 stack 棧：后進(jìn)先出

類似優(yōu)先隊(duì)列
st.push();  st.pop();
st.top();

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

6.8 pair

1. 只有兩個(gè)元素
p.first; p.second; //注意沒有括號(hào)

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

6.9 <algorithm>中常用函數(shù)

• max(); min(); abs();
• swap()
• reverse(it1, it2)l; 將兩迭代器之間的內(nèi)容逆序，不包括it2所在位置元素
• 全排列 next_permutation(it1, it2); 或者使用指針作為參數(shù)。當(dāng)已經(jīng)達(dá)到全排列的最后一個(gè)（逆序時(shí)），則會(huì)返回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); 給數(shù)組或者容器復(fù)制233
• sort(it1, it2, cmp);
• it = lower_bound(it1, it2, val); 返回第一個(gè)大于等于val的元素的iter
  it = upper_bound(it1, it2, val); 返回第一個(gè)大于val的元素的iter

7 數(shù)據(jù)結(jié)構(gòu)專題

7.1 棧 stack

兩個(gè)棧實(shí)現(xiàn)簡單計(jì)算器：從頭開始讀表達(dá)式，遇到數(shù)字立即壓入數(shù)字棧。遇到運(yùn)算法與算符棧頂比較：

• 若比棧頂優(yōu)先級高則入棧
• 若比棧頂算符優(yōu)先級低，則算符棧棧頂出棧，與數(shù)字棧頂兩位數(shù)字運(yùn)算后壓入數(shù)字棧。

7.3 鏈表

• 動(dòng)態(tài)鏈表一般頭部不保存數(shù)據(jù)，便于下面insert，del函數(shù)的編寫。靜態(tài)列表首部保存數(shù)據(jù)。

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

（1） 動(dòng)態(tài)分配內(nèi)存：malloc 與 free

int* p = (int*)malloc(sizeof(int)); // 申請一塊int32大小的32位內(nèi)存，返回指針
free(p); //釋放內(nèi)存

（2） 動(dòng)態(tài)分配內(nèi)存：new 與 delete

int* p = new int; // 同樣返回一個(gè)指針
delete(p); // 與new對應(yīng)的釋放內(nèi)存

• for循環(huán)創(chuàng)建鏈表（表頭也保存數(shù)據(jù)）

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個(gè)位置插入數(shù)據(jù)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 深度優(yōu)先

• 用一個(gè)棧的出棧入棧就能實(shí)現(xiàn)
• 一般用遞歸實(shí)現(xiàn)，遞歸的本質(zhì)也是系統(tǒng)棧的入棧出棧。
• 程序見8.2后

8.2 BFS 廣度優(yōu)先

• 用一個(gè)先進(jìn)先出隊(duì)列能實(shí)現(xiàn)
• 不訪問曾經(jīng)訪問過的節(jié)點(diǎn)
• 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 數(shù)據(jù)結(jié)構(gòu)專題

9.1 樹與二叉樹

1. 定義：空樹、層次（根節(jié)點(diǎn)為第一層）、度（節(jié)點(diǎn)子樹的棵數(shù)）；n個(gè)節(jié)點(diǎn)的樹有n-1條邊；深度（自頂向下，根節(jié)點(diǎn)為1）、高度（自底向上，最底層子節(jié)點(diǎn)為1）

2. 二叉樹分類：滿二叉樹（E）、完全二叉樹（D，E）

   
   
   在這里插入圖片描述

6.1.3 二叉樹儲(chǔ)存、查找、修改、插入

• 儲(chǔ)存結(jié)構(gòu)

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

• 生成新節(jié)點(diǎn)

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

• 根據(jù)二叉樹類型不同有不同的插入方式，需要新建節(jié)點(diǎn)時(shí)直接引用root，注意&

void insert(node* &root, int val){
    if(root == NULL){
        root = newNode(val);
        return;
    }
    if(根據(jù)二叉樹性質(zhì)val應(yīng)該插在左子樹){
        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的區(qū)別

9.2 二叉樹的遍歷

• 先序遍歷：根節(jié)點(diǎn)->左子樹->右子樹 （深度優(yōu)先）
• 中序遍歷：左子樹->根節(jié)點(diǎn)->右子樹 （深度優(yōu)先）
• 后序遍歷：左子樹->右子樹->根節(jié)點(diǎn) （深度優(yōu)先）
• 層次遍歷（廣度優(yōu)先）

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

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

• 利用先序序列（數(shù)組）和（中序序列）構(gòu)建一棵二叉樹

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;
}

• 中序序列可以和先序序列、后序序列、層序序列中任意一個(gè)來構(gòu)建唯一的二叉樹。因?yàn)橄刃蛐蛄?、后序序列、層序序列都可以確定root，而中序序列用于劃分左子樹和右子樹。

9.2.4 層序遍歷

類似廣度優(yōu)先算法，利用隊(duì)列。可在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 二叉樹靜態(tài)實(shí)現(xiàn)

• 用一個(gè)node數(shù)組保存節(jié)點(diǎn)，用數(shù)組的下標(biāo)來代替之前的指針，程序?qū)懛ê颓懊娴念愃?。引入全局變量index，nodes[index]

9.3 一般樹的遍歷

• 一般使用靜態(tài)寫法，用數(shù)組的下標(biāo)代替指針，指向一棵子樹。

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）

• 對任意一個(gè)節(jié)點(diǎn)，左子樹的數(shù)據(jù)都比根節(jié)點(diǎn)數(shù)據(jù)小，右子樹的數(shù)據(jù)都比根節(jié)點(diǎn)數(shù)據(jù)大。

1. 查找元素x，并返回其所在節(jié)點(diǎn)。

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);
}

2. 不存在重復(fù)元素的插入

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);
    }
}

3. 用數(shù)組建立二叉查找樹

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

4. 若刪除的節(jié)點(diǎn)下沒有子樹，則直接刪除。若該節(jié)點(diǎn)有左子樹，則尋找該結(jié)點(diǎn)的前驅(qū)代替它。若該節(jié)點(diǎn)沒有左子樹而有右子樹，則尋找該結(jié)點(diǎn)的后繼代替它。（比根節(jié)點(diǎn)data小的最大節(jié)點(diǎn)稱為根節(jié)點(diǎn)的前驅(qū)，同理比根節(jié)點(diǎn)data大的最小節(jié)點(diǎn)成為該節(jié)點(diǎn)的后繼）

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); //因?yàn)榍膀?qū)或者后繼不一定為空樹，前驅(qū)可能有左子樹，后繼可能有右子樹
        }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);
    }
}

5. 二叉查找樹的中序遍歷是從小到大排列的數(shù)

9.5 平衡二叉樹（AVL樹）

• 每次插入元素后樹的高度仍保持O(logn)。要求每個(gè)節(jié)點(diǎn)左子樹和右子樹高度之差的絕對值不超過1
• 在結(jié)構(gòu)體中增加保存高度的參數(shù)?！?/li>

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

• 新建節(jié)點(diǎn)的函數(shù)也需稍作修改

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

• 返回節(jié)點(diǎn)高度的函數(shù)，NULL節(jié)點(diǎn)返回高度0

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

• 更新節(jié)點(diǎn)高度的函數(shù)

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

• 計(jì)算平衡因子的函數(shù)

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

1. 查找操作與二叉查找樹相同
2. 插入操作需掌握左旋、右旋操作?？梢宰C明，然后把最靠近插入節(jié)點(diǎn)的失衡節(jié)點(diǎn)（平衡因子絕對值為2）調(diào)整到正常，路徑上的所有節(jié)點(diǎn)都會(huì)平衡。調(diào)整分4種情況。

3. 插入操作需掌握左旋、右旋操作。可以證明，然后把最靠近插入節(jié)點(diǎn)的失衡節(jié)點(diǎn)（平衡因子絕對值為2）調(diào)整到正常，路徑上的所有節(jié)點(diǎn)都會(huì)平衡。調(diào)整分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);
            }
        }
    }
}

4. 刪除操作（筆者自行發(fā)揮）

• 刪除節(jié)點(diǎn)分三種情況。
• 第1種被刪除的節(jié)點(diǎn)是葉結(jié)點(diǎn)：直接刪除，隨著遞歸函數(shù)的系統(tǒng)棧的彈出，自底向上地更新祖先節(jié)點(diǎn)的高度，并檢查祖先節(jié)點(diǎn)是否平衡。若不平衡，調(diào)整方案與插入操作時(shí)相同。
• 第2種被刪的節(jié)點(diǎn)只有左子樹或者右子樹：用該節(jié)點(diǎn)唯一的子樹代替該節(jié)點(diǎn)的位置。自底向上地更新祖先節(jié)點(diǎn)的高度，并檢查祖先節(jié)點(diǎn)是否平衡并調(diào)整。
• 第3種被刪的節(jié)點(diǎn)既有左子樹又有右子樹：將該節(jié)點(diǎn)的前驅(qū)或者后繼（當(dāng)左子樹高度大于右子樹時(shí)用前驅(qū)，當(dāng)右子樹高度大于等于左子樹時(shí)用后繼）的data與該節(jié)點(diǎn)交換（交換后，樹還是平衡的），前驅(qū)或者后繼的位置一定是第1種或第2種情況。然后對前驅(qū)或者后繼節(jié)點(diǎn)進(jìn)行刪除操作（即調(diào)用deleteNode的函數(shù)進(jìn)入第1種或第2種情況）。
• 在之前二叉查找樹的deleteNode()代碼基礎(chǔ)上稍作修改得到以下

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:左子樹高度大于右子樹時(shí)用前驅(qū)
                node* pre = findMax(root->lchild);
                root->data = pre->data;
                deleteNode(root->lchild, pre->data); //因?yàn)榍膀?qū)或者后繼不一定為空樹，前驅(qū)可能有左子樹，后繼可能有右子樹
            }else{  //情況3:當(dāng)右子樹高度大于等于左子樹時(shí)用后繼
                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); //刪除左子樹的節(jié)點(diǎn)，不平衡時(shí)只可能左子樹比右子樹低。
        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

• 用一個(gè)數(shù)組即可實(shí)現(xiàn) int father[N];
• 初始化: 令所有元素都是一個(gè)獨(dú)立的集合，即父節(jié)點(diǎn)指向本身

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

• 查找根節(jié)點(diǎn)：可以用循環(huán)或者遞歸實(shí)現(xiàn)

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;
}

• 路徑壓縮：將所有節(jié)點(diǎn)都連接在根節(jié)點(diǎn)上，在查找時(shí)重連接

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

9.7 堆（完全二叉樹）

• 以大頂堆為例
• 用一個(gè)數(shù)組從下標(biāo)1開始保存。和下標(biāo)為 i 的節(jié)點(diǎn)的子節(jié)點(diǎn)為 i 和 i+1
• 向下調(diào)整（下沉法）：將根節(jié)點(diǎn)與他的子結(jié)點(diǎn)對比，如果根節(jié)點(diǎn)子節(jié)點(diǎn)小，則與子節(jié)點(diǎn)中較大的一個(gè)交換位置，一直向下調(diào)整，直到不能調(diào)整。根結(jié)點(diǎn)的選取從下往上、從右往左。

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個(gè)元素的堆，[1, floor(n/2)] 都是非葉子節(jié)點(diǎn)。從下往上、從右往左地調(diào)整

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);
}

• 刪除堆頂元素：用最后一個(gè)元素覆蓋堆頂元素，堆的元素個(gè)數(shù)減1，然后向下調(diào)整堆頂元素

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

• 增加新元素：將元素添加至最后，然后對他進(jìn)行向上調(diào)整（上浮法）

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個(gè)數(shù)，尋找一棵樹，使得樹的所有葉子節(jié)點(diǎn)的恰好為這n個(gè)數(shù)，并且使得這棵樹的帶權(quán)路徑長度最小，這樣的樹被稱為哈夫曼樹。
• 構(gòu)建過程：用一個(gè)優(yōu)先隊(duì)列保存所有的節(jié)點(diǎn)，每次選出權(quán)值最小的兩個(gè)節(jié)點(diǎn)，將它們合并為父節(jié)點(diǎn)后送入優(yōu)先隊(duì)列。
• 哈夫曼編碼：統(tǒng)計(jì)給定字符串中各個(gè)字符出現(xiàn)的次數(shù)，得到一段最短的01編碼。
  （以下代碼為筆者自行發(fā)揮）

#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); // 按出現(xiàn)次數(shù)降序排列
}


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，編碼關(guān)系保存在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 圖的相關(guān)定義

• 有向圖 和 無向圖
• 頂點(diǎn)的度，出度 和 入度
• 點(diǎn)和邊的權(quán)值，點(diǎn)權(quán) 和 邊權(quán)

10.2 圖的儲(chǔ)存

• 鄰接矩陣：矩陣中保存權(quán)值

• 鄰接表：每個(gè)點(diǎn)保存一個(gè)鄰接表，用鏈表 或 vector，每個(gè)元素包含指向的點(diǎn)和權(quán)值

• 無向圖： 連通分量；有向圖：強(qiáng)連通分量

10.3 圖的遍歷

• DFS：棧、遞歸函數(shù)
• BFS：隊(duì)列，可以用node作為元素，node中保存深度。

10.4 最短路徑

Dijkstra算法

• 只能解決所有邊的權(quán)重都是非負(fù)數(shù)的情況。如果邊的權(quán)重出現(xiàn)負(fù)數(shù)，最好使用SPFA算法
• 處理無向邊時(shí)，只需把無向邊看作雙向的有向邊。
• 統(tǒng)計(jì)已訪問的點(diǎn)(vis)到其他各個(gè)可到達(dá)點(diǎn)的最短距離d[i]，將最近的一個(gè)點(diǎn)設(shè)為已訪問，并遍歷更新該點(diǎn)直接連接的點(diǎn)到原點(diǎn)的最短距離。每重復(fù)一次這樣的過程，已訪問的點(diǎn)個(gè)數(shù)增加1，重復(fù)n次這樣的過程即可訪問到所有n個(gè)點(diǎn)
• 以鄰接表圖為例

struct node{int v, dis;};

const int inf = 0x3fffffff;
vector<node> Adj[1000];
int n; //點(diǎn)的個(gè)數(shù)
int d[1000]; // 到i的最短路徑
int pre[1000]; // 記錄前驅(qū)節(jié)點(diǎn)
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;
            }
        }
    }
}

• 用遞歸函數(shù)輸出最短路徑

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

• 在接受多條最短路徑的情況下,記錄前驅(qū)節(jié)點(diǎn)的pre數(shù)組可以改為vector<int> pre[1000];。遍歷所有最短路徑，可以找出一條使第二標(biāo)尺最優(yōu)的路徑。

10.4.2 Bellman-Ford算法 和 SPFA算法

• 零環(huán)、正環(huán)、負(fù)環(huán)：負(fù)環(huán)的存在會(huì)影響最短路徑的求解，若遭遇負(fù)環(huán)BF算法返回false。
• BF算法思路：每輪操作遍歷所有u到v的邊，如果走這條邊，可以使v到原點(diǎn)的距離更短，則更新v到原點(diǎn)的距離d[v]，這樣的一次更新稱作松弛操作?？梢宰C明進(jìn)行n-1輪這樣的操作一定能得到原點(diǎn)到所有點(diǎn)的最短路徑。但是并不一定需要進(jìn)行n-1輪操作，在某一輪操作后，發(fā)現(xiàn)所有的邊都沒有被松弛，則說明數(shù)組d中的所有的值都已經(jīng)達(dá)到最優(yōu)，不需要繼續(xù)。

struct node{
    int v, dis;
    node(int _v, int _dis):v(_v), dis(_dis){}
};
const int inf = 0x3fffffff;
vector<node> Adj[1000];
int n; //點(diǎn)的個(gè)數(shù)
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;
    }
    // 檢測是否存在負(fù)環(huán)
    for(int u=0; u<n; u++){
        for(auto it: Adj[u]){
            if(d[it.v] > d[u] + it.dis) return false;
        }
    }
    return true;
}

• 我們注意到只有當(dāng)某個(gè)頂點(diǎn)u的d[u]值變化時(shí)，從它出發(fā)的邊的鄰接點(diǎn)v的d[v]值才有可能被改變。可以進(jìn)行優(yōu)化：建立一個(gè)隊(duì)列，每次將隊(duì)首的u取出，然后對從u出發(fā)的所有邊進(jìn)行松弛操作。如果成功松弛，使得d[v]獲得更優(yōu)的值，并且v不在當(dāng)前隊(duì)列中，則將v加入隊(duì)列。
  由每個(gè)點(diǎn)加入隊(duì)列的次數(shù)(注意,不是松弛的次數(shù))，可以判斷是否存在負(fù)環(huán)。每個(gè)點(diǎn)加入隊(duì)列的次數(shù)都不應(yīng)超過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; //點(diǎn)的個(gè)數(shù)
int d[1000]; // 到i的最短路徑
int num[1000]; // 統(tǒng)計(jì)入隊(duì)次數(shù)
bool inq[1000]; // 標(biāo)志是否在隊(duì)列中

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十分靈活，可以根據(jù)具體場景的不同進(jìn)行調(diào)整。上述代碼中的隊(duì)列可以替換為優(yōu)先隊(duì)列，以加快速度?；蛘咛鎿Q為雙端隊(duì)列（deque），使用SLF和LLL優(yōu)化，提高至少50%效率。上述代碼給出的是BFS版本，如果將隊(duì)列替換成棧，則可以實(shí)現(xiàn)DFS版本的SPFA，對判斷環(huán)有奇效。

10.4.3 Floyd算法

• 用于解決全源最短路徑問題。
• 如果以k為中介點(diǎn)，可以使頂點(diǎn) i 到頂點(diǎn) j 的當(dāng)前最短距離縮短，則更新 i 到 j 的最短距離。對每個(gè)頂點(diǎn)都作為中介點(diǎn)檢查一遍。
• 用鄰接矩陣保存距離

const int inf = 0x3fffffff;
const int maxn = 200;
int n; //點(diǎn)的個(gè)數(shù)
int m; //邊的條數(shù)
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 最小生成樹

• 性質(zhì)：
  1. 最小生成樹中包含一張無向圖中所有的點(diǎn)，樹的邊都來自于圖的邊，而且保證樹中所有邊的權(quán)重之和最小。
  2. 最小生成樹的邊數(shù)等于頂點(diǎn)數(shù)減一，且樹內(nèi)一定不會(huì)有環(huán)。
  3. 最小生成樹可以不唯一，但其邊權(quán)之和一定唯一。
  4. 最小生成樹是在無向圖上生成的，因此其根節(jié)點(diǎn)可以是這棵樹上的任意一個(gè)節(jié)點(diǎn)。

10.5.2 Prim算法

• Prim算法和Dijkstra算法思路幾乎完全相同，僅有d[i] 的含義不同。Dijkstra算法中 d 存放所有點(diǎn)到原點(diǎn)的當(dāng)前最短距離，Prim算法中 d 存放所有點(diǎn)到已訪問點(diǎn)集合 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的點(diǎn)，因?yàn)槭Ｏ碌狞c(diǎn)與現(xiàn)在的已訪問集合不連通 
        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. 對所有邊按權(quán)值從小到大排序
  2. 從小到大的檢測這些邊，如果當(dāng)前檢測的邊連接的兩個(gè)頂點(diǎn)在兩個(gè)不同的連通塊中，則將這條邊添加進(jìn)最小生成樹，否則舍棄
  3. 重復(fù)執(zhí)行步驟2，直到最小生成樹的邊數(shù)為n-1，若小于n-1則說明這張圖不是全連通的
• 用并查集判斷兩個(gè)頂點(diǎn)是否在同一連通塊中

const int maxn = 1000;
struct edge{
    int u, v, dis;
    edge(){}  // !!!數(shù)組提前分配空間時(shí)需要調(diào)用無參數(shù)的構(gòu)造函數(shù)
    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: 為一個(gè)結(jié)構(gòu)體提前分配數(shù)組空間，需要該結(jié)構(gòu)體有一個(gè)無參數(shù)的構(gòu)造函數(shù)

• 如果是稠密圖（邊多）選擇Prim算法，如果是稀疏圖（邊少）選擇Kruskal算法

10.6 拓?fù)渑判?/h2>

• 基本步驟：
  1. 定義一個(gè)隊(duì)列q，把所有入度為0的節(jié)點(diǎn)加入隊(duì)列
  2. 取出隊(duì)首節(jié)點(diǎn)并輸出，然后刪去所有從它出發(fā)的邊，并令這些邊到達(dá)點(diǎn)的入度減1
  3. 若到達(dá)點(diǎn)的入度減為0，則讓該點(diǎn)進(jìn)入隊(duì)列。重復(fù)第2步操作直至對列元素個(gè)數(shù)為0

const int maxn = 1000;
vector<int> Adj[maxn];
int inDegree[maxn];
int n; // 頂點(diǎn)數(shù)
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 關(guān)鍵路徑

10.7.1 AOV網(wǎng) 和 AOE網(wǎng)

• 頂點(diǎn)活動(dòng)AOV：Activity on vertex, 用頂點(diǎn)表示活動(dòng), 用邊表示頂點(diǎn)及優(yōu)先級關(guān)系的有向圖
• 邊活動(dòng)AOE：Activity on edge，用代權(quán)的邊集表示活動(dòng)，用頂點(diǎn)表示“事件“（這里的事件僅代表一種中介狀態(tài)）的有向圖。
• AOE圖有多個(gè)源點(diǎn)和匯點(diǎn)時(shí)，可以引入超級源點(diǎn)和超級匯點(diǎn)，超級源點(diǎn) 和 超級匯點(diǎn) 到源點(diǎn)和匯點(diǎn)的邊的權(quán)值為0。
• 將AOV網(wǎng)中每個(gè)頂點(diǎn)拆成兩個(gè)頂點(diǎn)，兩個(gè)頂點(diǎn)由帶權(quán)值的邊連接，可將AOV網(wǎng)轉(zhuǎn)化為AOE網(wǎng)。
• 定義：AOE網(wǎng)中的最長路徑被稱為關(guān)鍵路徑，把關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)，顯然關(guān)鍵活動(dòng)會(huì)影響整個(gè)工程的進(jìn)度。

10.7.2 最長路徑

• 將所有邊權(quán)乘- 1 后用最短路徑中的Bellman-Ford的算法或SPFA算法求最短路徑。圖中如果有正環(huán)，那么最長路徑不存在。

10.7.3 關(guān)鍵路徑

• 求解有向無環(huán)圖中最長路徑的方法
• 算法思路：
  1. 活動(dòng)的最早開始時(shí)間和最遲開始時(shí)間可以由活動(dòng)兩側(cè)的事件（節(jié)點(diǎn)）的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間確定。
  2. 而事件 j 的最早發(fā)生時(shí)間由它的一個(gè)或多個(gè)前驅(qū)節(jié)點(diǎn) i 的最早發(fā)生時(shí)間加上事件 i 的時(shí)長決定（取最大值）。
  3. 使用拓?fù)渑判蚩梢员ＷC在訪問某個(gè)節(jié)點(diǎn)時(shí)，它的前驅(qū)節(jié)點(diǎn)都已經(jīng)訪問完畢。
  4. 因?yàn)橛汕膀?qū)節(jié)點(diǎn)找到后繼節(jié)點(diǎn)容易，而反之很難。所以一個(gè)比較好的策略是：在拓?fù)渑判蛟L問到某個(gè)節(jié)點(diǎn)時(shí)，去更新其所有后繼節(jié)點(diǎn)的最早發(fā)生時(shí)間。
  5. 同理，為了得到事件的最遲發(fā)生時(shí)間，需要由下一事件推出前一事件的最遲發(fā)生時(shí)間。在訪問某個(gè)節(jié)點(diǎn)時(shí)需要保證，它的后繼節(jié)點(diǎn)都已經(jīng)訪問完畢，利用逆拓?fù)湫騺肀ＷC（具體實(shí)現(xiàn)方式是：在求拓?fù)湫驎r(shí)入棧，一個(gè)個(gè)出棧得到逆拓?fù)湫颍?/li>
  6. 事件最早發(fā)生時(shí)間數(shù)組 ve[ ] 用0初始化，事件最遲發(fā)生時(shí)間數(shù)組 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; // 頂點(diǎn)數(shù)
vector<int> sorted_series;

int ve[maxn];
int vl[maxn];
stack<int> TopoOrder; // 為了方便得到逆拓?fù)湫?
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;

    // 對于多個(gè)匯點(diǎn)的圖，棧頂事件不一定是最晚發(fā)生的事件
    int maxve = 0;
    for(int i=0; i<n; i++) if(ve[i] > maxve) maxve = ve[i];
    fill(vl, vl+n, maxve); //用最后一個(gè)事件的最早發(fā)生時(shí)間初始化所有事件的最遲發(fā)生時(shí)間
    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 動(dòng)態(tài)規(guī)劃專題（Dynamic programming）

• 定義：用來解決一類最優(yōu)化問題的算法思想
• 遞歸寫法：又稱作記憶化搜索，當(dāng)下次再碰到需要計(jì)算相同的內(nèi)容時(shí)，就直接使用上次計(jì)算的結(jié)果。
• 遞推寫法：從邊界開始向上尋找問題的解，通過狀態(tài)轉(zhuǎn)移方程將邊界量擴(kuò)散到整個(gè)子問題集。
  1. 分治與動(dòng)態(tài)規(guī)劃：分解出的子問題是不重疊的，動(dòng)態(tài)規(guī)劃分解出的子問題有重疊。分治法解決的問題不一定是最優(yōu)化問題，而動(dòng)態(tài)規(guī)劃解決的問題一定是對話問題。
  2. 貪心與動(dòng)態(tài)規(guī)劃：都要求原問題必須擁有最優(yōu)子結(jié)構(gòu)。貪心并不等待子問題求解完畢后再選擇使用哪一個(gè)，而是通過一種策略直接選擇一個(gè)子問題去求解，沒被選擇的子問題就直接放棄，總是在上一步選擇的基礎(chǔ)上繼續(xù)選擇；這種局部最優(yōu)選擇的正確性需要用歸納法證明。動(dòng)態(tài)規(guī)劃從邊界開始向上得到目標(biāo)問題的解，總是會(huì)考慮所有子問題，并選擇繼承能得到最優(yōu)結(jié)果的那個(gè)，對暫時(shí)沒被繼承的子問題，后期可能會(huì)再次考慮到他們。

10.2 最大連續(xù)子序列和

• 給定一個(gè)數(shù)字序列 a[n]，輸出連續(xù)子序列的最大和。
• 考慮以 a[i] 結(jié)尾的連續(xù)序列的最大和（記為dp[i]），只有以下兩種情況：
  1. 這個(gè)最大和的連續(xù)序列只有一個(gè)元素，就是 a[i]
  2. 以 a[i-1] 為結(jié)尾的子序列的最大和，加上 a[i]。dp[i-1] + a[i]
• n次計(jì)算max(a[i], dp[i-1]+a[i])即可得到完整的dp序列，其中最大值是我們想要的連續(xù)子序列的最大和

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）

• 在一個(gè)數(shù)字序列中找到一個(gè)最長子序列（可以不連續(xù)）使得這個(gè)子序列也是不下降的
• 考慮以 a[i] 結(jié)尾的最長不下降子序列元素個(gè)數(shù)（記為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）

• 給定兩個(gè)字符串 A 和 B，求一個(gè)字符串使得這個(gè)字符串是 A 和 B 的最長公共部分（可以不連續(xù)，但順序不變）
• 算法思路：遞推思想
  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]前面再?zèng)]有元素，所以我們做了個(gè)padding，將A、B都向后移一位，設(shè)定任意的dp[0][i]、dp[i][0]都為0，現(xiàn)在兩字符串首位是dp[1][1]

const int maxn = 100; 
string A, B;
int LCS(){
    int dp[maxn][maxn]; //小心爆棧，2MB，最多開721*721個(gè)int，2MB/4B = 2^19 = 524288個(gè)int
    A = " " + A; // padding
    B = " " + B;
    int m = A.size(), n = B.size();
    // 設(shè)置邊界條件
    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 最長回文子串

• 給定一個(gè)字符串s，求s的最長回文子串長度。
• 書上給的代碼，兩重循環(huán)，第1層循環(huán)是子串的長度從3開始，第2層循環(huán)在原字符串內(nèi)按子串長度掃描。

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;
    }
    //設(shè)置邊界
    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（有向無環(huán)圖）最長路

• 用數(shù)組dp[i] 保存從 i 號(hào)頂點(diǎn)出發(fā)能獲得的最長路徑長度
• 需要按照逆拓?fù)湫虻捻樞蚯蠼鈊p數(shù)組，或者使用遞歸的方法
• 不妨初始化整個(gè)dp數(shù)組為0

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

vector<node> Adj[1000];
int n; //點(diǎn)的個(gè)數(shù)
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);
    } 
}

• 固定終點(diǎn),求最長路徑長度。

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時(shí)裝入前 i 件物品時(shí)，所能獲得的最大價(jià)值。
• 邊界條件是 i = 0 或 v = 0，此時(shí)dp為0
• 思路：
  1. 不放第 i 件物品時(shí)，問題轉(zhuǎn)化為前 i-1 件物品恰好裝入容量為v的背包中所能獲得的最大價(jià)值
  2. 若放第 i 件物品，那么問題轉(zhuǎn)化為前 i-1 件物品恰好裝入容量為 v - w[i] 的背包中所能獲得的最大價(jià)值。
• 狀態(tài)轉(zhuǎn)移方程：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(){  // 用滾動(dòng)數(shù)組優(yōu)化減少空間復(fù)雜度
    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背包的區(qū)別在于每種物體有無窮多件。
• 這個(gè)問題之前是用貪心算法做的，總是先放入單位重量價(jià)值更高的物品
• 同樣，dp[i][v] 保存在背包容量剩余v時(shí)裝入前 i 件物品時(shí)，所能獲得的最大價(jià)值。
• 邊界條件是 i = 0 或 v = 0，此時(shí)dp為0
• 思路：
  1. 不放第 i 件物品時(shí)，問題轉(zhuǎn)化為前 i-1 件物品恰好裝入容量為v的背包中所能獲得的最大價(jià)值
  2. 若放第 i 件物品，而第 i 件物品可以放任意件，那么問題轉(zhuǎn)化為前 i 件物品恰好裝入容量為 v - w[i] 的背包中所能獲得的最大價(jià)值。因?yàn)榭赡艽嬖谶@樣的過程 dp[i][v-w[i]] -> dp[i][v]，因?yàn)橛盅b入了一件 i 物品
• 完全背包狀態(tài)轉(zhuǎn)移方程：dp[i][v] = max(dp[i-1][v], dp[i][v-w[i]] + c[i]);
• 相比01背包問題代碼只需稍作修改，從逆向枚舉改為正向枚舉。因?yàn)榭梢员ＷC計(jì)算 dp[i][v] 時(shí)，已經(jīng)完成 dp[i][v-w[i]] 的計(jì)算

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(){  // 用滾動(dòng)數(shù)組優(yōu)化減少空間復(fù)雜度
    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進(jìn)階

• 最簡單的方法是將只包含大寫字母的字符串直接轉(zhuǎn)化為26進(jìn)制，一個(gè)字符串對應(yīng)一個(gè)整數(shù)
• 為了避免產(chǎn)生的整數(shù)過大的問題，一般我們會(huì)舍棄一些唯一性，對產(chǎn)生的結(jié)果取模?？梢宰C明把進(jìn)制數(shù)p設(shè)置為級別的素?cái)?shù)(10000019)，把設(shè)置為級別的素?cái)?shù)(1000000007)，很少發(fā)生唯一性沖突。

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'可能是負(fù)數(shù)
        all_H[i] = H;
    }
    return H;
}

• 字符串s的從 i 到 j 位的子串的hash值，可以由從0到 j 位和 0 到 i-1 位的子串的哈希值推導(dǎo)出來，在一些問題中可以避免重復(fù)計(jì)算。因?yàn)樾±ㄌ?hào)內(nèi)計(jì)算結(jié)果可能為負(fù)數(shù)，所以需要進(jìn)行一系列的取余計(jì)算
  

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. 若回文串長度是奇數(shù)：枚舉回文中心 i 和二分子串的半徑k，判斷[i-k, i] 和 [i, i+k] 子串是否相反（左子串，反向求hash）
  2. 若回文串長度是偶數(shù)：枚舉回文中心 i 和二分子串的半徑k，判斷[i-k+1, i] 和 [i+1, i+k] 子串是否相反（左子串，反向求hash）

12.2 KMP算法

• 字符串的匹配問題，text 文本串 和 pattern 模式串。判斷pattern是否是text的子串。

12.2.1 next數(shù)組

• next[i] 表示子串 s[0..i] 的前綴 s[0..k] 等于后綴 s[i-k..i] 的最大k
• next[i]可以由遞推的方法由 next[0]~next[i-1] 求出
  引用：關(guān)于遞推式理解
  
  套娃：增長一位后如何比較

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++; // 第一位與倒數(shù)第一位相等時(shí)，若不等則不存在相同前后綴
        Next[i] = j;
    }    
}

10.2.2 KMP算法

• i 指向text文本串中的一個(gè)位置，j 指向pattern模式串中的一個(gè)位置
• next數(shù)組的含義就是當(dāng) j+1 位匹配失敗時(shí)，j 應(yīng)該退回到的位置
• 算法思路：
  1. 初始化 j = -1，表示pattern當(dāng)前已被匹配的最后位
  2. 讓i 遍歷文本串text，對每個(gè) i 執(zhí)行③④步來試圖匹配 text[i] 和 pattern[j+1]
  3. 不斷令 j = Next[j]，直到 j 回退到 -1 或 text[i] = pattern[j+1] 成立
  4. 如果 text[i] = pattern[j+1] ，則令 j++。如果 j 達(dá)到 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;
}

• 還可以實(shí)現(xiàn)統(tǒng)計(jì) text 字符串中 pattern 出現(xiàn)的次數(shù)

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算法還可以優(yōu)化，因?yàn)槲覀儼l(fā)現(xiàn)如果回退后的對應(yīng)位置（next[j]）上的字符與回退前對應(yīng)位置（j）的字符相同時(shí)，即 pattern[j] == pattern[Next[j]]，必然還會(huì)失配。所以我們優(yōu)化next數(shù)組為nextval數(shù)組，它的含義可以理解為當(dāng)前模式串pattern的 j+1 位發(fā)生失配時(shí)，j 應(yīng)當(dāng)退回到最佳位置，對next生成函數(shù)操作修改

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 專題擴(kuò)展

13.1 分塊思想

• 給定一個(gè)整數(shù)序列，查詢序列中第K大的元素
• 類似儲(chǔ)存管理系統(tǒng)中的頁表思想，分級查詢。將有n個(gè)元素的序列分為塊，每一塊中有個(gè)元素。
  舉例說明: 對一個(gè)擁有個(gè)不超過的非負(fù)整數(shù)的序列，可劃分為317塊，每一塊中有316個(gè)元素。定義一個(gè)統(tǒng)計(jì)數(shù)組block[317]，和一個(gè)hash數(shù)組table[100001]
  1. 新增元素 x 時(shí)，block[x/316]++, hash[x]++
  2. 查詢第K大的元素時(shí)，從小到大枚舉塊號(hào)，利用block數(shù)組累加得到前 i-1 塊中存在元素的總個(gè)數(shù)，若再加上block[i] 恰好大于等于K，則進(jìn)入第 i 塊，逐個(gè)累加，直至第K大個(gè)數(shù)，時(shí)間復(fù)雜度是

13.2 樹狀數(shù)組(BIT)

13.2.1 lowbit運(yùn)算

• lowbit(x) = x & (-x) 表示取x的二進(jìn)制最右邊的1和它右邊所有0。也可以理解為能整除x的最大2的次冪

13.2.2 樹狀數(shù)組及其應(yīng)用

• 樹狀樹組BIT與sum[]數(shù)組類似，不過它的第 i 位存放的是在整數(shù)序列 i 號(hào)位之前的lowbit(i)個(gè)整數(shù)之和

  
  
  樹狀數(shù)組定義圖
• 構(gòu)建樹狀數(shù)組的函數(shù)、返回前x個(gè)整數(shù)之和的函數(shù)、將第x個(gè)整數(shù)加v后更新樹狀數(shù)組的函數(shù)：

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

void get_c(){
    int n = A.size(); //A的第0位保留，設(shè)為-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個(gè)整數(shù)加v后。
void update(int x, int v){
    int n = A.size();
    for(int i=x; i<=n; i+=lowbit(i)) c[i] += v;
}

• 樹狀數(shù)組可以解決如下問題：給定一個(gè)有n個(gè)正整數(shù)的序列A，對序列中每個(gè)數(shù)求出序列中它左邊比它小的數(shù)的個(gè)數(shù)

#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個(gè)整數(shù)加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);
}

• 當(dāng)A[i]非常大時(shí)，可以用到離散化的技巧，將原始元素映射為一個(gè)符合要求的序號(hào)

完結(jié)撒花

李方楠
2020年8月14日