本文档总结了非ACMer应知应会基础算法cpp版本，不涉及算法详解，适合（保研机考/找实习）复习框架使用。

大部分资料来源与互联网各大佬的总结与整理，此处作为复习整合。此外非常感谢学长提供的算法模板手册！

施工建设中……

0 program basic

以下是c++语言基础部分参考复习

0.1 万能头

1	#include<bits/stdc++.h>

0.2 输入输出处理

cin/cout
getline(cin, str, '\n')：默认读入一行，可以更换截断字符
读取不定行数：while(getline(...))

0.2.1 输出保留小数位数

double a=46.21534,b=1.20001;
cout.setf(ios::fixed);    // 打开fixed功能，功能和下一行的fixed功能一样，同时写没关系
cout << fixed << setprecision(2) << b << endl;      //输出结果为1.20
cout.unsetf(ios::fixed); // 关闭fixed功能，如果不关闭会一直保持
cout << setprecision(2) << b << endl;   //不含fixed，保持小数点前的位数，输出1.2
cout << setprecision(5) << a << endl;    //46.215
cout << setprecision(1) << a << endl;  //5e+001

0.2.2 int string互转

【int->string】

to_string(int)

ostringstream：

1
2
3

ostringstream ss;
ss << num;
cout << ss.str();

【string->int】

istringstream
atoi(str)

0.2.3 string操作

string s;
s.insert(pos,args); // 在pos后插入
s.erase(pos,len); // 删除pos开始的len个字符，如果没有len删除至末尾

0.3 std::sort踩坑记录

在使用排序的过程中我们通常为了省时省力会选择使用c++库中提供的sort函数，重载compare来进行。众所周知sort底层原理是快速排序，但是实际上的情况不尽如此。

在使用sort排序一个大数组时，我碰到了如下问题：

AddressSanitizer: heap-buffer-overflow on address 0x7f6fbd3a47e8

网上查阅相关资料得知，原来是因为compare重载时，两个数出现==的情况也返回了true，这就导致出现循环相等的情况。因此，在大数组排序时，出现相等元素一定不能cmp函数返回true。

0.4 文件输入输出

#include <iostream>
#include <fstream>
#include <string>

int main() {
    std::string filename = "example.txt";
    std::ifstream file(filename);

    if (!file.is_open()) {
        std::cerr << "无法打开文件：" << filename << std::endl;
        return 1;
    }

    std::string line;
    while (std::getline(file, line)) {
        std::cout << line << std::endl;
    }

    file.close(); // 关闭文件
    return 0;
}

#include <iostream>
#include <fstream>
#include <string>

int main() {
    std::string filename = "example.txt";
    std::ofstream file(filename);

    if (!file.is_open()) {
        std::cerr << "无法打开文件：" << filename << std::endl;
        return 1;
    }

    std::string text = "Hello, World!";
    file << text << std::endl; // 写入字符串

    file.close(); // 关闭文件
    return 0;
}



#include <iostream>
#include <fstream>
#include <string>

int main() {
    std::string filename = "example.txt";
    std::fstream file(filename, std::ios::in | std::ios::out);

    if (!file.is_open()) {
        std::cerr << "无法打开文件：" << filename << std::endl;
        return 1;
    }

    // 写入字符串
    std::string text = "Hello, World!";
    file << text << std::endl;

    // 移动到文件开头
    file.seekg(0); // 设置文件读指针位置到文件开头

    // 读取字符串
    std::string readText;
    std::getline(file, readText);
    std::cout << readText << std::endl;

    file.close(); // 关闭文件
    return 0;
}

0.5 java

从以下部分开始是java的基础处理部分

0.5.1 输入输出

使用scanner可以方便处理命令行输入

Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
int t = sc.nextInt();
float f = sc.nextFloat();

while(sc.hasNextLine()){
    ...
}

使用System.out.print或者System.out.println可以输出，输出格式规则和c语言printf相同。

0.5.2 文件

File类相关的操作

File file = new File("path");
if(!file.exists()){
    file.createNewFile();
}

0.5.2.1 读取文件

// 使用Scanner
File file = new File("path");
Scanner in = new Scanner(file,"UTF-8"); // 防止出现中文乱码
// 然后就可以按照scanner的使用方式nextLine等方式使用
while(in.hasNextLine()){
    String line = in.nextLine();
}

// 使用bufferedReader
File file = new File("path");
FileReader fr = new FileReader(file);
BufferedReader bfReader = new BufferedReader(fr);
String line;
while((line = bfReader.readLine()) != null){
    ...
}

0.5.2.2 写入文件

// 使用PrintWriter
PrintWriter pw = new PrintWriter(file, "UTF-8");
// 以下三种方式都是直接覆盖原文件
pw.print(...);
pw.append(...);
pw.write(...);

// 使用FileWriter
FileWriter fw = new FileWriter("path");
BufferedWriter bw = new BufferedWriter(fw);
bw.write(...);
bw.close();
fw.close(); 
// 注意关闭顺序，一定要先关闭输出流再关闭文件，否则文件无法保存

以上方法都会重写原文件，即覆盖原文件

【追加写入】

File file = new File("path");
FileOutputStream fos = new FileOutputStream(file,true);
OutputStreamWriter osw = new OutputStreamWriter(fos,"UTF-8");
osw.write(...);

File file = new File("path");
FileWriter fw = new FileWriter(file,true); // 表示追加
BufferedWriter bw = new BufferedWriter(fw);
bw.write(...);

0.5.2.3 junit相关文件比较

0.5.3 string操作

0.5.3.1 string和int互转

string -> int：

1
2
3

String s;
int a = Integer.parseInt(s);
int b = Integer.valueOf(s);

int -> string：

1
2
3

int a;
String s1 = Integer.toString(a);
String s2 = String.valueOf(a);

0.5.3.2

0.5.3 常用数据结构

1 STL速查

1.1 常用STL操作

