Cpp算法笔记

万能头文件

#include <bits/stdc++.h>

---

排序

外部函数

bool cmp(T a, T b){
    return //sort rule;
}

void main(){
    sort(nums.begin(), nums.end(), cmp);
}

Lambda表达式

sort(nums.begin(),nums.end(),[](T &a, T &b){
    return //sort rule;
});

快速排序模板

int Partition(int A[], int left, int right){
    int tmp = A[left];
    while(left<right){
        while(left<right&&A[right]>tmp) right--;
        A[left] = A[right];
        while(left<right&&A[left]<=tmp) left++;
        A[right] = A[left];
    }
    A[left] = tmp;
    return left;
}

void quickSort(int A[], int left, int right){
    if(left<right){
        int pos = Partition(A, left, right);
        quickSort(A, left, pos-1);
        quickSort(A, pos+1, right);
    }
}

//choose random principal point
int randPartition(int A[], int left, int right){
    int p = round(1.0*rand()/RAND_MAX*(right-left)+left);//生成[left,right]内的随机数；
    swap(A[p],A[left]);
    //same as Partition
    int tmp = A[left];
    while(left<right){
        while(left<right&&A[right]>tmp) right--;
        A[left] = A[right];
        while(left<right&&A[left]<=tmp) left++;
        A[right] = A[left];
    }
    A[left] = tmp;
    return left;

}

---

二分查找

查看元素是否存在

