算法笔记V2.0

第一章 基础算法

暴力的调整区间的方法：

双指针调整区间的方法：

1.1快速排序

void quick_sort(int q[], int l, int r){
    // 没有数或者只有一个数
    if (l >= r) return;
    
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j){
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100;
int n;
int q[N];

void quick_sort(int q[], int l, int r){
    // 没有数或者只有一个数
    if (l >= r) return;
    // 定义两个指针，定义区间分割点 x
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    // 两个指针向中间靠
    while (i < j){
        // 找到第一个 q[i] >= x
        do i ++ ; while (q[i] < x);
        // 找到第一个 q[j] <= x
        do j -- ; while (q[j] > x);
        // 两个指针 i j 都找到了当前不符合的数的位置，则交换它们
        if (i < j) swap(q[i], q[j]);
    }
    // 递归处理左右两段
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        cin >> q[i];
    }
    
    quick_sort(q, 0, n - 1);
    
    for (int i = 0; i < n; i ++ ) cout << q[i] << ' ';
    
    return 0;
}

1.2归并排序

void merge_sort(int q[], int l, int r){
    if (l >= r) return;
    
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
    	else tmp[k ++ ] = q[j ++ ];
    
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100;
int n;
int q[N], tmp[N];

void merge_sort(int q[], int l, int r){
    if (l >= r) return;
    // 确定分界点
    int mid = l + r >> 1;
    // 递归左右两边
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    // 归并，需要格外数组
    int k = 0, i = l, j = mid + 1; // k 代表已经合并了多少个数，i 指向左半边的起点，j 指向右半边的起点
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
    	else tmp[k ++ ] = q[j ++ ];
    // 把剩余的数拿过来
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    // 将结果复制回来
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        cin >> q[i];
    }
    
    merge_sort(q, 0, n - 1);
    
    for (int i = 0; i < n; i ++ ) cout << q[i] << ' ';
    
    return 0;
}

1.3整数二分算法

1.3.1模板

bool check(int x){
	/**/
    // 检查x是否满足某种性质
}

// 区间[l, r]被划分为[l, mid]和[mid + 1, r]时使用
int bsearch_1(int l, int r){
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分为[l, mid - 1]和[mid, r]时使用
int bsearch_2(int l, int r){
    while (l < r){
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

• 技巧：
• 假设有一个总区间，经由我们的 check 函数判断后，可分成两部分，这边以o作 true，…..作 false 示意较好识别
• 如果我们的目标是下面这个v，那麽就必须使用模板 1
• …………….vooooooooo
• 假设经由 check 划分后，整个区间的属性与目标v如下，则我们必须使用模板 2
• oooooooov……………….

1.3.2例题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m; // n数组中数的个数，m询问的个数
int q[N];

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    
    while (m -- ){
        int x;
        scanf("%d", &x);
        
        int l = 0, r = n - 1; // 我们二分查找的是下标，而下标的范围是0~n-1
        while (l < r){
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        
        if (q[l] != x) cout << "-1 -1" << endl; // 二分确定的不是答案，返回找不到
        else{
            cout << l << ' '; // 找到了左端点，先输出即可
            
            int l = 0, r = n - 1; // 再次初始化查找右端点
            while (l < r){
                int mid = r + l + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            
            cout << r << endl;
        }
    }
    
    return 0;
}

1.4浮点数二分算法

bool check(double x) {/*...*/} //检查x是否满足某种性质

double bsearch_3(double l, double r){
    const double eps = 1e-6; // eps表示精度，取决于题目对精度的要求
    while (r - l > eps){
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

1.5高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B){
    if (A.size() < B.size()) return add(B, A);
    
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ ){
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    
    if (t) C.push_back(t);
    return C;
}

1.6高精度减法

// C = A - B，满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B){
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ ){
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

1.7高精度乘以低精度

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b){
    vector<int> C;
    
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ ){
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

1.8高精度除以低精度

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r){
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- ){
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

1.9一维前缀和

下标从1开始，S0 = 0， 方便处理边界，如求[1, 10] = S10 - S0 = S10 - 0 = S10

原数组：a1, a2, …, an

前缀和数组：Si = a1 + a2 + … + ai

如何求Si

for i = 1; i <= n; s[i] = s[i - 1] + a[i];

Si的作用：快速求原数组中的一段数的和，

[l, r] = S[r] - S[l - 1];

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], S[N];

int main(){
    ios::sync_with_stdio(false);
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i ++ ) scanf("%d", &a[i]);
    
    // 前缀和初始化
    for (int i = 1; i <= n; i ++ ) S[i] = S[i - 1] + a[i];
    
    // m个询问
    while (m -- ){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    
    return 0;
}

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

1.10二维前缀和

快速计算子矩阵的和，原矩阵是aij， Sij代表以Sij这个点为界限的左上角的矩阵的和

求内部子矩阵的和时，子矩阵的左上角为x1, y1, 右下角是x2, y2;

w = S(x2, y2) - S(x2, y1 - 1) - S(x1 - 1, y2) + S(x1 - 1, y1 - 1)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m; // 矩阵的长和宽
int q; // q个询问
int a[N][N], s[N][N];

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            scanf("%d", &a[i][j]);
    
    // 前缀和初始化
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ){
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    
    while (m -- ){
        int x1, y1, x2, y2;
       	scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    
    return 0;
    }
}

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

1.11一维差分

原数组是a1, a2, …, an

构造b数组b1, b2, …, bn；使得ai = b1 + b2 + b3 + … + bi，使得a数组是b数组的前缀和

构造方法：b1 = a1; b2 = a2 - a1；b3 = a3 - a2; … ; bn = an - an - 1;

b称为a的差分，a称为b的前缀和

对b求前缀和，就可以在O(n)的时间内求出a数组

差分主要用来快速处理这样一种操作：给定区间[l, r]， 对于这个区间的所有数全部加上C，用差分可以使用O(1)的时间完成这个操作；如果还想求出操作后的a数组，就可以扫描一遍b数组，然后求前缀和即可

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int  N = 100010;

int n, m;
int a[N], b[N];

// 区间[l, r] 内全部加上c
void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}

int main(){
    sacnf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);
    
    // m个操作
    while (m -- ){
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    
    // 再求原来的数组
    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];
    
    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);
    
    return 0;
}

给区间[l, r]中的每个数加上c: B[l] += c, B[r + 1] -= c

1.12二维差分

1.12.1模板

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

1.12.2差分矩阵

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m, q; // n矩阵长，m矩阵宽，q询问的个数
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c){
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main(){
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);
    
    while (q -- ){
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ )
            printf("%d ", b[i][j]);
        puts("");
    }
    
    return 0;
}

1.13位运算

1.13.1模板

求n的第k位数字：n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

1.13.2例题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main(){
    int n = 10;
    
    for (int k = 3; k >= 0; k -- ){
        cout << ((n >> k) & 1);
    }
    
    return 0;
}

1.13.3Lowbit

// 返回x的最后一位1
x = 1010, lowbit(x) = 10
实现：x&-x
c++ 中，-x=~x+1
x & -x = x & (~x + 1)
作用：统计x中1的个数：每次把1去掉，最后返回即可

#include <iostream>
#include <cstring>
#include <algorithm>
    
using namespace std;

int lowbit(int x){
    return x & -x;
}

int main(){
    int m;
    cin >> m;
    
    while (m -- ){
        int x;
        cin >> x;
        
        int res = 0;
        while (x) x -= lowbit(x), res ++ ; // 每次减去x的最后一位1
        
        cout << res << ' ';
    }
    
    return 0;
}

1.14双指针算法

1.14.1模板

for (int i = 0, j = 0; i < n; i ++ ){
    while (j < i && check(i, j)) j ++;
    // 具体问题的逻辑
}
常见问题分类：
    （1）对于一个序列，用两个指针维护一段区间
    （2）对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

1.14.2最长连续不重复子序列

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int q[N], s[N];

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    
    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ ){
        s[q[i]] ++ ;
        while (j < i && s[q[i]] > 1) s[q[j ++ ]] -- ;
        res = max(res, i - j + 1);
    }
    
    cout << res << endl;
    
    return 0;
}

1.14.3数组元素的目标和

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int a[N], b[N], n, m, x;

int main(){
    scanf("%d%d%d", &n, &m, &x);
    
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
    
    for (int i = 0, j = m - 1; i < n; i ++ ){
        // 因为保证一定有解
        while (a[i] + b[j] > x) j -- ;
        if (a[i] + b[j] == x){
            printf("%d %d\n", i, j);
            break;
        }
    }
    
    return 0;
}

1.15离散化

1.15.1模板

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()) // 将所有值进行排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去除重复元素