reverse(container.begin(), container.end())：反转
sort(container.begin(), container.end(), bool cmp)：排序
unique(container.begin(), container.end())：先把容器排序，然后去重，返回去重后的结尾迭代器，可以通过.erase()删除结尾部分
shuffle(container.begin(), container.end())：随机打乱元素（c++14 以前使用random_shuffle()）
lower_bound(a.begin(), a.end(), x)：找到第一个 >= x的数，返回迭代器（找不到返回尾迭代器）【区别于upper_bound，upper返回第一个 > x的数】可以用此迭代器减去a.begin()获取这个数的下标

1.2 vector

初始化

vector<int> a(n);
vector<int> b(n,0);
vector<int> c = {1,2,3};
vector<int> d(a); // 将a复制一份为d
vector<vector<int>> e(n,vector<int>(n));

push_back：在数组末尾插入，emplace_back更高效
pop_back：在数组末尾删除

1.3 map

映射，底层仍然是红黑树

map<int,int> mp；
mp[x] = 1; // 此种写法无论原来是否存在都会分配内存，使用find方法不会
mp.find(x); // 返回迭代器

for(auto [x,y] : mp){...} // c++17开始支持

如果要使用hash table，应该使用unordered_map，使用方式与map相同

1.4 set

底层是红黑树

insert：插入元素 $O(logn)$
lower_bound(x)：二分查找有序数列，返回大于等于x的最大值（迭代器iterator）
erase(x)：删除迭代器对应的元素，如果x是迭代器 $O(1)$ ，是元素则会先find后删除 $O(logn)$
find(x)：查找 $O(logn)$ ，返回迭代器
遍历：使用迭代器

multiset可以插入重复元素，使用erase时只删除一个元素，不会把重复的都删除

利用有序的set/map可以自动实现插入自动排序，即将元素放置到对应位置，辅助lower_bound进行二分查找

1.5 stack

push(x)：加入元素
pop()：删去栈顶，返回值为void
top()：返回栈顶元素

1.6 queue

push(x)
pop()
front()

1.6.1 deque

同时操作头尾，双端队列

push_back(x)：队尾插入
pop_back()：弹出队尾元素
push_front(x)：队首插入
pop_front()：弹出队首元素

1.6.2 priority_queue

通常作为堆使用

初始化

1 2	priority_queue<int> q; // 默认大根堆（最大堆） priority_queue<int, vector<int>, greater<int>> q; //使用vector作为底层容器，小根堆

top()：访问堆顶元素
push(x)
pop()

1.7 pair

使用first/second来访问元素

2 字符串

// 字符串基本操作
string s;
s += 'a';

if(s1 < s2) {...}

s.c_str(); // 将string转化为c风格字符串，返回头指针
char[] c_str_ptr;
s = c_str_ptr; // 直接将char[]转换成string

s.substr(pos,len); // 截取下标开始处的len长度字串，不写len默认取到结尾

stoi(s); // 将字符串表示的数字直接转换为int

【int与string互转】

int转string
c++11中的新特性to_string()

// c++11
string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);

string转int：使用istringstream

2.1 字符串哈希

基本思想：将字符串通过哈希函数转化为int值， $hash(s) = \Sigma_{i=0}^{n-1} s_i b^i$

注意点：b是大素数，计算出来的和（很大）需要取模

const int M = 1e9+7;
const int B = 233;

int get_hash(const string& s){
    int res = 0;
    for(int i = 0;i < s.size();i++){
        res = (i64)(res*B + s[i]) % M;
    }
    return res;
}

bool cmp(const string& s, const string& t){
    return get_hash(s) == get_hash(t);
}

代码来自oi-wiki，i64表示int64_t，即c++中的64位带符号整数（头文件写法：using i64 = int64_t;）

【例题】leetcode 187.Repeated DNA Sequences

2.2 Manacher算法

用于求解字符串中的最大回文串。“abcdsdc"在字符串中加入占位符和开始结束符号，”$#a#b#c#d#s#d#c#^"，然后遍历回文串可能的中心位置c，记录该中心位置对应的最大回文半径r

当中心从c移到i的时候，如果i < r，那么当前i的回文半径至少是r-i和关于c对称的位置回文半径r[2c-i]中的最小值，需要根据i周围情况做进一步调整。如果i > r，那就要从1开始扩展。

vector<int> manacher(string& s){
    //返回中心半径数组
    int n = s.size();
    //构造扩充后的字符串
    vector<char> expand(n+n+1+2);
    expand[0] = '$';
    expand[1] = '#';
    for(int i = 0;i < n;i++){
        expand[i+i+2] = s[i];
        expand[i+i+3] = '#';
    }
    expand[n+n+2] = '^';

    vector<int> p(n+n+1,0);//第一个位置空着不用，从1开始；最后一个位置也不用半径
    int r = 0, c = 0;
    for(int i = 2;i < n+n+1;i++){
        p[i] = (i < r)? min(r-i,p[c+c-i]):1;
        while(expand[i+p[i]] == expand[i-p[i]])++p[i];
        if(i+p[i] > r){
            c = i;
            r = i+p[i];
        }
    }
    return p;
}

计算最长回文子串时，需要注意半径中包含#占位符，计算长度和起始位置时需要一些转换。可以参考以下例题的实际代码。

【例题】leetcode 5.Longest Palindromic Substring

2.3 KMP算法

不重复匹配已经匹配过的相同前缀

void kmp(string a, string b, vector<int>& next){
    //在a中匹配b，n和m分别表示a和b的长度，next数组维护公共前缀
    int n = a.length(),m = b.length();
    for(int i = 0,j = -1;i < n;i++){
        while(j > 0 && (j == m || a[i] != b[j+1])) j = next[j];
        if(a[i] == b[j+1]) j++;
        if(j == m-1) // a[i-m+1:i]是b在a中第一次出现
    }
}

vector<int> getNext(string b){
    int m = b.length();
    vector<int> next(m+1);
    next[0] = -1;
    for(int i = 1, j = -1; i < m; i++){
        while(j > 0 && b[i] != b[j+1]) j = next[j]; // 如果下一位不同，往前回溯
        if(b[i] == b[j+1]) ++j; // 下一位相同，更新最大前缀
        next[i] = j; 
    }
    return next;
}

【例题】leetcode 28.Find the Index of the First Occurrence in a String

2.4 Trie

字典树

可以用链表传统树结构实现，也可以用数组的形式简易实现。