//template
int binarySearch(int A[], int left, int right, int target){
    while(left<=right){
        int mid = left + (right-left)/2;
        if(A[mid]==target) return mid;
        else if(A[mid]>x){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return -1;
}
//STL
binary_search(nums.begin(), nums.end(), target);

求序列中第一个大于等于target的元素的位置

//template
int lower_bound(int A[], int left, int right, int target){
    while(left<right){
        int mid = left + (right-left)/2;
        if(A[mid]>=x){
            right = mid;
        }else{
            left = mid + 1;
        }
    }
    return left;
}

//STL
lower_bound(nums.begin(), nums.end(), target, [](const T target, const T &a){
    return //rule;
});

求序列中第一个大于target的元素的位置

//template
int upper_bound(int A[], int left, int right, int target){
    while(left<right){
        int mid = left + (right-left)/2;
        if(A[mid]>x){
            right = mid;
        }else{
            left = mid + 1;
        }
    }
    return left;
}

//STL
upper_bound(nums.begin(), nums.end(), target, [](const T target, const T &a){
    return //rule;
});

---

数学

快速幂

求解a^b%m

递归写法

typedef long long LL;
LL binaryPow(LL a, LL b, LL m){
    if(b==0) return 1;
    if(b&1){
        return a*binaryPow(a, b-1, m)%m;//if b is an odd num, convert to b-1
    }else{
        LL mul = binaryPow(a, b/2, m);//if b is an even num, convert to b/2
        return mul*mul%m;
    }
}

迭代写法

typedef long long LL;
LL binaryPow(LL a, LL b, LL m){
    LL ans = 1;
    while(b>0){
        if(b&1){
            ans = ans*a%m;
        }
        a = a*a%m;
        b >>= 1;
    }
    return ans;
}

---

素数筛

#define maxn 1000000
bool vis[maxn];
int prime[maxn], primeNums;

埃氏筛

void aiShiShai(int n){
    for(int i = 2; i<=n; i++){
        if(!vis[i]) prime[primeNums++] = i;
        for(int j = 2; j*i<=n; j++){
            vis[i*j] = true;
        }
    }
}

欧拉筛

void ouLaShai(int n){
    for(int i = 2; i<=n; i++){
        if(!vis[i]) prime[primeNums++] = i;
        for(int j = 0; j<primeNums; j++){
            if(i*prime[j]>n) break;
            vis[i*prime[j]] = true;
            if(i%prime[j]==0) break;
        }
    }
}

---

STL

priority_queue

priority_queue<T, vector<T>, less<T>> q;//big num, high priority
priority_queue<T, vector<T>, greater<T>> q;//small num, low priority 

//priority setting of struct
//friend
struct fruit{
    string name;
    int price;
    friend bool operator < (fruit f1, fruit f2){
        return f1.price < f2.price;//价格高的优先级高
    }
}
priority_queue<fruit> q;

//cmp
struct cmp{
    bool operator()(fruit f1, fruit f2){
        return f1.price>f2.price;
    }
}//the operator is contrast to the sort
priority_queue<T, vector<T>, cmp> q;

//lambda
 auto cmp = [](const T& a, const T& b) -> bool {
             return a.second < b.second; 
        };
 priority_queue<T, vector<T>, decltype(cmp)> que(cmp);

---

并查集

class UnionFind {
private:
    vector<int> parent;
    int n_areas;
public:
    UnionFind(int n) {
        parent.resize(n);
        n_areas = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    //recursion
    int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }

        return parent[x];
    }

    //iteration
    int Find(int x){
        int tmp = x;
        while(x!=parent[x]){
            x = parent[x];
        }
        while(tmp!=parent[tmp]){
            int z = tmp;
            tmp = parent[tmp];
            parent[z] = x;
        }
        return x;
    }

    void Union(int x, int y) {
        int root_x = Find(x);
        int root_y = Find(y);
        if (root_x == root_y) return;

        parent[root_y] = root_x;
        n_areas--;
    }

    int get_total_areas() {
        return n_areas;
    }
};

---

图算法

Dijkstra算法

int n, G[MAXV][MAXV];//n is the num of nodes, MAXV is the max num of nodes
int dis[MAXV]；
bool vis[MAXV] = {false};

void Dijkstra(int start){
    fill(d,d+MAXV,INF);
    dis[start] = 0;
    for(int i = 0; i<n; i++){
        int u = -1, MIN = INF;
        for(int j = 0; j<n; j++){
            if(vis[j]==false && d[j]<MIN){
                u = j;
                MIN = d[j];
            }
        }
        //can't find d[u] smaller than INF，means the rest nodes do not connect with start
        if(u==-1) return;
        vis[u] = true;
        for(int v = 0; v<n; v++){
            if(vis[v] == false && G[u][v]!=INF && d[u] + G[u][v] < d[v]){
                d[v] = d[u] + G[u][v];
            }
        }
    }
}

---

Floyd算法

const int MAXV = 200;
int n,m;//n is num of the nodes, m is the num of edges
int dis[MAXV][MAXV];//minimum dis between i, j

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

---

Prim算法

int n, G[MAXV][MAXV];//n is the num of nodes, MAXV is the max num of nodes
int d[MAXV];
bool vis[MAXV] = {false};

int prim(){
    fill(d, d+MAXV,INT);
    d[0] = 0;
    int ans = 0;//sum of minimum spanning tree;
    for(int i = 0; i<n; i++){
        int u = -1, MIN = INF;
        for(int j = 0; j<n; j++){
            if(vis[j]==false && d[j]<MIN){
                u = j;
                MIN = d[j];
            }
        }
        //can't find d[u] smaller than INF，means the rest nodes do not connect with start
        if(u==-1) return -1;
        vis[u] = true;
        ans += d[u];
        for(int v = 0; v<n; v++){
            if(vis[v] == false && G[u][v]!=INF && d[u] + G[u][v] < d[v]){
                d[v] = G[u][v];
            }
        }
    }
    return ans;
}

---

Kruskal算法

struct edge{
    int u, v;
    int cost;
}E[MAXE];

int Kruskal(int n, int m){
    int ans = 0;
    UnionFind U(n);
    sort(E,E+m,[](struct edge a, struct edge b){
        return a.cost<b.cost;
    });
    for(int i = 0; i<m; i++){
        int faU = U.Find(E[i].u);
        int faV = U.Find(E[i].v);
        if(faU!=faV){
            U.Union(faU,faV);
            and += E[i].cost;
            if(U.get_total_areas()==1) break;
        }
    }
    if(U.get_total_areas()==1) return -1;
    else return ans;
}

---

拓扑排序

vector<int> G[MAXV];
int n, m inDegree[MAXV];

bool topologicalSort(){
    int num = 0;//num of nodes in the topological sequence
    queue<int> q;
    for(int i = 0; i<n; i++){
        if(inDegree[i]==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = 0; i<G[u].size(); i++){
            int v = G[u][i];
            inDegree[v]--;
            if(inDegree[v]==0){
                q.push(v);
            }
        }
        G[u].clear();
        num++;
    }
    if(num==n) return true;
    else return false;
}

---

动态规划

01背包问题

有n件物品，每件物品的重量为w[i],价值为c[i],现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的价值最大，其中每种物品都只有一件  

dp[i][v]表示前i件物品恰好装入容量为v的背包中所能获得的最大价值

for(int i = 1; i<=n; i++){
    for(int v = w[i]; v<=V; v++){
        dp[i][v] = max(dp[i-1][v], dp[i-1][v-w[i]]+c[i]);
    }
}

滚动数组优化：

for(int i = 1; i<=n; i++){
    for(int v = V; v>=w[i]; v--){
        dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
    }
}

---

完全背包

有n种物品，每种物品的单件重量为w[i],价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大，每种物品都有无穷件。

dp[i][v]表示前i件物品恰好装入容量为v的背包中所能获得的最大价值

for(int i = 1; i<=n; i++){
    for(int v = w[i]; v<=V; v++){
        dp[i][v] = max(dp[i-1][v], dp[i][v-w[i]]+c[i]);
    }
}

滚动数组优化

for(int i = 1; i<=n; i++){
    for(int v = w[i]; v<=V; v++){
        dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
    }
}

---

字典树

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

class Trie {
    Trie *child[26];
    bool isWord;
public:
    /** Initialize your data structure here. */
    Trie() {
        isWord = false;
        for(int i=0;i<26;i++){
            child[i] = nullptr;
        }
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie *t = this;
        for(char c: word){
            if(!t -> child[c-'a']){
                t->child[c-'a'] = new Trie();
            }
            t = t->child[c-'a'];
        }
        t->isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie *t = this;
        for(char c:word){
            if(!t -> child[c - 'a']){
                return false;
            }
            t = t->child[c - 'a'];
        }
        return t->isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie *t = this;
        for(char c:prefix){
            if(!t->child[c-'a']){
                return false;
            }
            t = t->child[c - 'a'];
        }
        return true;
    }
};

---

其他

lowbit

能被x整除的最大2的幂次

lowbit(x) = x&(-x)

---

位运算

a^b^c == a^c^b
0 ^ n = n;
n ^ n = 0;

---

求1+2+…+n

int sumNums(int n) {
    n && (n += sumNums(n-1));
    return n;
}

不用加减乘除法做加法

//^表示无进位求和
//&表示求每位的进位数
 int add(int a, int b) {
    if(a == 0){
        return b;
    }
    if(b == 0){
        return a; 
    }
    return add(a^b, (unsigned)(a&b) << 1); 
}