// 二分求出x对应的离散化的值
int find(int x){ // 找到第一个大于等于x的值
    int l = 0, r = alls.size() - 1;
    while (l < r){
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1，2，...n
}

1.15.2区间和

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

// 查询10万， 插入10万，查询需要两个坐标，插入需要1个坐标，共30万
const int N = 300010;

int n, m; // 
int a[N],s[N]; // 存的数 前缀和

vector<int> alls; // 存需要离散化的值
vector<PII> adds, query; // 定义两种操作，插入和查询

// 求x离散化后的值
int find(int x){
    int l = 0, r = alls.size() - 1;
    while (l < r){
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid; // 找到的是大于x的最小的数
        else l = mid + 1;
    }
    
    return r + 1;
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ){
        int x, c;
        cin >> x >> c;
        adds.push_back({x, c});
        
        alls.push_back(x); // 加入到待离散化的数组中
    }
    
    for (int i = 0; i < m; i ++ ){
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        
        alls.push_back(l); // 查询的端点区间也需要离散化
        alls.push_back(r); 
    }
    
    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    
    // 遍历所有操作
    for (auto item : add){
        int x = find(item.first); 
        a[x] += item.second;
    }
    
    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
    
    // 处理询问
    for (auto item : query){
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    
    return 0;
}

1.16区间合并

1.16.1模板

// 将所有存在交集的区间合并
void merge(vector<PII> &segs){
    vector<PII> res;
    
    sort(segs.begin(), segs.end());
    
    int st = -2e9, ed = -2e9;
    for (auto seg : segs){
        if (ed < seg.first){
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }else ed = max(ed, seg.second);
    }
    
    if (st != -2e9) res.push_back({st, ed});
    
    segs = res;
}

1.16.2区间合并题目

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

uisng namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
vector<PII> segs;

void merge(vector<PII> & segs){
    vector<PII> res;
    
    sort(segs.begin(), segs.end());
    
    int st = -2e9, ed = -2e9;
    for(auto seg : segs){ 
        if (ed < seg.first){ // 维护的区间严格在枚举的区间的左边
            if (st != -2e9) res.push_back({st, ed}); // 不存在交集，直接加到答案里面去
        		st = seg.first, ed = seg.second; // 更新当前所维护的区间
        }else ed = max(ed, seg.second); // 有交集，那么更新右端点即可
    }
    
    if (st != -2e9) res.push_back({st, ed}); // 防止一开始segs里面是空的
    segs = res;
}

int main(){
    cin >> n;
    
    for (int i = 0; i < n; i ++ ){
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    
    merge(segs);
    
    cout << segs.size() << endl;
    
    return 0;
}

第二章 数据结构

2.1单链表

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init(){
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a){
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头节点存在
void remove(){
    head = ne[head];
}

2.2双链表

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个点
int e[N], l[N], r[N], idx;

// 初始化
void init(){
    // 0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x){
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点
void remove(int a){
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

2.3栈

// tt 表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空，如果 tt > 0 , 则表示不为空
if (tt > 0){
    
}

2.4队列

2.4.1普通队列

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 队头的值
q[hh];

// 判断队列是否为空，如果hh <= tt, 则表示不为空
if (hh <= tt){
    
}

2.4.2循环队列

// hh表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空，如果hh != tt, 则表示不为空
if (hh != tt){
    
}

2.5单调栈

常见模型：找出每个数左边离他最近的比他大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ ){
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

2.6单调队列

常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ ){
    while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt]), i) tt -- ;
    q[ ++ tt] = i;
}

2.7KMP

2.7.1模板

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组
for (int i = 2, j = 0; i <= m; i ++ ){
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ ){
    while (j && s[i] != p[j + 1]) j = ne[i];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m){
        j = ne[j];
        // 匹配之后的逻辑
    }
}

2.7.2KMP字符串

#include <iostream>

using namespace std;

const int N = 10010, M = 100010;

int n, m;
char p[N], s[M];
int ne[N];

int main(){
    cin >> n >> p + 1 >> m >> s + 1;
    
    // 求next数组
    for (int i = 2, j = 0; i <= n; i ++ ){
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }
    
    
    // KMP匹配过程
    for (int i = 1, j = 0; i <= m; i ++ ){ //i j错开一位，i是j + 1进行匹配的
        while (j && s[i] != p[j + 1]) j = ne[j]; // 如果没有返回起点，并且i和j + q不匹配的了，那就往前退
        if (s[i] == p[j + 1]) j ++ ; // 匹配成功了，移到下一位
        if (j == n){
            printf("%d ", i - n);
            j = ne[j]; // 匹配到最后一位想要继续匹配
        }
    }
    return 0;
}

2.8Trie树

int son[N][26], cnt[N], idx;
// 0号点既是根结点，又是空节点
// son[][]存储树中每个节点的子节点
// cnr[]存储每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

2.9并查集

2.9.1模板

（1）朴素并查集：
int p[N]; // 存储每个节点的祖宗节点

// 返回x的祖宗节点
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

//合并a和b所在的两个集合
p[find(a)] = find(b);

（2）维护size的并查集
int p[N], size[N];
// p[]存储每个点的祖宗节点，size[]只有祖宗节点的有意义

// 返回x的祖宗节点
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ){
    p[i] = i;
    size[i] = 1;
}

// 合并a和b所在的两个集合
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

（3）维护到祖宗节点距离的并查集：
int p[N], d[N];
// p[]存储每个点的祖宗节点，d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x){
    if (p[x] != x){
        int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ){
    p[i] = i;
    d[i] = 0;
}

// 合并a和b所在的两个集合
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的便宜量

2.9.2合并集合

#include <iostream>
#include <cstirng>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m; // 点的数量和操作的数量
int p[N];