namespace Trie{
    int root = 1, nodeCnt = 1, ch[N][26]; // 根节点从1开始编号
    bool flag[N]; // flag表示第x个节点是否为一个字符串结尾
    void insert(char s[], int n){
        int cur = root;
        for(int i = 1;i <= n;i++){
            if(!ch[cur][s[i]-'a']) ch[cur][s[i]-'a'] = ++nodeCnt;
            cur = ch[cur][s[i]-'a'];
        }
        flag[cur] = true;
    }
    bool query(char s[], int n){
        int cur = root;
        for(int i = 1;i <= n;i++) cur = ch[cur][s[i]-'a'];
        return flag[cur];
    }
}

【例题】leetcode 208.Implement Trie Prefix Tree

3 常用结构

数据结构题单

3.1 栈

First in, Last out.

STL提供stack<T>，也可以用数组简单实现

经典例题：括号匹配问题 leetcode 20.Valid Parentheses

【*单调栈】栈中元素保持单调递增性或递减性，例题请查看单调栈题单

【例题】

3.2 队列

First in, First out.

STL提供queue<T>，详见1.6节

【经典应用】广度优先搜索BFS（见4.6.1节）

3.2.1 *单调队列

类似于单调栈，队列中元素保持单调性，通常用于滑动窗口问题。一般多用双端队列deque实现，但是deque常数较大，可以用数组替代。
通常用于滑动窗口问题。

【例题】leetcode 239.Sliding Window Maximum

3.2.2 优先队列/堆

优先队列使用堆实现，STL提供priority_queue（见1.6.2节）

使用数组实现堆（大根堆），元素从1开始

vector<int> heap;

int top(){return heap[1];} // 返回最值

void push(int k){ // 插入元素
    heap.push_back(k);
    swim(heap.size()-1);
}

void pop(){
    heap[0] = heap[heap.size()-1];
    heap.pop_back();
    sink(0);
}

void swim(int pos){ // 上浮，用于push情况
    while(pos > 1 && heap[pos/2] < heap[pos]){
        int tmp = heap[pos/2];
        heap[pos/2] = heap[pos];
        heap[pos] = tmp;
        pos = pos/2;
    }
}

void sink(int pos){ // 下沉，用于删除后情况
    while(2*pos < heap.size()){
        int i = 2*pos;
        if(i+1 < heap.size() && heap[i+1] > heap[i])++i;
        if(heap[i] > heap[pos]){
            int tmp = heap[pos];
            heap[pos] = heap[i];
            heap[i] = tmp;
            pos = i;
        }else{break;}
    }
}

经典应用：求第k大的元素

【例题】leetcode 218.The Skyline Problem

3.3 哈希表

STL提供unordered_set查找元素是否在集合中，用unordered_map存储键值对

【例题】leetcode 128.Longest Consecutive Sequence

一个很妙的原地hash技巧，即利用数组下标的性质，将数组中元素变为-或者插入一个数位，保留原来数据的性质的同时也能标记其他数据，节省空间
查看例题：leetcode 41.First Missing Positive

3.4 并查集

基本思想：标记每一个节点的父节点

基本操作：

查询根节点（get）
合并树（merge）

并查集有两种优化方式，路径压缩和按秩合并

3.4.1 路径压缩

基本思想：每次get(x)后将x的根节点设置为查询到的节点

namespace UFS{
    int ufs[N];
    void initialize(){for(int i = 0;i < n;i++) ufs[i] = i;}
    int get(int x){ return ufs[x] == x ? x : ufs[x] = get(ufs[x]);}
    void merge(int x,int y){
        int fx = get(x), fy = get(y);
        if(fx == fy) return;
        ufs[fx] = fy;
    }
}

3.4.2 按秩合并

按秩合并和路径压缩不能一起使用。

按树的节点数量合并
按树的深度（秩）合并

namespace UFS{
    int ufs[N],rank[N];
    void initialize(){
        for(int i = 0;i < n;i++){
            ufs[i] = i;
            rank[i] = 1;
        }
    }
    int get(int x){return ufs[x] == x ? x : get(ufs[x]);}
    void merge(int x,int y){
        int fx = get(x), fy = get(y);
        if(fx == fy) return;
        if(rank[fx] < rank[fy]) ufs[fx] = fy;
        else{
            ufs[fy] = fx;
            if(rank[fx] == rank[fy]) rank[fx]++; // 高度相同时合并树高要加1
        }
    }
}

【例题】

leetcode标签：并查集

3.5 链表

3.6 树

【遍历】

前序
中序
后序
层次

【完全二叉树】

只有叶子层可以有空节点，其他层必须拥有全部节点，且叶子层节点必须从左向右依次排列

【满二叉树】

所有节点如果不是叶子节点必须有两个子结点。

3.6.1 BST

3.6.2 B/B+ Tree

3.6.3 Balanced Tree

3.6.4 Red Black Tree

3.6.5 LCA

寻找lowest common ancester

3.6.5.1 递归

查看左右子树是否包含该节点

TreeNode* lca(TreeNode* root,TreeNode* l,TreeNode* r){
    if(!root || root == p || root == q)return root;
    TreeNode* left = lca(root->left,p,q);
    TreeNode* right = lca(root->right,p,q);
    if(!left)return right;
    if(!right) return left;
    return root;
}

3.6.5.2 倍增

3.6.6 最长路径/树的直径

3.6.6.1 两次BFS

从任意节点p出发，利用广度优先/深度优先找到最长路径x的终点i
从i出发，找到最长路径y
y即树的最长路径

任意节点出发寻找的最长路径终点一定是叶子节点，从叶子节点出发寻找的最长路径即为整棵树的最长路径

3.6.6.2 树上DP

设 $f(x)$ 表示到x点最长的叶子节点的距离，那么 $f(x) = dist(x,y)+f(y)$ ， $y$ 是 $x$ 的子节点。

如果 $y_1,y_2$ 是 $x$ 的两个不一样的子节点（ $y_1$ 和 $y_2$ 不在 $x$ 同一条子节点路上），那么可以把树的直径用 $dist(x,y_1)+f(y_1)+dist(x,y_2)+f(y_2)$ 更新一下。通过dp可以遍历节点，相当于每次考虑经过一个节点最长路径。