int find(int x){ // 返回x的祖宗节点+路径压缩
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    
    while (m -- ){
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        
        if (op[0] == 'M') p[find(a)] = find(b);
        else{
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

2.10堆

// h[N]存储堆中的值，h[1]是堆顶，x的左儿子是2x，右儿子是2x+1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b){
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u){
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t){
        heap_swap(u, t);
        down(t);
    }
}

void up(int u){
    while (u / 2 && h[u] < h[u / 2]){
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

2.11一般哈希

2.11.1模板

（1）拉链法
int h[N], e[N], ne[N], idx;

// 向哈希表中插入一个数
void insert(int x){
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++ ;
}

// 在哈希表中查询某个数是否存在
bool find(int x){
    int k = (x % N + N) % N;
    for (i = h[k]; i != -1; i = ne[i]){
        if (e[i] == x)
            return true;
    }
    
    return false;
}

（2）开放寻址法
int h[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回应该插入的位置
int find(int x){
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x){
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}

2.11.2模拟散列表

// 拉链法
#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010;

int h[N], e[N], ne[N], idx;

void insert(int x){
    int k = (x % N + N) % N;
    
    memset(h, -1, sizeof h);
    
    e[idx] = x, ne[idx] = h[k], h[k] = idx ++;
}

bool find(int x){
    int k = (x % N + N) % N;
    
    for (int i = h[k]; i != -1; i = ne[i]){
        if (e[i] == x)
            return true;
    }
}

int main(){
    int n;
    scanf("%d", &n);
    
    while (n -- ){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        
        if (*op == 'I') insert(x);
        else{
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

2.12字符串哈希

核心思想：将字符串看成p进制数，p的经验值是131或13331， 取这两个值冲突概率较低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值，p[k]存储p^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ ){
    h[i] = h[i - 1] * p + str[i];
    p[i] = p[i - 1] * p;
}

// 计算字串str[1 ~ r]的哈希值
ULL get(int l,  int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}

2.13C ++ STL简介

vector, 边长数组，倍增的思想
    size() 返回元素的个数
    empty() 返回是否为空
    clear() 清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
vector<int>::iterator it;
for (it = vec.begin(); it != vec.end(); it ++ )
    cout << *it << endl;

pair<int, int>
    first 第一个元素
    second 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
    
string 字符串
    size()/length() 返回字符串的长度
    empty()
    clear()
    substr(起始下标，(子串长度)) 返回字串
    c_str() 返回字符串数组的起始地址
    
queue 队列
    size()
    empty()
    push() 向队尾处插入一个元素
    front() 返回队尾元素
    pop() 弹出队头元素
    
priority_queue 优先队列，默认是大根堆
    size()
    empty()
    push()
    top()
    pop()
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack 栈
    size()
    empty()
    push() 向栈顶插入一个元素
    top() 返回栈顶元素
    pop() 弹出栈顶元素
    
dequeue 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度O(logn)
    
    set/multiset
    	insert() 插入一个数
    	find() 查找一个数
    	count() 返回某一个数的个数
    	erase()
    		（1）输入是一个数x，删除所有x O(k + logn)
    		（2）输入一个迭代器，删除这个迭代器
    	lower_bound()/upper_bound()
    		lower_bound(x) 返回大于等于x的最小的数的迭代器
    		upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
    insert() // 插入的数是一个pair
    erase() 输入的参数是pair或者迭代器
    find()
    [] 注意multimap不支持此操作。时间复杂度是O(logn)
    lower_bound()/upper_bound()
    
unordered_set, unordered_map, unordered_multiset, unordered_multimap，哈希表
    和上面的类似，增删改查的时间复杂度是O(1)
    不支持lower_bound()/upper_bound(), 迭代器的++， --
    
bitset 压位
    bitset<10000> s;
	~, &, |, ^
    >>, <<
    ==, !=
    []
    
    count() 返回有多少个1
    
    any() 判断是否至少有一个1
    none() 判断是否全为0
    
    set() 把所有位置为1
    set(k, v) 将第k位变为v
    reset() 把所有位变为0
    flip() 等价于~
    flip(k) 把第k位取反
    	

第三章 搜索与图论

3.1树与图的存储

树是一种特殊的图，与图的存储方式相同。

对于无向图中的边ab，存储两条有向边a->b, b->a。

因此我们可以只考虑有向图的存储。

（1）邻接矩阵：

g[a][b] 存储边a->b

（2）邻接表：

// 对于每个点k, 开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

3.2树与图的遍历

时间复杂度O(n + m)， n表示点数，m表示边数

3.2.1深度优先遍历

int dfs(int u){
    st[u] = true; // st[u] 表示点u已经被遍历过
    
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

3.2.1.1树的重心：

思路是DFS。从任意一个点出发进行DFS，同时计算如果删去之，所得剩余最大连通块节点个数。先搜集其所有未访问的子树的节点个数，每次搜集到一棵子树之后，就得到了该子树的节点个数（”当前“的意思是如果删去当前节点，所得最大连通块节点个数），搜集完所有子树之后，再用总结点个数减去所有子树节点和再减去当前节点自己，就得到了当前节点父亲的那棵子树节点个数，这样就得到了最大子树的节点个数。如果其小于等于

$$⌊ n / 2 ⌋$$

，说明当前点是重心（证明参考https://blog.csdn.net/qq_46105170/article/details/125841504），答案已经求出，将这个信息返回给上一层；否则返回当前节点子树的节点个数给上一层。

在深度优先遍历的过程中可以求出每个点的子树的点的数量

而当前节点上面的连通块的点的数量就是总的点数n减去当前点所有子树的点之和后得到的数

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 2 * N;

int n, m;
int h[N], e[M], ne[M], idx;
bool st[N];

int ans = N;

void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }

// 以u为根的子树的点的数量
int dfs(int u){
	st[u] = true;
    
    int sum = 1, res = 0; // 当前点的数量，每一个连通块点数量的最大值
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if (!st[j]){
            int s = dfs(j); // 当前子树的大小
            res = max(res, s); // 当前子树也相当于一个连通块，需要比较
            sum += s; // 当前子树是以u为根的子树的点的数量的一部分，需要加和
        }
    }
    
    // 外层的那个剩余的部分
    res = max(res, n - sum);
    
    ans = min(ans, res);
    
    return sum;
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n - 1; i ++ ){
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    dfs(1);
    
    printf("%d\n", ans);
    
    return 0;
}

3.2.1.2排列数字

#include <iostream>


using namespace std;

const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u){
    if (u == n){
        for (int i = 0; i < n; i ++ ) printf("%d", path[i]);
        puts("");
       	return;
    }
    
    for (int i = 1; i <= n; i ++ ){
        if (!st[i]){
            path[u] = i;
            st[i] = true;
            
            dfs(u + 1);
            
            path[u] = 0;
            st[i] = false;
        }
    }
}

int main(){
    cin >> n;
    
    dfs(0);
    
    return 0;
}

3.2.1.3n-皇后问题（全排列搜索顺序）

#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N]; // 一种方案
bool col[N], dg[N], udg[N]; // 行 对角线 反对角线

void dfs(int u){
    if (u == n){
        for (int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
        return;
    }
    
    for (int i = 0; i < n; i ++ ){
        if (!col[i] && !dg[u + i] && !udg[n - u + i]){
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
    }
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';
    
    dfs(0);
    
    return 0;
}

3.2.1.4n-皇后问题（逐个格子进行枚举搜索）

#include <iostream>

using namespace std;

const int N = 10;

int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];



void dfs(int x, int y, int s){
    if (y == n) y = 0, x ++ ; // 当前行的格子全部枚举完了，横坐标置为0，纵坐标跳到下一行
    
    if (x == n){ // 全部格子枚举完了
        if (s == n){ // 皇后的个数等于n了，找到了一组解
            for (inr i = 0; i < n; i ++ ) puts[g[i]];
            puts("");
        }
        return;
    }
    
    // 每个格子有下面两种处理方式
    //  不放皇后
    dfs(x, y + 1, s); // 不放皇后，递归到下一个格子
    
    // 放皇后，需要判断:这一行没有、这一列没有、对角线没有、反对角线也没有皇后，才可以放
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]){
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';
    
    dfs(0, 0, 0);
    
    return 0;
}

3.2.2宽度优先遍历

3.2.2.1模板

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size()){
    int t = q.front();
    q.pop();
    
    for (int i = h[t]; i != -1; i = ne[i]){
        int j = e[i];
        if (!st[j]){
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

3.2.2.2图中点的层次

本题是图的存储+BFS的结合

图的存储用邻接表

图的权值是1的时候，重边和环不用考虑。

所有长度都是1，表示可以用BFS来求最短路，否则应该用迪杰斯特拉等算法来求图中的最短路径。

BFS需要记录的是出发点到当前点的距离，就是d数组，每次d要增加1。

一定要注意数组的初始化！！！！

memset(h, -1, sizeof h); //数组的整体初始化为-1，这是链表结束循环的边界，缺少会TLE
memset(d,-1,sizeof d); //表示没有走过。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 10010, M = N << 1;

int n, m;
int h[N], e[M], ne[M], idx;
int d[N];

void add(int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs(){
	queue<int> q;
	q.push(1);
	
	memset(d, -1, sizeof d);
	d[1] = 0;
	
	while (q.size()){
		auto t = q.front();
		q.pop();
		
		for (int i = h[t]; i != -1; i = ne[i]){
			int j = e[i];
			if (d[j] == -1){
				d[j] = d[t] + 1;
				q.push(j);
			}
		}
	}
	
	return d[n];
}

int main(){
	memset(h, -1, sizeof h);
	
	cin >> n >> m;
	
	for (int i = 1; i <= m; i ++ ){
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	
	cout << bfs() << endl;
	
	return 0;
}

3.2.2.3走迷宫

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N]; // 存储迷宫
int d[N][N]; // 存储每个点到起始点的距离
PII q[N * N], Prev[N][N]; // 队列

int bfs(){
    int hh = 0, tt = 0; // 队头hh 队尾tt
    q[0] = {0, 0}; // 把起始点加入队列准备扩展
    
    memset(d, -1, sizeof d); // 表示没有走过
    d[0][0] = 0; // 代表【0，0】已经走过并且距离起始点的距离是0
    
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    while (hh <= tt){
        auto t = q[hh ++ ];
        
        for (int i = 0; i < 4; i ++ ){
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                d[x][y] = d[t.first][t.second] + 1;
                Prev[x][y] = t;
                q[ ++ tt] = {x, y};
            }
        }
    }
    // 使用Prev数组往前推
    int x = n - 1, y = m - 1;
    while (x || y){ // x y不同时为0，也就是不是起始点的时候
        cout << x << ' ' << y << endl;
        auto t = Prev[x][y];
        x = t.first, y = t.second;
    }
    
    return d[n - 1][m - 1];
}

int main(){
    cin >> n >> m;
    
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m ; j ++ )
            cin >> g[i][j];
    
    cout << bfs() << endl;
    
    return 0;
}

3.3完全二叉树

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10000 + 10;

int n;
long long q[N];

int main(){
    cin >> n;
    
    for (int i = 1; i <= n; i ++ ) cin >> q[i];
    
    int max_ = -1e18;
    /*
    完全二叉树 每层的开头为 2 ^ (n - 1)结尾则是2^n - 1
    计算每层的数值只需要两个positioner分别指向开头和结尾
    */
    int depth = 1;
    int res = 1;
    for (int i = 1; i <= n; i *= 2){
        long long s = 0;
        for (int j = i; j <= i * 2 - 1 && j <= n; j ++ ){
            s += q[j];
        }
        if (s > max_){
            max_ = s;
            res = depth;
        }
        depth ++ ;
    }
    cout << res;
    
    return 0;
}

3.4堆优化版Dijkstra

// 时间复杂度O(mlogn) , n表示点数，m表示边数
typedef pair<int, int> PII;

int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号的距离
bool st[N]; // 存储每个点的最短距离是否已经确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1}); // firatu存储距离，second存储节点的编号
    
    while (heap.size()){
        auto t = heap.top();
        heep.pop();
        
        int ver = t.second, distance = t.first;
        
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if (dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

3.4.4Dijkstra求最短路（朴素）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ ){
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        
        st[t] = true;
        
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    scanf("%d%d", &n, &m);
    
    memset(g, 0x3f, sizeof g);
    
    while (m -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    
    int t = dijkstra();
    
    printf("%d\n", t);
    
    return 0;
}

3.4.5Dijkstra求最短路（堆优化）

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0; // 到1号点的距离是0
    
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1}); // 1号点的距离已经知道了，我们需要用它来更新其他点，距离是0，编号是1
    
    while (heap.size()){
        auto = heap.top(); // 每次找到距离最短的点
        heap.pop();
        
        int ver = t.second, distance = t.first;
        if (st[ver]) continue; // 这个点已经出现过，是一个冗余备份，我们跳过即可
        
        for (int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i]; // j存储当前点的编号
            if (dist[j] > distance  + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    
    while (m -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    int t = dijkstra();
    
    printf("%d\n", t);
    
    return 0;
}

3.5Bellman-Ford算法

// 时间复杂度O(nm)，n表示点数，m表示边数
int n, m;
int dist[N]; // dist[x] 存储1到x的最短路距离

struct Edge{ // 边， a表示出点，b表示入点，w表示边权
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1
int bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    // 如果第n次迭代任然会松弛三角不等式，就说明存在一条长度是n + 1的最短路径，由抽屉原理，路径中至少存在两个相同的点， 说明图中存在负权回路。
    for (int i = 0; i < n; i ++ ){
        for (int j = 0; j < m; j ++ ){
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w){
                dist[b] = dist[a] + w;
            }
        }
    }
    
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

3.5.1有边数限制的最短路

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010;

int n, m;
int dist[N], backup[N];

struct Edge{
    int a, b, w;
}edges[M];

int bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < k; i ++ ){
        memcpy(backup, dist, sizeof dist);
        for (tin j = 0; j < m; j ++ ){
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w); // 只用上一次的结果，来更新当前的距离
            
        }
    }
    
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    
    for (int i = 0; i < m; i ++ ){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &m);
        edges[i] = {a, b, w};
    }
    
    int t = bellman_ford();
    
    if (t == -1) puts("impossible");
    else printf("%d\n", t);
    
    return 0;
}

3.6spfa算法（队列优化的Bellman_Ford算法）

// 时间复杂度平均情况下O(m), 最坏情况下O(nm)，n表示点数，m表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N];
bool st[N]; // 存储每个点是否在队列中

// 求1号点到n号点的最短距离，如果1号点无法走到n号点则返回-1
int spfa(){
    memset(dist, 0x3f, sizeof 0x3f);
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while (q.size()){
        auto t = q.front();
        q.pop();
        
        st[t] = false;
        
        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                if (!st[j]){ // 如果队列中已存在j，则不需要将j重复插入
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

3.7spfa判断图中是否存在负环

// 时间复杂度O(nm)，n表示点数，m表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中

// 如果存在负环，则返回true， 否则返回false
bool spfa(){
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n + 1个点，由抽屉原理一定有两个点相同，所以存在环
    
    queue<int> q;
    for (int i = 1; i <= n; i ++ ){
        q.push(i);
        st[i] = true;
    }
    
    while (q.size()){
        auto t = q.front();
        q.pop();
        
        st[t] = false;
        
        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (dist[j] > dist[t] + w[i]){
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    return false;
}

3.8floyd算法

// 时间复杂度是O(n^3)，n表示点数
// 初始化
for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= n; j ++ )
        if (i == j) d[i][j] = 0;
		else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd(){
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

3.8.1Floyd求最短路

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];

void floyd(){
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            for (int k = 1; k <= n; k ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main(){
    scanf("%d%d%d", &n, &m, &Q);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
    		else d[i][j] = INF;
    
    while (m -- ){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        
        d[a][b] = min(d[a][b], w);
    }
    
    floyd();
    
    while (Q -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        if (d[a][b] > INF / 2) printf("impossible");
        else printf("%d\n", d[a][b]);
    }
    return 0;
}

3.9朴素版prim

// 时间复杂度是O(n^2 + m), n表示点数，m表示边数
int n; // n表示点数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中

// 如果图不连通，则返回INF（0x3f3f3f3f），否则返回最小生成树的树边权重之和
int prim(){
    memset(dist, 0x3f, sizeof dist);
    
    int res = 0;
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ ){
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        
        if (i && dist[t] == INF) return INF;
        
        if (i) res += dist[t];
        st[t] = true;
        
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }
    
    return res;
}

3.9.1Prim算法求最小生成树

#include <cstirng>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim(){
    memset(dist, 0x3f, sizeof dist);
    
    int res = 0;
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
        if (i && dist[t] == INF) return INF;
        if (i) res += dist[t];
        
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
        
        st[t] = true;
        
    }
    
    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    
    memset(g, 0x3f, sizeof g);
    
    while (m -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    
    int t = prim();
    
    if (t == INF) puts("impossible");
    else printf("%d\n", t);
    
    return 0;
}

3.10Kruskal算法

// 时间复杂度O(mlogm)，n表示点数，m表示边数
int n, m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组
struct Edge{
    int a, b, w;
    
    bool operator< (const Edge &W)const{
        return W < W.w;
    }
}edges[M];

int find(int x){ // 并查集核心操作
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal(){
    sort(edges, edges + m);
    
    for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
    
    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ){
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        
        a = find(a), b = find(b);
        if (a != b){ // 如果两个连通块不连通，则将这两个连通块合并
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }
    
    if (cnt < n - 1) return INF;
    return res;
}

第四章 数学知识

4.1试除法判定质数

bool is_prime(int x){
    if (x < 2) return false; // 第一个质数从2开始
    for (int i = 2; i <= x / i; i ++ ){ // 枚举到sqrt(x)即可
        if (x % i == 0) // 如果出现了1和它本身以外的约数，那么判断不是质数
            return false;
    }
    return true;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

bool is_prime(int x){
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ ){
        if (x % i == 0) return false;
    }
    return true;
}

int main(){
    cin >> n;
    
    for (int i = 1; i <= n; i ++ ){
    	if (is_prime(i)) cout << i << endl;
	}
    
    return 0;
}

4.2试除法分解质因数

void divide(int x){
    for (int i = 2; i <= x / i; i ++ ){
        if (x % i == 0){
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

void divide(int x){
    for (int i = 2; i <= x / i; i ++ ){
        if (x % i == 0){
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

int main(){
    cin >> n;
    
    divide(n);
    
    return 0;
}

4.3朴素筛法求素数

int primes[N], cnt; // primes[]存储所有的素数
bool st[N]; // st[x]存储x是否被筛掉

void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i){
            st[j] = true;
        }
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100;

int n;
int primes[N], cnt; // primes[]存储所有的素数
bool st[N]; // st[x]存储x是否被筛掉

void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i){
            st[j] = true;
        }
    }
}

int main(){
    cin >> n;
    
    get_primes(n);
    
    for (int i = 0; i < N; i ++ ) cout << primes[i] << endl;
    
    return 0;
}

4.4线性筛法求素数

int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉

void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ){
            st[primes[j] * i] = true;
            if (i % primses[j] == 0) break;
        }
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100;

int n;
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉

void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main(){
    cin >> n;
    
    get_primes(n);
    
    for (int i = 0; i < n; i ++ ) cout << primes[i] << endl;
    
    return 0;
}

4.5试除法求所有约数

vector<int> get_divisors(int x){
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ ){
        if (x % i == 0){
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

vector<int> get_divisors(int x){
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ ){
        if (x % i == 0){
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int main(){
	vector<int> res;
	
    cin >> n;
    
    res = get_divisors(n);
    
    for (auto x : res) cout << x << endl;
    
    return 0;
}

4.6约数个数之和

4.6.1如果数N可以表示为

$$N = p_1^{c_1} \times p_2^{c_2} \times \cdots \times p_k^{c_k}$$

4.6.2约数的个数为

$$(c_1 + 1) \times (c_2 + 1) \times \cdots \times (c_k + 1)$$

4.6.3约数之和为

$$(1+p_1+p_1^2+\cdots+p_1^{c_1})\times(1+p_2+p_2^2+\cdots+p_2^{c_2})\times\cdots\times(1+p_k+p_k^2+\cdots+p_k^{c_k})$$

4.7欧几里得算法

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

4.8求欧拉函数

int phi(int i){
    int res = x;
    for (int i = 2; i <= x / i ; i ++ ){
        if (x % i == 0){
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    
    return res;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n;

int phi(int x){
    int res = x;
    for (int i = 2; i <= x / i; i ++ ){
        if (x % i == 0){
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    
    return res;
}

int main(){
    cin >> n;
    
    cout << phi(n);
    
    return 0;
}

4.8.1欧拉函数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;
    
    while (n -- ){
        int a;
        cin >> a;
        
        int res = a;
        for (int i = 2; i <= a / i; i ++ ){
            if (a % i == 0){ // i是a的一个质因子
                res = res / i * (i - 1);
                while (a % i == 0) a /= i; // a就把这个质因子除干净
                
            }
        }
        if (a > 1) res = res / a * (a - 1); // 说明a还有一个大于1的质因子
        cout << res << endl;
    }
    return 0;
}

4.9筛法求欧拉函数

int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; //st[x]存储x是否被筛掉

void get_eulers(int n){
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]){
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ ){
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0){
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1001;

int n;
int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; //st[x]存储x是否被筛掉

void get_eulers(int n){
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]){
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ ){
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0){
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

int main(){
    cin >> n;
    
    get_eulers(n);
    
    cout << euler[n];
    
    return 0;
}

4.10快速幂

求 m^k mod p, 时间复杂度 O(logk)

int qmi(int m, int k, int p){
    int res = 1 % p, t = m;
    while (k){
        if (k & 1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int qmi(int m, int k, int p){
    int res = 1 % p, t = m;
    while (k){
        if (k & 1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

int main(){
    cout << qmi(2, 1156165, 3);
    
    return 0;
}

4.11高斯消元

// a[N][N]是增广矩阵

第五章 动态规划

5.1 01背包问题

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

int n, m; // 物品个数，背包容量
int v[N], w[N]; // 物品体积 物品价值
int f[N][N]; // 状态属性

int main(){
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    // f[0][0~m], 表示考虑前0件物品，总体积不超过m的所有选法中的最大值
    for (int i = 1; i <= n; i ++ ) // 枚举所有的物品
        for (int j = 0; j <= m; j ++ ){ // 枚举所有体积
            f[i][j] = f[i - 1][j]; // 左边的情况一定存在
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); // 右边的情况不一定存在，只有当剩余的背包容量大于体积v[i]时才成立
        }
    
    cout << f[n][m] << endl; // 代表从前n件物品中，总体积不超过m的所有选法中价值最大的那一个，就是答案
    
    return 0;
}

5.2完全背包问题

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    
    cout << f[n][m] << endl;
}

5.3多重背包问题I

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int v[N], w[N], s[N]; 
int f[N][N];

int main(){
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++ ) cin >> v[i] >> w[i] >> s[i];
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ )
               f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    
    cout << f[n][m] << endl;
    
    return 0;
}

5.4多重背包问题||

5.5分组背包

#include <iostream>
#include <algorithm>

using namespace std;

const int N =110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main(){
    cin >> n >> m;
    
    for (i = 1; i <= n; i ++ ){
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }
    
    for (int i = 1; i <= n; i ++ ) // 从前往后枚举每一组
        for (int j = m; j >= 0; j -- ) // 从大到小枚举体积
            if (v[i][k] <= j)
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    
    cout << f[m] << endl;
    
    return 0;
}

第六章 贪心

第七章 时空复杂度分析

第八章 动态规划——从集合角度考虑DP问题

8.1数字三角形模型

第九章 搜索

第十章 图论

11.6最近公共祖先

11.6.1向上标记法

11.6.2倍增法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 40010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16];
int q[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int root){
    memset(depth, 0x3f, sizeof depth); // 初始时，dist初始化为正无穷
    depth[0] = 0, depth[root] = 1; // 其中0号点是哨兵，我们定义为0， 根结点是1
    int hh = 0, tt = 0;
    q[0] = root; // 根结点先加入到队列中去
    while (hh <= tt){ // 宽搜求这两个数组
        int t = q[hh ++ ];
        for (int i = h[t]; i != -1; i = ne[i])[
            int j = e[i];
            if (depth[j] > depth[t] + 1){
                depth[j] = depth[t] + 1;
                q[ ++ tt] = j;
                fa[j][0] = t;
                for (int k = 1; k <= 15; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
                
            }
        ]
    }
}

int lca(int a, int b){
    if (depth[a] > depth[b]) swap(a, b); // 如果a在b的上面，则交换
    // 跳到同一层，从高往低跳
    for (int k = 15; k >= 0; k -- ){
        if (depth[fa[a][k]] >= depth[b]) // 跳了之后，在b的下面或者是同一层
         a = fa[a][k]; // 那么说明a是可以跳的   
    }
    if (a == b) return a; // 说明a或者b就是公共祖先
    // 否则同时往上跳
    for (int k = 15; k >= 0; k -- ){
        if (fa[a][k] != fa[a][k]){ // 说明还没有跳到公众祖先上面
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

int main(){
    scanf("%d", &n);
    int root = 0; // 定义根结点
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n; i ++ ){
        int a, b;
        scanf("%d%d", &a, &b);
        if (b == -1) root = a; // b是-1，则a是根结点
        else add(a, b), add(b, a);
    }
    
    bfs(root);
    
    scanf("%d", &m);
    while (m -- ){
        int a, b;
        scanf("%d%d", &a, &b);
    	int p = lca(a, b);
    	if (p == a) puts("1");
    	else if (p == b) puts("2");
    	else puts("0");
    }
    
    return 0;
}

第十一章 高级数据结构

第十二章 数学知识

第十三章 基础算法

第十七章 图论

第十八章 数据结构

第十九章 动态规划

19.1数字三角形模型

19.1.1摘花生

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int n, m;
int w[N][N];
int f[N][N];

int main() {
    int T;
    scanf("%d%d", &n, &m);
    while (T -- ) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                scanf("%d", w[i][j]);
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                f[i][j] = max(f[i - 1][j] + w[i][j], f[i][j - 1] + w[i][j]);
        printf("%d\n", f[n][m]);
    }
    return 0;
}

19.1.2最低通行费

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, INF = 1e9;

int n;
int w[N][N];
int f[N][N];

int main() {
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            scanf("%d", &w[i][j]);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == 1 && j == 1) f[i][j] = w[i][j]; // 边界特判，特判左上角
    		else {
                f[i][j] = INF;
                if (i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]); // 只有不在第一行的时候，才可以从上面过来
                if (j > 1) f[i][j] = min(f[i][j - 1] + w[i][j], f[i][j]); // 只有不在第一列的时候，才可以从左面过来
            }
    
    printf("%d\n", f[n][n]);
    
    return 0;
}

19.1.3方格取数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int w[N][N];
int f[N * 2][N][N];

int main() {
    scanf("%d", &n);
    
    int a, b, c;
    while (cin >> a >> b >> c, a || b || c) w[a][b] = c;
    for (int k = 2; k <= n + n; k ++ )
        for (int i1 = 1; i1 <= n; i1 ++ )
            for (int i2 = 1; i2 <= n; i2 ++ ) {
                int j1 = k - i1, j2 = k - i2;
                if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n) {
                    int t = w[i1][j1];
                    if (i1 != i2) t += w[i2][j2];
                    int &x = f[k][i1][i2];
                    x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1 - 1][i2] + t);
                    x = max(x, f[k - 1][i1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1][i2] + t);
                }
            }
    printf("%d\n", f[n + n][n][n]);
    return 0;
}

19.2最长上升子序列（一）

19.2.1最长上升子序列朴素版

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
    for (int i = 1; i <= n; i ++ ) {
        // 空集
        f[i] = 1;
        for (int j = 1; j < i; j ++ )
            // 上升序列合法
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
    printf("%d\n", res);
    
    return 0;
}

19.2.2怪盗基德的滑翔翼

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int a[N], f[N];

int mian() {
    int T;
    scanf("%d", &T);
    while (T -- ) {
        scanf("%d", &n);
        // 读入每一个楼的高度
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
        // 正向求解LIS问题
        int res = 0;
        for (int i = 1; i <= n; i ++ ) {
            f[i] = 1;
            for (int j = 1; j < i; j ++ )
                if (a[i] > a[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        // 反向求解LIS
        for (int i = n; i; i -- ) {
            f[i] = 1;
            for (int j = n; j > i; j -- )
                if (a[i] > a[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        printf("%d\n", res);
    }
    
    return 0;
}

19.2.3登山

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N], g[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    // 从左往右求
    for (int i = 1; i <= n; i ++ ) {
        f[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
    }
    // 从右往左求
    for (int i = n; i; i -- ) {
        g[i] = 1;
        for (int j = n; j > i; j -- )
            if (a[i] > a[j])
                g[i] = max(g[i], g[j] + 1);
    }
    // 枚举中间值
    int res = 0;
    fro (int i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i] - 1);
    
    printf("%d\n", res);
    
    return 0;
}

19.2.4合唱队形

最少去掉多少个，就是最多留下的，也就成了登山题

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int a[N];
int f[N], g[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    // 从左往右求
    for (int i = 1; i <= n; i ++ ) {
        f[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
    }
    // 从右往左求
    for (int i = n; i; i -- ) {
        g[i] = 1;
        for (int j = n; j > i; j -- )
            if (a[i] > a[j])
                g[i] = max(g[i], g[j] + 1);
    }
    // 枚举中间值
    int res = 0;
    fro (int i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i] - 1);
    
    printf("%d\n", n - res);
    
    return 0;
}

19.2.5友好城市

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

int n;
PII q[N];
int f[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &q[i].first, &q[i].second);
    sort(q, q + n);
    
    int res = 0;
    for (int i = 0; i < n; i ++ ) {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (q[i].sceond > q[j].second) 
                f[i] = max(f[i], f[j + 1]);
        
        res = max(res, f[i]);
    }
    
    printf("%d\n", res);
    
    return 0;
}

19.2.6最大上升子序列和

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin << a[i];
    
    int res = 0;
    for (int i = 1; i <= n; i ++ ) {
        f[i] = a[i];
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[k])
                f[i] = max(f[i], f[j] + a[i]);
    }
    
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
    
    cout << res << endl;
    
    return 0;
}

19.2.7拦截导弹

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int q[N];
int f[N];
int g[N]; // 现有的所有子序列

int main() {
    while (cin >> q[n]) n ++ ;
    
    int res = 0;
    for (int i = 0; i < n; i ++ ) {
        int res = 0;
        for (int j = 0; j < i; j ++ )
            if (q[j] >= q[i])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    
    cout << res << endl;
    
    int cnt = 0; // 当前子序列的个数
    for (int i = 0; i < n; i ++ ) {
        int k = 0; // 从前往后找的序列
        // 只要我们没有遍历完序列 && 当前序列的结尾是小于当前数的
        while (k < cnt && g[k] < q[i]) k ++ ;
        g[k] = q[i];
        // 没有任何一个序列是大于等于当前数的
        if (k >= cnt cnt ++ ; // 开一个新的序列
    }
            
    cout << cnt << endl;
    
    return 0;
}

19.2.8导弹防御系统

#include <iostream>
#include <cstring>

using namespace std;

const int N = 55;

int n;
int q[N];
int up[N], down[N]; // 分别表示上升子序列的结尾和下降子序列的结尾
int ans; // 全局最小值，使用dfs进行更新

// u 当前枚举到了第几个数， su 当前上升子序列的个数，sd 当前下降子序列的个数
void dfs(int u, int su, int sd) {
    // 不可能使得答案变小了，直接返回
    if (su + sd >= ans) return;
    // 说明找到一个方案
    if (u == n) {
        // 更新 ans
        ans = su + sd;
        return;
    }
    
    // 情况1：将当前数放到上升子序列中
    int k = 0;
    // 先进行备份
    while (k < su && up[k] >= q[u]) k ++ ;
    int t = up[k];
    up[k] = q[u];
    if (k < su) dfs(u + 1, su, sd);
    else dfs(u + 1, su + 1, sd);
    // 恢复现场
    up[k] = t;
    
    // 情况2：将当前数放到下降子序列中
    k = 0;
    while (k < sd && down[k] <= q[u]) k ++ ;
    t = down[k];
    down[k] = q[u];
    if (k < sd) dfs(u + 1, su, sd);
    else dfs(u + 1, su, sd + 1);
    down[k] = t;
}

int main() {
    while (cin >> n, n) {
        for (int i = 0; i < n; i ++ ) cin >> q[i];
        // 进行暴搜之前，先记录最大值 n，就是最坏情况下，每个数单独一个序列
        ans = n;
        dfs(0, 0, 0);
        
        cout << ans << endl; 
    }
    
    return 0;
}

19.2.9最长公共上升子序列

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N]；
int f[N][N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ) {
            // 先考虑右半部分
            f[i][j] = f[i - 1][j];
            // 再考虑左半边，情况又细分为多种，需要依次枚举
            // 当 a[i] == b[j] 的时候才会存在
            if (a[i] == b[j]) {
                // 先考虑小块中存在的空集
                f[i][j] = max(f[i][j], 1);
                for (int k = 1; k < j; k ++ ) {
                    // 这里需要再判断每个小块是否存在
                    if (b[k] < b[j])
                        f[i][j] = max(f[i][j], f[i][k] + 1);
                }
            }
        }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    
    printf("%d\n", res);
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int n;
int a[N], b[]；
int f[N][N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
    
    for (int i = 1; i <= n; i ++ ) {
        int maxv = 1; // 满足 b[k]<a[i] 的情况下 1 到 j-1 的最大值
        for (int j = 1; j <= n; j ++ ) {
            // 先考虑右半部分
            f[i][j] = f[i - 1][j];
            // 再考虑左半边，情况又细分为多种，需要依次枚举
            // 当 a[i] == b[j] 的时候才会存在
            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv); // 将循环优化为它
            if (b[j] < a[i]) maxv = max(maxv, f[i][j] + 1);
        }
    }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    
    printf("%d\n", res);
    return 0;
}

19.3背包模型

多重背包III

完全背包

第二十章 计算几何

第二十一章 数学

第二十二章 搜索

第二十三章 基础算法

附录：练习题目

1.数的进制转换

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int T;
    cin >> T;
    while (T -- ){
        int a, b;
        string a_line, b_line;
        cin >> a >> b >> a_line;
        
        vector<int> number;
        for (auto c : a_line){
            if (c >= '0' && c <= '9') number.push_back(c - '0');
            if (c >= 'A' && c <= 'Z') number.push_back(c - 'A' + 10);
            if (c >= 'a' && c <= 'z') number.push_back(c - 'a' + 36);
        }
        reverse(number.begin(), number.end());
        
        vector<int> res;
        while (number.size()){
            int r = 0;
            for (int i = number.size() - 1; i >= 0; i -- ){
                number[i] += r * a;
                r = number[i] % b;
                number[i] /= b;
            }
            res.push_back(r);
            while (number.size() && number.back() == 0) number.pop_back();
        }
        
        reverse(res.begin(), res.end());
        for (auto x : res){
            if (x <= 9) b_line += char(x + '0');
            if (x >= 10 && x <= 35) b_line += char(x - 10 + 'A');
            if (x >= 36) b_line += char(x - 36 + 'a');
        }
        
        cout << a << ' ' << a_line << endl;
        cout << b << ' ' << b_line << endl;
        cout << endl;
    }
    
    return 0;
}

2.两数之和

暴力

class Solution{
public:
    vector<int> twoSum(vector<int> &nums, int target){
        for (int i = 0; i < nums.size() - 1; i ++ )
            for (int j = i + 1; j < nums.size(); j ++ )
                if (nums[i] + nums[j] == target)
                    return {i, j};
        return {};
    };
};

两遍哈希

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target){
        map<int, int> a; //建立hash表存放数组元素
        vector<int> b(2, -1); // 存放结果
        for (int i = 0; i < nums.size(); i ++ )
            a.insert(map<int, int>::value_type(nums[i], i));
        for (int i = 0; i < nums.size(); i ++ ){
            if (a.count(target - nums[i]) > 0 && (target - nums[i] != i)){
            // 判断是否找到目标元素且目标元素不能是本身
                b[0] = i;
                b[1] = a[target - nums[i]];
                break;
            }
        }
        return b;
    };
};

3.LeetCode暑期刷题打卡2019——Week1 二分专题

69.x的平方根

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r) {
            int mid = l + (long long)r + 1 >> 1;
            if (mid <= x / mid) l = mid;
            else r = mid - 1;
        }
        
        return r;
    }
};

35.搜索插入位置

class Solution {
public:
    int searchInsert(vector<int> &nums, int target) {
        if (nums.empty() || nums.back() < target) return nums.size();
        
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        
        return r;
    }
};

34.在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    vector<int> searchRange(vector<int> &nums, int target) {
        if (nums.empty()) return {-1, -1};
        
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        
        if (nums[r] != target) return {-1, -1};
        int start = l;
        
        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        int end = l;
        return {start, end};
    }
};

74.搜索二维矩阵

https://leetcode.cn/problems/search-a-2d-matrix/description/

class Solution {
public:
    bool searchMatrix(vector<int> &matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n * m - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[mid / m][mid % m] >= target) r = mid;
            else l = mid + 1;
        }
        
        if (matrix[r / m][r % m] != target) return false;
        return true;
    }
};

153.寻找旋转排序数组中的最小值

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/

class Solution {
public:
    int findMin(vector<int> &nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
        	int mid = l + r >> 1;
        	if (nums[mid] <= nums.back()) r = mid;
        	else l = mid + 1;
    	}
        
        return nums[r];
    }
};

33.搜索旋转排序数组

class Solution {
public:
    int search(vector<int> &nums, int target) {
        if (nums.empty()) return -1;
        
        // 找到最小值
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] <= nums.back()) r = mid;
            else l = mid + 1;
        }
        
        if (target <= nums.back()) r = nums.size() - 1;
        else l = 0, r -- ;
        
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        
        if (nums[l] == target) return l;
        else return -1;
    }
};

278.第一个错误的版本

bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            int mid = (long long)l + r >> 1;
            if (isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        
        return r;
    }
};

162.寻找峰值

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;

        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }

        return r;
    }
};

287.寻找重复数

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;

            int cnt = 0;
            for (auto x: nums) {
                if (x >= l && x <= mid)
                    cnt ++ ;
            }

            if (cnt > mid - l + 1) r = mid;
            else l = mid + 1;
        }

        return r;
    }
};

275.H指数 II

class Solution {
public:
    int hIndex(vector<int> &nums) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[nums.size() - mid] >= mid) l = mid;
            else r = mid - 1;
        }
        
        return r;
    }
};

19.删掉倒数第n个结点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode *head, int n) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        
        auto first = dummy, second = dummy;
        while (n -- ) first = first->next;
        while (first->next) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        
        return dummy->next;
    }
};

237.删除链表中的结点

class Solution {
public:
    void deleteNode(ListNode *node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

class Solution {
public:
    void deleteNode(ListNode *node) {
        *(ndoe) = *(node->next);
    }
};

83.从排序列表中删除重复项

class Solution {
public:
    ListNode* deleteDuplicates(ListNode *head) {
        auto cur = head;
        while (cur) {
            if (cur->next && cur->next->val == cur->val)
                cur->next = cur->next->next;
            else cur = cur->next;
        }
        return head;
    }
};

61.旋转链表

class Solution {
public:
    ListNode* rotateRight(ListNode *head, int k){
        if (!head) return NULL;
        
        int n = 0;
        for (auto p = head; p; p = p->next) n ++ ;
        
        k %= n;
        auto first = head, second = head;
        while (k -- ) first = first->next;
        while (first->next) {
            first = first->next;
            second = second->next;
        }
        
        first->next = head;
        head = second->next;
        second->next = NULL;
        
        return head;
    }
};

24.交换链表中相邻的两个节点，最后返回头结点

class Soultion {
public:
    ListNode * swapPairs(ListNode *head){
        auto dummy = new ListNode(-1);
        dummy->next = head;
        
        for (auto p = dummy; p->next && p->next->next;) {
            auto a = p->next, b = a->next;
            p->next = b;
            a->next = b->next;
            b->next = a;
            p = a;
        }
        
        return dummy->next;
    }
};

206.翻转链表I

class Solution {
public:
    ListNode* reverseList(ListNode *head) {
        if (!head) return NULL;
        
        auto a = head, b = head->next;
        while (b) {
            auto c = b->next;
            b->next = a;
            a = b, b = c;
        }
        
        head->next = NULL;
        
        return a;
    }
};

92.翻转链表II

class Solution {
public:
    ListNode* reverseBetween(ListNode *head, int m, int n) {
        if (m == n) return head;
        // 定义虚拟节点
        auto dummy = new ListNode(-1);
        dummy->next = head;
        // 找到b和d的位置
        auto a = dummy, d = dummy;
        for (int i = 0; i < m - 1; i ++ ) a = a->next;
        for (int i = 0; i < n; i ++ ) d = d->next;
        // 进行翻转
        auto b = a->next, c = d->next;
        
        for (auto p = b, q = b->next; q != c; ) {
            auto o = q->next;
            q->next = p;
            p = q, q = o;
        }
        // 改变指针
        a->next = d;
        b->next = c;
        
        return dummy->next;
    }
};

160.两个链表的交点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        while (p != q) {
            if (p) p = p->next;
            else p = headB;
            if (q) q = q->next;
            else q = headA;
        }
        
        return p; 
    }
};