int f[N],ans = 0;
void dp(int x,int fa){
    for(int j = head[x];j;j = e[j].nxt){
        int y = e[j].to;
        dp(y,x);
        ans = max(ans,f[x]+e[j].val+f[y]);
        f[x] = max(f[x],e[j].val+f[y]);
    }
}

3.7 *树状数组

3.7.1 一维

用来解决“单点修改，单点查询”，“单点修改，区间查询”，“区间查询，区间修改”这些问题，这篇博客详细解释了树状数组的求和原理

lowbit：数字最低为1位表示的数字大小（例如，lowbit(1) = 1，lowbit(5) = 1，lowbit(6) = 2

树状数组中存储的元素，表示区间[i-lowbit[i]+1,i]的区间查询元素

单点修改，区间查询模板

namespace Bit{
    int s[N];
    int lowbit(int i){ return i & (-i);}
    void modify(int p,int v){
        //下标为p的元素+v(单点修改)
        for(;p <= n;p += lowbit(p)) s[p] += v;
    }
    int query(int p){
        // 区间[0,p]的和
        int ret = 0;
        for(;p > 0;p -= lowbit(p)) ret += s[p];
        return ret;
    }
    int query(int l, int r){
        //查询区间[l,r]
        return query(r)-query(l-1);
    }
}

树状数组修改和查询的时间复杂度均为 $O(logn)$

如何构建树状数组？
使用前缀和之类的手段

【例题】

3.7.2 二维

3.8 *线段树

线段树适合用来解决“区间修改、区间查询”的问题。

将每一段区间按照叶节点记录子区间，父节点记录将子区间合并成一个大区间。修改区间时，针对该节点以下子节点的更新，使用lazy tag标记，访问时将tag下推。

区间修改代码（区间和）

namespace SegTree{
    int s[N << 2], t[N << 2]; //s数组用于存储线段树区间和，t数组用于记录tag
    #define lc (p << 1) // left child at position [2*p]
    #define rc (p << 1 | 1) // right child at position [2*p+1]
    #define mid ((l+r) >> 1) // 用于建树

    inline void up(int p){s[p] = s[lc]+s[rc];} // 向上更新
    inline void down(int p, int l, int r){
        // 使用tag向下更新
        if(!tag[p]) return;
        s[lc] += tag[p]*(mid-l+1);tag[lc] += tag[p];
        s[rc] += tag[p]*(r-mid);  tag[rc] += tag[p];
        tag[p] = 0;
    }

    // 使用递归技巧建树
    void build(int p, int l, int r){
        if(l == r){
            s[p] = a[l];
            return;
        }
        build(lc,l,mid);
        build(rc,mid+1,r);
        up(p);
    }

    //修改某个区间:[x,y]区域内的值+v
    void modify(int p, int l, int r,int x,int y,int v){
        if(x <= l && y >= r){ // 递归结束，找到包括的全部区间
            s[p] += (r-l+1)*v;
            tag[p] += v;
            return;
        }
        down(p,l,r);
        if(x <= mid) modify(lc,l,mid,x,y,v);
        if(y > mid) modify(rc,mid+1,r,x,y,v);
        up(p);
    }

    //查询某个区间内的值
    int query(int p,int l,int r,int x,int y){
        if(x <= l && y >= r){
            return s[p];
        }
        down(p,l,r);
        int ret = 0;
        if(x <= mid) ret += query(lc,l,mid,x,y);
        if(y > mid) ret += query(rc,mid+1,r,x,y);
        return ret; 
    }
}

单点修改

void modify(int p,int l,int r,int x,int v){
    if(l == r){
        s[p] += v;
        return;
    }
    down(p,l,r);
    if(x <= mid) modify(lc,l,mid,x,v);
    else modify(rc,mid+1,r,x,v);
    up(p);
}

单点查询

int query(int p,int l,int r,int x){
    if(l == r){
        return s[p];
    }
    down(p,l,r);
    if(x <= mid) return query(lc,l,mid,x);
    return query(rc,mid+1,r,x);
}

线段树的时间复杂度为 $O(nlogn)$

如何修改模板以适应不同的问题

区间复合如何实现，即如何实现up函数
区间更新操作如何实现，即如何实现down和modify函数

3.9 ST表

这篇博客详细解释了ST表的原理。简单解释就是利用了区间可加性的思想，即区间[l,r]的性质可以由[l,s]和[s+1,r]两个区间的相同性质合并而来。例如：max(l,r) = max(max(l,s),max(s+1,r))

在ST表中，我们考察区间 $[i,i+2^j-1]$ 这个区间，可以发现这个区间可以由 $[i,i+2^{j-1}-1]$ 和 $[i+2^{j-1},i+2^j-1]$ 这两个区间，其中，每个子区间包含了 $2^{j-1}$ 个元素，总共区间有 $2^j$ 个元素

查询时，区间中有r-l+1个元素，因此取 $s = \lfloor log_2(r-l+1) \rfloor$ ，此时区间 $[l,l+2^s-1]$ 和 $[r-2^s+1,r]$ 可以交叉覆盖整个查询区间。

以下模板以求解区间最大值为例：

int st[N][M]; // 数组一共有N个元素，M = log2(N)，可以根据题目范围适当开大一点
int log2_[N]; // 预处理好求解log数组，c++log2库函数常数大

//建表
void build(){
    for(int i = 1;i <= n;i++) { // 数组从下标为1开始
        st[i][0] = a[i]; 
        log2_[i] = log2(i);
    }

    for(int j = 1;(1 << j) <= n;j++){
        for(int i = 1; i+(1 << j)-1 <= n;i++){
            st[i][j] = max(st[i][j-1],st[i+(1 << (j-1))][j-1]);
        }
    }
}

// 查询区间
int query(int l,int r){
    int s = log2_[r-l+1];
    return max(st[l][s],st[r-(1 << s)+1][s])
}

区间问题的总结请查看4.8节前缀和与差分数组

3.10 分块

将数组分成几个区间，使用tag标记区间统一操作情况，不在区间中的零散数据直接暴力处理。

可以将区间内的数据进行排序以获得更高的性能。

一般来说还是优先考虑线段树等log数据结构

4 技巧

4.1 动态规划

原理：保存子问题的解避免重复计算

核心：找到状态转移方程

动态规划题单

4.1.1 一维动态规划

爬楼梯问题：多种传递方式叠加
打家劫舍问题：有限制的叠加方式
不考虑顺序，即组合类问题：通过枚举可能的选项，固定顺序求解，具体例题请查看coin change II

4.1.2 二维动态规划

4.1.3 分割类型

4.1.4 子序列与字符串

连续子序列：选定结尾枚举（有些题目可以考虑前缀和方法）
非连续型子序列：
- 【经典问题】最长公共子序列（见题单线性dp专题）
- 【经典问题】最长递增子序列

【最长公共子序列的并行计算问题】

所有的并行计算问题都可以使用拓扑排序的思想解决

4.1.5 背包问题

0-1背包：每个物体只能选1次或0次，通过限制体积（或其他等价限制）来遍历
完全背包

4.1.6 状态机

4.1.7 树形dp

4.1.8 区间dp

4.1.9 状态压缩dp

4.2 贪心

4.2.1 区间问题

4.3 多指针与滑动窗口

4.3.1 双指针

4.3.2 滑动窗口

4.4 二分法

二分题单

二分查找模板：

找到大于等于/大于/小于等于/小于：

4.5 排序

4.5.1 归并排序

divide & conquer

void helper(vector<int>& nums,int l,int r,vector<int>& temp){
    if(l+1 >= r)return;
    //divide
    int m = l+(r-l)/2;
    helper(nums,l,m,temp);
    helper(nums,m,r,temp);
    //conquer
    int p = l,q = m,i = l;
    while(p < m || q < r){
        if(q >=r || (p < m && nums[p] <= nums[q])){
            temp[i++] = nums[p++];
        }else{
            temp[i++] = nums[q++];
        }
    }
    for(i = l;i < r;i++){
        nums[i] = temp[i];
    }
}

void mergesort(vector<int>& nums){
    vector<int> temp(nums.size());
    helper(nums,0,nums.size(),temp);
}

【例题】很精妙的运用LCR170. 交易的逆序对总数

4.5.2 快速排序

4.6 搜索

4.6.1 广度优先BFS

使用队列来存储每一层可以到达的节点

树BFS：层次遍历
图BFS

BFS可以较为容易的实现计算深度（层数/路径长度），但是难以记录路径

【例题】leetcode 934.Shortest Bridge

【专题】如何在BFS中找到最短路径（记录路径）

访问题目leetcode 126.Word Ladder II

4.6.2 深度优先DFS

使用栈结构，不要忘记访问过的标记避免重复访问

【例题】

leetcode 547.Friend Circles

4.6.3 其他搜索

【例题】变形搜索leetcode 240.Search a 2D Matrix II

网格搜索专题题单

图上BFS/DFS搜索相关题单请查看图论部分总题单

4.7 位运算

位运算题单

【常见技巧】

n&(n-1)：消去n最低位的1
n&(-n)：获取最低位的1的大小
reverse(lowbit(reverse(x)))：获取最高位1，reverse是把进制位头尾颠倒

【解题思想】

and参与运算的数越多，得到的结果越小；or参与运算的数越多，得到的结果越大
and/or运算可以把参与运算的整数拆分为二进制32位，按照每一位考虑

4.8 前缀和与差分数组

前缀是一个能解决很多问题的思想。

4.8.1 前缀和

对于任意一个数组 $a_0,a_1,...,a_n$

构造前缀和数组 $b_i = b_{i-1}+a_{i-1}, b_0 = 0$ ，求解区间 $[l,r]$ 的和可以用 $O(1)$ 复杂度求出

4.8.2 差分数组

构造差分数组 $d_i = a_i-a_{i-1}, d_0 = 0$ ，对区间 $[l,r]$ 做相同操作时（如同时加上 $v, d_l += v, d_{r+1} -= v$ ）可以以 $O(1)$ 复杂度实现。

【例题】leetcode 560.Subarray Sum Equals K

4.8.3 区间求值问题总结

摘自leetcode用户宫水三叶的总结

数组不变，求区间和：「前缀和」、「树状数组」、「线段树」
多次修改某个数，求区间和：「树状数组」、「线段树」
多次整体修改某个区间，求区间和：「线段树」、「树状数组」（看修改区间的数据范围）
多次将某个区间变成同一个数，求区间和：「线段树」、「树状数组」（看修改区间的数据范围）

总而言之，「线段树」的扩展性最佳，树状数组通常可以简化线段树。

4.8.4 前后缀分解

摘自leetcode用户灵茶山艾府的总结

两个非重叠子数组的最大和 1680
三个无重叠子数组的最大和
找到所有好下标 1695
适合野炊的日子 1702
使字符串平衡的最少删除次数 1794
将字符串翻转到单调递增
找两个和为目标值且不重叠的子数组 1851
得到山形数组的最少删除次数 1913
除自身以外数组的乘积 ~2000
使二进制字符串字符交替的最少反转次数 2006
构造乘积矩阵 2075
移除所有载有违禁货物车厢所需的最少时间 2219
统计回文子序列数目 2223
删除元素后和的最小差值 2225
最少得分子序列 2432
统计上升四元组 2433
执行操作后的最大分割数量 3039
最大连续 1 的个数 II（会员题）
经过一次操作后的最大子数组和（会员题）

4.9 回溯

4.10 曼哈顿距离

将坐标系顺时针旋转45°并拉伸为 $\sqrt{2}$ 倍，可以将两点之间的曼哈顿距离转换为在x’轴或者y’轴上的投影（即相对距离）。

坐标转换：(x,y) -> (x+y,x-y)

5 图论

图论系列题单

5.1 图的基本表示方法

5.1.1 邻接矩阵

邻接矩阵适用于点比较少的情况，用一个二维数组存储相互连接的点之间的权值(d[i][j] = v)

5.1.2 链式前向星

采用与每个点相连的边链表形式存储。