142.链表循环II

class Solution {
public:
    ListNode* detectCycle(ListNode *head) {
        auto fast = head, slow = head;
        while (slow) {
            fast = fast->next;
            slow = slow->next;
            if (slow) slow = slow->next;
            else break;
            
            if (fast == slow) {
                slow = head;
                while (slow != fast) {
                    fast = fast->next;
                    slow = slow->next;
                }
                
                return slow;
            }
        }
        return NULL;
    }
};

148.排序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        
        int n = 0;
        for (auto p = head; p; p = p->next) n ++ ;
        auto dummy = new ListNode(-1);
        dummy->next = head;

        for (int i = 1; i < n; i *= 2) {
            auto cur = dummy;
            for (int j = 0; j + i < n; j += i * 2) {
                auto left = cur->next, right = cur->next;
                for (int k = 0; k < i; k ++ ) right = right->next;
                int l = 0, r = 0;
                while (l < i && r < i && right) {
                    if (left->val <= right->val) {
                        cur->next = left;
                        cur = left;
                        left = left->next;
                        l ++ ;
                    }else {
                        cur->next = right;
                        cur = right;
                        right = right->next;
                        r ++ ;
                    }
                }
                while (l < i) {
                    cur->next = left;
                    cur = left;
                    left = left->next;
                    l ++ ;
                }
                while (r < i && right) {
                    cur->next = right;
                    cur = right;
                    right = right->next;
                    r ++ ;
                }

                cur->next = right;
            }
        }
        return dummy->next;
    }
};