int tot, head[N]; // tot表示当前边的下标（总数），head记录从这个点出发的所有边链表的头节点
struct Edge{ int to, nxt, val;} e[M]; //每条边节点记录到的点，链表中下一项，以及边的权值
void addEdge(int to, int from, int val){
    e[++tot].to = to;
    e[tot].val = val;
    e[tot].nxt = head[from];
    head[from] = tot;
}

void visitEdge(int n){
    //访问从n出发的所有边
    for(int i = head[n];i;i = e[i].nxt){

    }
}

5.2 图遍历

DFS
BFS
拓扑排序

5.3 最短路

5.2.1 floyd

时间复杂度 $O(n^3)$

floyd的思想是动态规划，可以视作经过k的i到j最短路径和不经过k的最短路径。

int f[N][N],d[N][N]; // f存储最短路径，d存储邻接矩阵
void floyd(){
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            f[i][j] = d[i][j]; // 初始化
        }
        f[i][i] = 0; // 点到自己的距离是0
    }
    for(int k = 1;k <= n;k++){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                f[i][j] = min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }
}

如果i到j不存在路径，可以取无穷，为了防止溢出，可以设d[i][j] = 0x3f3f3f3f

向图中新加一条通路，则需要更新经过此条通路和不经过这条通路的最小路径

for(int i = 1;i <= n;i++){
    for(int j = 1;j <= n;j++){
        f[i][j] = min(f[i][j],f[i][x]+d[x][y]+f[y][j]);
    }
}

5.2.2 dijkstra

基本思想：S={u}，每次计算到S集合距离最近的点加入集合。（贪心）

5.2.2.1 朴素实现

时间复杂度 $O(n^2)$

int d[N];
bool vis[N];
void dijkstra(int u){
    for(int i = 1;i <= n;i++) d[i] = inf;
    d[u] = 0; // 开始时集合中只有u这一个点
    for(int i = 1;i <= n;i++){ // 最多扩展n次（共有n个点）
        int v = 0;
        for(int j = 1;j <= n;j++){
            if(vis[j])continue;
            if(v == 0 || d[v] > d[j]) v = j;
        }
        vis[v] = true;
        for(int j = head[v];j;j = e[j].nxt){
            int w = e[j].to;
            d[w] = min(d[w],d[v]+e[j].val); // 更新到当前w点的最小路径
        }
    }

}

5.2.2.2 堆优化

算法瓶颈在于求最小值

经过堆优化后的时间复杂度为 $O(mlogm)$ ，m表示边的数量

using pii = pair<int,int>;
int d[N];bool vis[N];
void dijkstra(int u){
    for(int i = 1;i <= n;i++)d[i] = inf;
    d[u] = 0;
    priority_queue<pii> pq;
    pq.push(pii(d[u],u));
    while(!pq.empty()){
        int w = pq.top().second;pq.pop();
        if(!vis[w]){
            vis[w] = true;
            for(int j = head[w];j;j = e[j].nxt){
                int i = e[j].to;
                if(d[i] > d[w]+e[j].val){
                    d[i] = d[w]+e[j].val;
                    pq.push(pii(-d[i],i)); // 优先队列默认大根堆，通过取反间接实现小根堆
                }
            }
        }
    }
}

5.2.3 Bellman-Ford

用于处理负权边，实现原理：用以下不等式更新dis

$dis(y) <= dis(x)+w$

经过n轮迭代，可以保证就是最短路。如果n轮迭代后上述等式不成立（即还可以更新），表明图中存在负环。

该算法时间复杂度为 $O(nm)$ ，n为点的数目，m为边的数目。这一时间复杂度是稳定的。

5.2.3.1 朴素实现

int d[N];
for(int i = 1;i <= n;i++){
    d[i] = inf;
}
void bellmanFord(int u){
    d[u] = 0;
    for(int r = 1;r <= n;r++){ // 最多n轮
        for(int x = 1;x <= n;x++){ // 遍历当前与源相连的所有节点
            if(d[i] == inf)continue;
            for(int j = head[x];j;j = e[j].nxt){
                int to = e[j].to,val = e[j].val;
                d[to] = min(d[to],d[x]+val);
            }
        }
    }
}

5.2.3.2 spfa

队列优化的BellmanFord算法：类似bfs的思想，只有x更新，与x相连的点才会发生更新，因此使用队列存储被更新过的节点，然后更新相连的节点。

int d[N];
for(int i = 1;i <= n;i++){
    d[i] = inf;
}
void spfa(int u){
    bool visited[N]; // 是否在队列中
    queue<int> q;
    q.push(u);
    visited[u] = true;
    while(!q.empty()){
        int t = q.front();q.pop();visited[t] = false;
        for(int j = head[t];j;j = e[j].nxt){
            int to = e[j].to,val = e[j].val;
            if(d[to] > d[t]+val){
                d[to] = d[t]+val;
                if(!visited[to]){
                    q.push(to); 
                    visited[to] = true;
                }
            }
        }
    }
}

5.4 最小生成树

minimum spanning tree - MST

5.4.1 Kruskal算法

基于贪心的思想，每次向kruskcal加入没有联通的最小权值的边。时间复杂度为 $O(mlogm)$ ，主要瓶颈在于给边排序的时间复杂度。

使用并查集记录连通块。

struct Edge{int x,y,v;};
bool cmp(Edge& e1,Edge& e2){
    return e1.v < e2.v;
}
int kruscal(vector<Edge> edges){
    sort(edges.begin(),edges.end(),cmp);
    int cnt = 0, sum = 0;
    for(Edge e:edges){
        if(get(e.x) != get(e.y)){ // x，y不在同一个连通块内
            cnt++;
            merge(e.x,e.y);
            sum += e.v;
        }
        if(cnt >= n)break;
    }
    return sum;
}

5.4.2 Prim算法

类似dijkstra算法，每次将到当前连通块中边最小的点加入联通集合。

算法复杂度为 $O(n^2)$ ，瓶颈主要在找最小值的过程。

bool vis[N]; // 用于记录当前点是否加入生成树
int dis[N]; // 类似dijkstra，记录未加入点到连通块的最小距离
// 使用链式前向星记录边