98.判断二叉搜索树

class Solution {
public:
    bool isVaildBST(TreeNode *root) {
        return dfs(root, INT_MIN, INT_MAX);
    }
    
    bool dfs(TreeNode *root, long long minv, long long maxv){
        if (!root) return true;
        if (root->val < minv || root->val > maxv) return false;
        
        return dfs(root->left, miv, root->val - 1ll) && dfs(root->right, root->val + 1ll, maxv);
    }
}

94.二叉树的中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode*> stk;
        
        auto p = root;
        while (p || stk.size()){
            while (p){
                stk.push(p);
                p = p->left;
            }
            
            p = stk.top();
            stk.pop();
            res.push_back(p->val);
            p = p->right;
        }
        
        return res;
    }
}

101.镜像二叉树

class Solution {
public:
    bool isSymmetric(TreeNode *root){
        if (!root) return true; // 空节点是特殊的镜像二叉树
        return dfs(root->left, root->right);
    }
    
    bool dfs(TreeNode *p, TreeNode *q){
        if (!p || !q) return !p && !q; // 只有当左右子树同时为空时才为对称二叉树
        return p->val == q->val && dfs(p->left, q->right) && dfs(p->right, q->left);
    }
};

// 迭代法
// 左边：左中右遍历；右边：右中左遍历，同时检查是否相等
class Solution{
public:
    bool isSymmetric(TreeNode *root){
        if (!root) return true;
        stack<TreeNode*> left, right;
        auto l = root->left, r = root->right;
        while (l || r || left.size() || right.size()){
            while (l && r){
                left.push(l), l = l->left;
                right.push(r), r = r->right;
            }
            
            if (l || r) return false;
            
            l = left.top(), left.pop();
            r = right.top(), right.pop();
            if (l->val != r->val) return false;
            
            l = l->right, r = r->left;
        }
        return true;
    }
};

105.通过前序和中序构建二叉树

class Solution{
public:
    unordered_map<int, int> pos;
    
    TreeNode *buildTree(vector<int> & preorder, vector<int> &inorder){
        int n = preorder.size();
        for (int i = 0; i < n; i ++ ) pos[inorder[i]] = i;
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }
    
    TreeNode *dfs(vector<int> &preorder, vector<int> &inorder, int pl, int pr, int il, int ir){
        if (pl > pr) return NULL;
        
        int val = preorder[pl];
        // 前序遍历的起点、终点；中序遍历的起点、终点
        int k = pos[val]; //  前序遍历点在中序遍历中的位置
        int len = k - il; // 左子树长度
        auto root = new TreeNode(val);
        root->left = dfs(preorder, inorder, pl + 1, pl + len, il, k - 1);
        root->right = dfs(preorder, inorder, pl + len + 1, pr, k + 1, ir);
        return root;
    }
};

102.层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode *root){
        vector<vector<int>> res;
        
        if (!root) return res;
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (q.size()){
            int n = q.size(); // 当前这一层点的个数
            vector<int> level; //当前遍历的结果
            
            for (int i = 0; i < len; i ++ ){
                auto t = q.front();
                q.pop();
                level.push_back(t->val);
                
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            
            res.push_back(level);
        }
        
        return res;
    }
};

236.求两个点的最近公共祖先

class Solution{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q){
        // 如果以root为根的子树中包含q和q,则返回他们的最近公共祖先
        // 如果只包含p, 则返回p
        // 如果只包含q, 则返回q
        // 如果都不包含，则返回NULL
        if (!root || root == p || root == q) return root;
        
        auto left = lowestCommonAncestor(root->left, p, q);
        auto right = lowestCommonAncestor(root->right, p, q);
        
        if (!left) return right;
        if (!right) return left;
        return root;
    }
};

543.二叉树的直径

class Solution{
public:
    int ans = 0;
    