int prim(){
    for(int i = 1;i <= n;i++){
        vis[i] = false;
        dis[i] = inf;
    }
    dis[1] = 0; // 把点1先加入连通块
    int sum = 0;
    for(int i = 1;i <= n;i++){
        int x = 0;
        for(int j = 1;j <= n;j++){
            if(!vis[j] && dis[j] < dis[x])x = j; // 找到最小边点
        }
        vis[x] = true;
        sum += dis[x];
        for(int j = head[x];j;j = e[j].nxt){
            int y = e[j].to,val = e[j].v;
            if(!vis[y]){
                dis[y] = min(dis[y],val);
            }
        }
    }
    return sum;
}

5.5 二分图

5.6 网络流

6 数学

6.1 带余除法

6.1.1 最大公约数

辗转相除法（欧几里得法）求解最大公约数， $gcd(a,b) = gcd(a, b\space mod\space a)$

时间复杂度： $O(logn)$ 【证明：考虑 $a>\frac{b}{2}$ 和 $a<\frac{b}{2}$ 两种情况，可以证明每次整除会导致规模缩小一半】

实现与使用：

c++14：__gcd(int,int) （在<algorithm>库中）
c++17：gcd(int,int) （在<numeric>库中）

【例题】leetcode 1447.Simplified Fractions

6.1.2 不定方程

【定义】未知数个数超过方程数量，典型例子 $ax+by=c$ ， $x,y$ 为未知数， $a,b,c$ 为参数

【裴蜀定理】 $ax+by=c \iff gcd(a,b)|c$

简单证明：假设$a>b, a=b\cdot k+r $ ，那么 $ax+by=c$ 可以写作 $b(y+kx)+rx = bx_0+ry_0 = c$

在上述式子中， $r$ 可以写作 $a\space mod \space b$ ， $k$ 可以写作 $\lfloor\frac{a}{b}\rfloor$ （此处可利用c++中整数相除特性），因此扩展欧几里得算法可以写成：

int extgcd(int a,int b,int& x,int& y){ //此处默认c=gcd(a,b)
    if(!b){ // b=0, ax=c, a = gcd(a,b)
        x = 1;
        y = 0;
        return a;
    }
    int d = extgcd(b,a%b,x,y),x0 = x,y0 = y; // a = a/b * b + r  
    x = y0; // r*x+b*(a/b*x + y) = c, x->y0
    y = x0-(a/b)*y0; 
    return d;
}

【例题】leetcode 365.Water And Jug Problem

6.2 *素数/质数

6.2.1 质因数分解

任何数都可以被写成唯一的质因数分解形式 $\prod_{i=1}^k p_i^{r_i}$ ，其中 $p_i$ 是质数。

推理可知，如果要对一个整数进行质因数分解，只需要枚举 $[1,\sqrt{n}]$ 之间的素数（n最多只有一个大于 $\sqrt{n}$ 的质因数），时间复杂度为 $O(\sqrt{n})$

using pii = pair<int,int>;

vector<pii> getPrimes(int n){
    int tmp = n;
    vector<pii> ret;
    for(int i = 2;i*i <= n;i++){
        if(tmp % i == 0){
            int count = 0;
            for( ;tmp%i==0;tmp /= i)count++;
            ret.push_back(pii(i,count));
        }
    }
    // 如果存在大于根号n的质因数
    if(tmp != 1){
        ret.push_back(pii(tmp,1));
    }
    return ret;
}

6.2.2 素数筛

埃氏筛：枚举过程中将质数的倍数标记置为合数

int countPrimes(int n){
    int cnt = 0;
    vector<bool> isPrime(n+1,true);
    for(int i = 2;i <= n;i++){
        if(isPrime[i]){
            cnt++;
            for(int j = i+i;j <= n;j+=i){
                isPrime[j] = false;
            }
        }
    }
    return cnt;
}

埃氏筛的时间复杂度为

O(nloglogn)

？

欧拉筛：每个数被严格筛选一次，所以时间复杂度是

O(n)

int primeCnt = 0,primes[N];
bool notPrime[N];
void sieve(int maxN){
    for(int i = 2;i <= maxN;i++){
        if(!notPrime[i]) primes[++primeCnt] = i;
        for(int j = 1; j <= primeCnt && i*primes[j] <= maxN;j++){
            notPrime[i*primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

使用合数与该合数的最小质因数构造新的合数，假设a是一个合数，a = p * b，b是合数。假设存在 a = p’ * c，c是另一个合数，不妨设c > b（按照遍历次序），p’ < p，p’和p互质，因此p’|b，即 b%p’== 0，退出循环，不可能再出现p。详细证明请参考这篇博客

【例题】leetcode 204.Count Primes

素数筛的进阶用法：筛选积性函数

6.2.3 判断质数

【法一】从2到 $\sqrt{n}$ 遍历，查看是否能被整除

【法二】使用素数筛预处理范围内所有的素数

6.3 乘法逆元

乘法逆元： $ax \equiv 1 \pmod P$ ，x是模P意义下a的乘法逆元，等价于求解 $ax + Py = 1$ ，转换为不定方程使用扩展欧几里得算法求解。因此有解要求 $gcd(a,P) = 1$

6.3.1 费马小定理

费马小定理： $P$ 为质数， $a^P \equiv a \pmod P$

由费马小定理可以推出模P意义下a的乘法逆元特解是 $a^{P-2}$

6.3.2 线性递推

线性递推关系可以求解[1,n]每个整数对于P的逆元

$inv(1) = 1 \\ inv(n) = -\lfloor \frac{P}{n}\rfloor \cdot inv(P\bmod n) ,\space n \ge 2$

【总结】求解乘法逆元的方法

扩展欧几里得算法
费马小定理+快速幂直接求解
线性递推

这一部分的参考代码可以看这篇博客

6.3.3 快速幂

计算 $a^n$ ，传统做法是依次乘，时间复杂度为 $O(n)$ 。根据二分法的思想，可以计算 $a^2 \cdot a^2$ 将时间复杂度化为 $O(logn)$

递归写法：注意乘方会导致int类型数据溢出，因此使用long long类型并取模

typedef long long ll;
ll qpow(ll a, ll n){
    if(n == 0) return 1;
    if(n % 2 == 1) return (qpow(a, n-1) * a) % MOD;
    ll tmp = qpow(a,n / 2);
    return (tmp*tmp) % MOD;
}

循环写法：节省栈开销。 $a^{1001}$ 可以写成 $a^{1000}\cdot a^{1}$ . 通过把指数转化为二进制进行计算。

typedef long long ll;
ll qpow(ll a, ll n){
    ll ans = 1;
    while(n){
        if(n & 1){
            ans *= a;
        }
        a *= a;
        n >>= 1;
    }
    return ans;
}

6.4 矩阵计算

6.4.1 高斯消元

求解 $Ax=b, A\in R^{n\times m}, x\in R^{m\times 1}, b\in R^{n\times 1}$

基本思想：构造矩阵[A,b]

从上往下消元 -> 形成三角矩阵
从下往上消元 -> 形成对角矩阵

const double eps = 1e-7;// 精度值
bool Gauss(){
    for(int i = 1;i <= n;i++){ // 矩阵从数组的第一行第一列开始
        int r = i;
        for(int j = i+1;j <= n;j++){
            if(fabs(a[j][i]) > fabs(a[r][i])) r = j; // fabs用于计算浮点数的绝对值，找到该列绝对值最大的行，减少浮点计算误差
        }
        if(fabs(a[r][i]) < eps)return false; // 不存在唯一解
        if(r != i){
            for(int j = i;j < n+1;j++){
                swap(a[r][j],a[i][j]); // 交换绝对值最大的值所在行
            }
        }
        for(int j = i+1;j <= n;j++){
            double tmp = a[j][i] / a[i][i];
            for(int k = i;k <= n+1;k++)a[j][k] -= tmp * a[i][k];
        }
    }
    for(int i = n;i >= 1;i--){
        for(int j = i+1; j <= n;j++)a[i][n+1] -= a[j][n+1]*a[i][j];
        a[i][n+1] /= a[i][i];
    }
    return true;
}

6.4.2 矩阵乘法

可以用于处理一些递推关系，比如斐波那契数列 $F_n = F_{n-1}+F_{n-2}$

$\begin{bmatrix} F_{n-1} & F_n \end{bmatrix} \times \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} F_n & F_{n+1} \end{bmatrix}$

【矩阵求幂】快速幂优化。下述模板只是矩阵乘法的实现

class Matrix{
    int n,m;
    i64 v[n][m];
    Matrix(){memset(v,0,sizeof(v));}
    friend Matrix operator *(const Matrix& x, const Matrix& y){
        Matrix ret;
        ret.n = x.n;ret.m = y.m;
        for(int i = 0;i < ret.n;i++){
            for(int j = 0;j < ret.m;j++){
                for(int k = 0;k < x.m;x++){
                    ret.v[i][j] += x.v[i][k]*y.v[k][j];
                }
            }
        }
        return ret;
    }
}

6.5 组合数

求解组合数可以通过递归和阶乘两种方式求解

6.5.1 杨辉三角

杨辉三角揭示了组合数的递归规律， $C_i^j = C_{i-1}^j+C_{i-1}^{j-1}$ 。同时对于任意 $i \ge 1, C_i^0 = 1$

void getBinom(int n){
    c[0][0] = 1;
    for(int i = 1;i <= n;i++){
        c[i][0] = 1;
        c[i][i] = 1;
        for(int j = 1;j < i;j++){
            c[i][j] = c[i-1][j-1]+c[i-1][j];
        }
    }
}

该方法的复杂度为 $O(n^2)$

6.5.2 组合阶乘

原理： $C_i^j = \frac{i!}{j!(i-j)!}$ ，计算阶乘复杂度 $O(n)$ ，可以直接使用除法，也可以使用前面所说的乘法逆元（当对大数取模且P是质数时）

int fac[N], ifac[N]; // fac记录阶乘，ifac记录阶乘对应模P逆元
fac[0] = 1;
void getFac(int maxn){
    for(int i = 1;i <= maxn;i++){
        fac[i] = 1LL*fac[i-1]*i % P;
    }
    ifac[maxn] = fpow(fac[maxn],P-2); // 使用费马小定理和快速幂求解逆元
    for(int i = maxn-1;i >= 1;i--) ifac[i] = 1LL*ifac[i+1]*(i+1) % P;
}

int binom(int i, int j){
    if(i < j || i < 0 || j < 0) return 0;
    return fac[i]*(ifac[j] % P )*(ifac[i-j] % P)*1LL % P;
}

6.6 随机

带有权重的随机leetcode 528.Random Pick with Weight
用某个范围随机数生成另一些随机数leetcode 470.Implement Rand10 Using Rand7
使用随机数计算 $\pi$ ：利用面积公式，计算随机点落入圆的概率

6.6.1 java随机数

Random rand = new Random();
int t = rand.nextInt(100)+1; //生成1-100（包括）的整数

int num = (int)(Math.random()*100)+1;

Math.random()随机生成[0.0,1.0)之间的double类型数据

6.6.2 c++随机数

1	int t = rand() % num;

6.7 求解平方根

6.7.1 二分法

初始化为x/2，然后不断除2逼近

6.7.2 牛顿迭代法

设置一个近似值x（可以是n/2），然后不断用 $\frac{x+ \frac{a}{x}}{2}$ 迭代逼近

画图可以得到以下递推关系：

$f'(\theta_t) = \frac{f(\theta_t)-n}{\theta_t - \theta_{t+1}}$

6.8 回文数字

从小到大依次生成回文数字，基本思想：固定回文根，如12，那么可以生成奇数位和偶数位两种回文数，121和1221.

算法过程：枚举范围内所有回文根（按照位数枚举）

// n表示最大范围数位
for(int base = 1;base < n;base *= 10){
    // 生成奇数位回文数
    for(int i = base;i < base*10;i++){
        int x = i;
        for(int j = i/10;j;j /= 10){
            x = x*10+j % 10;
        }
        //存储或操作生成的x
    }
    if(base <= n/2){ // 不超过最大范围
        for(int i = base;i < base*10;i++){
            int x = i;
            for(int j = i;j;j /= 10){
                x = x*10+j % 10;
            }
            //存储或操作生成的x
        }
    }
}