    int diameterOfBinaryTree(TreeNode *root){
        dfs(root);
        
        return ans;
    }
    
    int dfs(TreeNode *root){
        if (!root) return 0;
        auto left = dfs(root->left);
        auto right = dfs(root->right);
        
        ans = max(ans, left + right);
        return max(left + 1, right + 1);
    }
};

124.二叉树最大路径和

class Solution {
public:
    
    int ans = INT_MIN;
    
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
    
    // 返回从root向下走的最大值
    int dfs(TreeNode *root){
        // 如果当前为空，则不存在
        if (!root) return 0;
        
        // 分别求从左子树向下走的最大值和从右子树向下走的最大值
        auto left = dfs(root->left);
        auto right = dfs(root->right);
        // 答案是从当前答案、左子树+右子树+当前值中的最大值
        ans = max(ans, left + right + root->val);
        
        // 返回分为：向左走、向右走、不走，0就没有必要返回了，返回0宁可不要
        return max(0, root->val + max(left, right));
    }
};

173.二叉树迭代器

// 时间复杂度O(1) 空间复杂度O(h), 即可用栈来模拟中序遍历的过程，栈的最大长度和树的高度成正比
class BSTIterator {
public:
    
    stack<TreeNode*> stk;
    
    BSTIterator(TreeNode* root) {
        // 初始化时，将树的最左边那条链插入到栈中
        while (root){
            // 每一次把根节点插入
            stk.push(root);
            root = root->left;
        }
    }
    
    // 每次调用返回中序遍历的下一个节点
    int next() {
        // 每次取next就是取栈顶元素
        auto p = stk.top();
        stk.pop();
        
        // 每次遍历完一个点的时候，就需要将右子树加入栈
        // 首先保存答案，因为最后要返回答案
        int res = p->val;
        // 先指向右子树
        p = p->right;
        // 将右子树加进来，就是将最左边的一条链加进来
        while (p){
            stk.push(p);
            p = p->left;
        }
        
        return res;
    }
    
    // 询问是否有下一个节点
    bool hasNext() {
        // 当我们遍历完所有点的时候，我们的栈就是空的
        return !stk.empty();
    }
};

297.序列化和反序列化二叉树

• 仅有前序遍历的话，是不能唯一确定一颗二叉树

• 前序遍历 + 中序遍历/后序遍历 + 中序遍历，就可以唯一确定一颗二叉树

• 但是如果前序、中序、后序遍历序列中包含了空节点，那么也可以唯一确定二叉树

class Codec {
public:
    // 序列化：二叉树转字符串
    string serialize(TreeNode* root){
        string res;
        
        dfs1(root, res);
        
        return res;
    }
    
    void dfs1(TreeNode* root, string &res){
        // 如果当前节点为空
        if (!root){
            res += "#,";
            return;
        }
        // 否则，先遍历根节点，先加上当前节点的值，加上逗号
        res += to_string(root->val) + ',';
        // 遍历完根节点，就遍历左子树和右子树
        dfs1(root->left, res);
        dfs1(root->right, res);
    }
    
    // 反序列化：字符串转二叉树
    TreeNode* deserialize(string data){
        // 需要一个指针，指向当前构建到哪个字符了
        int u = 0;
        return dfs2(data, u);
    }
    
    // 返回根节点的指针
    TreeNode* dfs2(string &data, int &u){
        // 如果当前字符是#，那就跳过2个位置
        if (data[u] == '#'){
            u += 2;
            return NULL;
        }
        
        // 当前节点不空，那就先求出当前节点的值
        // 节点中的值可能是负数，那就需要特判
        int t = 0;
        bool is_minus = false;
        if (data[u] == '-'){
            is_minus = true;
            u ++ ;
        }
        // 只要指针没有碰到逗号，就一直做
        while (data[u] != ','){
            // 计算值
            t = t * 10 + data[u] - '0';
            u ++ ;
        }
        // 最后还有加加，是为了跳过逗号
        u ++ ;
        // 是否是负数
        if (is_minus) t = -t;
        
        // 创建根节点，之后是根左右的顺序
        auto root = new TreeNode(t);
        root->left = dfs2(data, u);
        root->right = dfs2(data, u);
        
        return root;
    }
};

38.计数然后说

class Solution {
public:
    string countAndSay(int n){
        string s = "1";
        // 产生第n行，递推n-1次即可
        for (int i = 0; i < n - 1; i ++ ){
            // 先定义上一行的字符串，是空的
            string ns;
            // 然后遍历当前这一行中所有连续的段，从前往后枚举每一个位置
            for (int j = 0; j < s.size(); j ++ ){
                int k = j;
                while (k < s.size() && s[k] == s[j]) k ++ ;
                ns += to_string(k - j) + s[i];
                j = k - 1;
            }
            s = ns;
        }
        return s;
    }
};

49.Group Anagrams

class Solution{
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs){
        unordered_map<string, vector<string>> hash;
        for (auto str : strs){
            string key = str;
            // 乱序字符串的本质是排序后都是一样的
            sort(key.begin(), key.end());
            // 将排序后一样的字符串作为key，原来的字符串作为值，这样就做到了分组的效果
            hash[key].push_back(str);
        }
        
        vector<vector<int>> res;
        for (auto item : hash) res.push_back(item.second);
        return res;
    }
};

151.Reverse Words in a String

class solution{
public:
    string reverseWords(string s){
        int k = 0;
        for (int i = 0; i < s.size(); i ++ ){
            // 过滤所有的空格
            while (i < s.size() && s[i] != ' ') i ++ ;
            if (i == s.size()) break;
            // 找到一段连续的非空格
            int j = i;
            while (j < s.size() && s[j] != ' ') j ++ ;
            reverse(s.begin() + i, s.begin() + j);
            // 若k不是0，则先需要隔开一个空格
            if (k) s[k ++ ] = ' ';
            // 复制过程
            while (i < j) s[k ++ ] = s[i ++ ];
        }
        // k后多余的部分删去
        s.erase(s.begin() + k, s.end());
        // 最后再翻转一遍
        reverse(s.begin(), s.end());
        return s;
    }
};

165.Compare Version Numbers

如何找到字符串中的数字？

class Solution{
public:
    int compareVersion(string s1, string s2){
        // 定义两个指针，分别从0开始
        int i = 0, j = 0;
        // 两个指针只要有一个不空，就一直做
        while (i < s1.size() || j < s2.size()){
        	int x = i, y = j;
            while (x < s1.size() && s1[x] != '.') x ++ ;
            while (y < s2.size() && s2[y] != '.') y ++ ;
            
            // 特判一些，可能为0
            int a = i == x ? 0 : atoi(s1.substr(i, x - i).c_str());
            int b = j == y ? 0 : atoi(s2.substr(j, y - j).c_str());
            // 返回答案
            if (a > b) return 1;
            if (a < b) return -1;
            // 跳过'.'
            i = x + 1, j = y + 1;
        }
        return 0;
    }
};

929.Unique Email Addresses

先处理邮箱字符串

后使用哈希表数出不同的邮箱的种类

class Solution{
public:
    int numUniqueEmails(vector<string>& emails){
        unordered_set<string> hash;
        for (auto email : emails){
            int at = email.find('@');
            string name;
            for (auto c : email.substr(0, at));
            if (c == '+') break;
            else if (c != '.') name += c;
            string doumain = email.substr(at + 1);
            hash.insert(name + '@' + doumain);
        }
        return hash.size();
    }
};

5.Longest Palindromic Substring

返回最长回文串

class Solution{
public:
    string longestPalindrome(string s){
        string res;
        // 遍历字符串
        for (int i = 0; i < s.size(); i ++ ){
            int j, k; // j 往左走，k 往右走
            // 回文串长度是奇数
            for (j = i, k = i; j >= 0 && k < s.size() && s[j] == s[k]; j --, k ++ ){
                if (res.size() < k - j + 1)
                    res = s.substr(j, k - j + 1);
            }
            // 回文串长度是偶数
            for (j = i, k = i + 1; j >= 0 && k < s.size() && s[j] == s[k]; j --, k ++ ){
                if (res.size() < k - j + 1)
                    res = s.substr(j, k - j + 1);
            }
            return res;
        }
    }
};

6.ZigZag Conversion

class Solution{
public:
    string convert(string s, int n){
        // 特判，后面有i == n - 1的判断
        if (n == 1) return s;
        string res;
        // 枚举行
        for (int i = 0; i < n; i ++ ){
            
            // i = 0 或者 i == n - 1就是公差是2 * (n - 1)的等差数列
            if (!i || i == n - 1){
                for (int j = i; j < s.size(); j += 2 * (n - 1)) res += s[j];
            }else{
                // 两个等差数列交错
                for (int j = i, k = 2 * (n - 1) - i; j < s.size() || k < s.size(); j += 2 * (n - 1), k += 2 * (n - 1)){
                    if (j < s.size()) res += s[j];
                    if (k < s.size()) res += s[k];
                }
            }
        }
        return res;
    }
};

3.Longest Substring Without Repeating Characters

最长的没有包含重复字符的字符串

使用哈希表存储两个指针间出现没有重复字母的次数

class Solution{
public:
    int lengOfLongestSubstring(string s){
        unordered_map<char, int> hash;
        int res = 0;
        for (int i = 0, j = 0; i < s.size(); i ++ ){
            // 绿颜色的指针向后走的时候，会加进来一个新的字母
            hash[s[i]] ++ ;
            // 如果加完之后，两个指针间有重复字母，那么这个字母一定是s[i]
            // 有重复，那么将s[i]从Hash中删去，并让j后移
            while (hash[s[i]] > 1) hsah[s[j ++ ]] -- ;
            res = max(i - j + 1);
        }
        return res;
    }
};

208.Implement Tire (Prefix Tree)

class Trie {
public:
    
    // Tire树节点一般用结构体表示
    struct Node {
        // 有没有以这个节点为结尾的单词
        bool is_end;
        // 最多26个儿子
        Node *son[26];
        // 初始化
        Node() {
            is_end = false;
            for (int i = 0; i < 26; i ++ ) son[i] = NULL;
        }
    }*root;
    
    /** Initialize your data structure here. */
    Trie() {
        // 先创建根节点
        root = new Node();
    }
    
    /** Inserts a word into the trie*/ 
    void insert(string word) {
        // 就从根节点开始遍历
        auto p = root;
        // 从前往后遍历每一个字母
        for (auto c : word) {
            // 首先存储这个字母的编号
            int u = c - 'a';
            // 判断儿子是否存在，不存在就创建
            if (p->son[u] == NULL) p->son[u] = new Node();
            // p走到儿子上去
            p = p->son[u];
        }
        // 最后标记一下，现在有了以p结尾的单词
        p->is_end = true;
    }
    
    //
    bool search(string word) {
        // 查询也是一样，从前往后遍历这个单词
        auto p = root;
        for (auto c : word) {
            // 求一下当前的编号
            int u = c - 'a';
            // 如果当前儿子不存在的话，说明当前路径不存在，也就是说该单词不存在
            if (p->son[u] == NULL) return false;
            // 否则p继续向下走即可
            p = p->son[u];
        }
        // 最后进行判断是否有单词结束标记
        return p->is_end;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix*/ 
    bool startWith(string prefix) {
        // 查询也是一样，从前往后遍历这个单词
        auto p = root;
        for (auto c : prefix) {
            // 求一下当前的编号
            int u = c - 'a';
            // 如果当前儿子不存在的话，说明当前路径不存在，也就是说该单词不存在
            if (p->son[u] == NULL) return false;
            // 否则p继续向下走即可
            p = p->son[u];
        }
        // 找前缀，直接返回即可
        return true;
    }
};

273.Iteger to English Words

class Solution {
public:
    
    string small[20] = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    
    string decade[10] = {"", "", "Twenty", "Thrity", "Forty", "FIfty", "Sixty", "Seventy", "Eighty", "Ninety"};
    string big[4] = {"Billion", "Million", "Thousand", ""};
    
    string numberToWords(int num) {
        // 先判断num为0的特殊情况
        if (!num) return small[0];
        
        string res;
        // 开始枚举
        for (int i = 100000000, j = 0; i > 0; i /= 1000, j ++ ) {
            if (num >= i) {
                res += get_part(num / i) + big[j] + ' ';
                // 做完以后去除最大的三位
                num %= i;
            }
        }
        // 最后如果会多出很多空格，需要删除
        while (res.back() == ' ') res.pop_back();
        return res;
}
    // 输入1000以内的数，然后输出它
    string get_part(int num) {
        string res;
        // 如果大于等于100
        if (num >= 100) {
            // 先把百位输出
            res += small[num / 100] + " Hundred ";
            // 取出十位加个位数字，百位去除了
            num %= 100;
        }
        // 此时如等于0了，就不需要再做了
        if (!num) return res;
        // 如果小于20，可以直接取small
        if (num >= 20) {
            // 先输出十位
            res += decade[num / 10] + ' ';
            // 拿出个位，去除百位和十位
            num %= 10;
        }
        // 此时如等于0了，就不需要再做了
        if (!num) return res;
        // 最后加上小于20后的数字即可
        res += small[num] + ' ';
        return res;
    } 
};

4.寻找两个正序数组的中位数

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 先求数的总数
        int tot = nums1.size() + nums2.size();
        // 分两种情况
        // 如果 tot 是偶数
        if (tot % 2 == 0) {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }
    
    int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        // 假定第一个数组比较短，如果比较长的话，反过来做
        if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);
        // 处理边界问题，如果k=1,也就是只有一个数的话，那么取前两个数组的最小值即可，第一个数是第一数组的最小值，第二个数是第二数组的最小值，整个的最小值就是它们俩的最小值
        // 但是还需要特判
        if (k == 1) {
            // 第一个数组是空的
            if (nums1.size() == i) return nums2[j];
            // 否则返回最小值
            else return min(nums1[i], nums2[j]);
        }
        
        // 边界二，数组1是空的，那么k就是第二个数组的中位数
        if (nums1.size() == i) return nums2[j + k - 1];
        // si sj 是中间位置的下一个位置
        int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
        if (nums1[si - 1] > nums2[sj - 1]) {
            // 删除数组2的右半边
            return find(nums1, i, nums2, sj, k - (sj = j));
        } else {
            // 删除数组1的右半边
            return find(nums1, si, nums2, j, k - (si - i));
        }
    }
};

17.Letter Combinations of a Phone Number

class Solution {
public:
    // 备选字符
    string chars[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    vector<string> letterCombinations(string digits) {
        // 如果数字为空的话，返回的字符串为空
        if (digits.empty()) return vector<string>();
        
        vector<string> state(1, "");
        // 枚举所有的数字
        for (auto u : digits) {
            // 每次定义一个新的状态
            vector<string> now;
            // 取当前数字的备选字符，从 2 开始才有备选方案
            for (auto c : chars[u - '2']) {
                // 枚举上一次的所有状态
                for (auto s : state) {
                    now.push_back(s + c);
                }
            }
            state = now;
        }
        
        return state;
    }
};

79.Word Search

class Solution {
public:
    
    int n, m; // 矩阵的长和宽
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    bool exist(vector<<char>>& board, string word) {
        // 如果矩阵是空的，或者行是空的，直接返回
        if (board.empty() || board[0].empty()) return false;
        n = board.size(), m = board[0].size();
        
        for (int i = 0; i < n; i ++ )
        	for (int j = 0; j < m; j ++ )
        		if (dfs(board, i, j, word, 0))
        			return true;
        return false;
    }
    // x, y 表示矩阵中的位置，u 表示单词中的位置
    bool dfs(vector<vector<char>>& board, int x, int y, string& word, int u) {
        // 如果当前矩阵的位置上字符不等于单词的字符
        if (board[x][y] != word[u]) return false;
        // 如果全部匹配了，直接返回
        if (u == word.size() - 1) return true;
        
        // 否则，当前这个 xy 位置已经使用了，需要标记，后续不再使用
        board[x][y] = '.';
        // 枚举上下左右四个方向
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            // 判断是否在界内
            if (a >= 0 && a < n && b >= 0 && b < m) {
                // 如果走到下一个格子，可以匹配的话
                if (dfs(board, a, b, word, u + 1))
                	return true;
            }
        }
        // 恢复现场
        board[x][y] = word[u];
        // 否则，最后都没有匹配成功的话，就直接返回
        return false;
    }
};

46.Permutations

class Solution {
public:
    
    int n; // 输入大小
    vector<bool> st; // 当前这个分支里面可以用的数字是哪些
    vector<vector<int>> ans; // 答案
    vector<int> path; // 存当前方案
    
    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        st = vector<bool>(n);
        
        dfs(nums, 0);
        
        return ans;
    }
    
    void dfs(vector<int>& nums, int u) {
        if (u == n) {
            ans.push_back(path);
            return;
        }
        
        for (int i = 0; i < n; i ++ ) {
            if (!st[i]) {
                st[i] = true;
                path.push_back(nums[i]);
                dfs(nums, u + 1);

                st[i] = false;
                path.pop_back();
            }
        }
    }
};

47.Permutations II

class Solution {
public:
  	
    int n;
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;
    
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        st = vector<bool>(n);
        path = vector<int>(n);
        
        dfs(nums, 0, 0);
        
        return ans;
    }
    
    void dfs(vector<int>& nums, int u, int start) {
        if (u == n) {
            ans.push_back(path);
            return;
        }
        
        for (int i = start; i < n; i ++ ) {
            if (!st[i]) {
                st[i] = true;
                path[i] = nums[i];
                dfs(nums, u + 1, u + 1 < n && nums[u + 1] == nums[u] ? i + 1 : 0);
                
                st[i] = false;
                path[i] = 0;
            }
        }
    }
};

78.Subsets

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        // 左移表示 2^n
        for (int i = 0; i < 1 << nums.size(); i ++ ) {
            vector<int> now; // 当前的集合
            for (int j = 0; j < nums.size(); j ++ ) {
                // 如果 i 的第 j 位是 1 的话，就加入集合
                if (i >> j & 1) {
                    now.push_back(nums[j]);
                }
            }
            res.push_back(now);
        }
        
        return res;
    }
};

90.Subsets II

class Solution {
public:
    
    vector<vector<int>> ans;
    vector<int> path;
    
    vector<vector<int>> subsetsWithDup(vector<int> & nums) {
        // 为了把相同数字放在一起，先排序
        sort(nums.begin(), nums.end());
        
        dfs(nums, 0);
        
        return ans;
    }
    
    void dfs(vector<int>& nums, int u) {
        if (u == nums.size()) {
            ans.push_back(path);
            return;
        }
        
        // 计算当前数字的个数
        int k = 0;
        while (u + k < nums.size() && nums[u + k] == nums[u]) k ++ ;
        // 每次从 0 枚举到 k
        for (int i = 0; i <= k; i ++ ) {
            dfs(nums, u + k);
            path.push_back(nums[u]);
        }
        
        // 恢复现场
        for (int i = 0; i <= k; i ++ ) path.pop_back();
    }
};

216.Combination Sum III

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, 1, n);
        return ans;
    }
    
    void dfs(int k, int start, int n) {
        // 如果当前枚举完了所有数的话
        if (!k) {
            // 再判断当前的和是否是 n
            if (!n) return ans.push_back(path);
            return;
        }
        // 从 start 位置开始往后枚举 i <= 10 - k
        for (int i = start; i <= 9; i ++ ) {
            // 先把 i 加进来
            path.push_back(i);
            // 枚举下一个数，是倒着枚举，从 i + 1 位置开始找，总和就是 n - i
            dfs(k - 1, i + 1, n - i);
            // 恢复现场
            path.pop_back();
        }
    }
};

52.N-Queens II

class Solution {
public:
    
    int ans = 0, n;
    vector<bool> col, d, ud;
    
    int totalNQueens(int _n) {
        n = _n;
        col = vector<bool>(n);
        d = ud = vector<bool>(n * 2);
        // 从前往后枚举每一行
        dfs(0);
        
        return ans;
    }
    
    void dfs(int u) {
        if (u == n) {
            ans ++ ;
            return;
        }
        // 枚举每一列
        for (int i = 0; i < n; i ++ )
        	if (!col[i] && !d[u + i] && !ud[u - i + n]) {
                col[i] = d[u + i] = ud[u - i + n] = true;
                dfs(u + 1);
                col[i] = d[u + i] = ud[u - i + n] = false;
            }
    }
};