模板总结

数据结构与算法

发布日期: 2021-04-21

一般笔试题的时间限制是1秒或2秒，操作次数需要控制在 $<=10^8$。

$n \leq 30$, 指数级别, $dfs$+ 剪枝, 状态压缩dp
$n \leq 100$ => $O\left(n^{3}\right)$, floyd, dp
$n \leq 1000 => O\left(n^{2}\right), O\left(n^{2}\right. log(n) ), dp$, 二分, 朴素版Dijkstra, Prim, Bellman-Ford
$n \leq 10^5$ => $O(nlogn)$ => sort后贪心或者前缀和, 归并排序, 线段树、树状数组、set/map, heap、拓扑排序、dijkstra+heap. prim+heap, spfa、二分区间、二分答案
$n \leq 10^6$ => $O(n)$=> 单调队列、单调栈、hash、双指针扫描、并查集, $kmp . AC$ 自动机，n较小的 $O( nlogn )$ 的做法: sort, 树状数组、heap. dijkstra, spfa,以及$O(n*m)$的做法:Trie树
$n \leq 10^7=>O(n)$, 双指针扫描, $kmp , AC$ 自动机、线性筛素数
$n \leq 10^{9} => O(\sqrt{n})$, 判断质数
$n \leq 10^{18} => O(logn)$, 最大公约数, 快速幂

二分答案(性质与自变量存在连续性及单调性)

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

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
// 查找单调递增序列中 >= x 的最小一个数
int bisectr(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]时使用：
// 查找单调递增序列中 <= x 的最大一个数
int bisectl(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

反转链表

ListNode* reverseList(ListNode* head) {
    ListNode *pre = nullptr;
    ListNode *cur=head;
    while(cur)
    {
        ListNode *ne=cur->next;
        cur->next=pre;
        pre=cur;
        cur=ne;
    }
    return pre;
}

快速幂

int qmi(int a, int b, int mod) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

最大公约数

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

快速排序

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

归并排序(逆序对)

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<deque>
using namespace std;

const int N=1000010;
int n,k;
int a[N];
int main()
{
    cin>>n>>k;
    deque<int> q;
    // 维护长度k区间的最小值
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(q.size()>0 && i-k+1>q.front()){
            q.pop_front();
        }
        while(q.size()>0 && a[q.back()]>=a[i]){
            q.pop_back();
        }
        q.push_back(i);
        if(i>=k-1){
            cout<<a[q.front()]<<" ";
        }        
    }
    q.clear();
    cout<<endl;
    // 维护长度k区间的最大值
    for(int i=0;i<n;i++){
        if(q.size()>0 && i-k+1>q.front()){
            q.pop_front();
        }
        while(q.size()>0 && a[q.back()]<=a[i]){
            q.pop_back();
        }
        q.push_back(i);
        if(i>=k-1){
            cout<<a[q.front()]<<" "; 
        }
    }
    return 0;
}

单调栈

输出每个数左边第一个比它小的数，如果不存在则输出 −1

#include<stack>

using namespace std;
int n;
int a[100010];
int main(){
    cin>>n;
    stack<int> stk;
    for(int i=0;i<n;i++){
        cin>>a[i];
        while(stk.size()>0 && stk.top()>=a[i]){
            stk.pop();
        }
        if(stk.size()>0){
            cout<<stk.top()<<" ";
        }
        else cout<<"-1 ";
        stk.push(a[i]);
    }
    return 0;
}

Trie树

int trie[N][26], tot = 1, cnt[N], n, m;
void insert(string s) {
    int len = s.length(), p = 1;
    for (int k = 0; k < len; k++) {
        int ch = s[k] - 'a';
        if (!trie[p][ch]) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    cnt[p]++;
}
int find(string t) {
    int len = t.length(), p = 1;
    for (int k = 0; k < len; k++) {
        p = trie[p][t[k] - 'a'];
        if (p == 0) return ans;
        ans += cnt[p];
    }
    return ans;
}

并查集

int f[N], sz[N], n;
void init() {
    for (int i = 0; i <= n; i++) {
        f[i] = i;
        sz[i] = 1;
    }
}
int find(int x) {
    if (x != f[x]) f[x] = find(f[x]);
    return f[x];
}
void merge(int a, int b) {
    int fa = find(a), fb = find(b);
    if (fa == fb) return;
    if (sz[fa] < sz[fb]) {
        f[fa] = fb;
        sz[fb] += sz[fa];
    } else {
        f[fb] = fa;
        sz[fa] += sz[fb];
    }
}
init();

树状数组

int find(int x) {
    int ans = 0;
    for (int i = x; i!=0; i -= i & -i) ans += tr[i];
    return ans;
}
void add(int x, int c) {
    for (int i = x; i <= n; i += i & -i) tr[i] += c;
}

线段树

typedef long long ll;
ll a[N],tr[4*N],t[4*N];

void pushup(int u)
{
    tr[u]=tr[u<<1]+tr[u<<1|1];
}
void pushdown(int u,int l,int r)
{
    if(t[u]!=0)
    {
        int mid=l+r>>1;
        tr[u<<1]+=t[u]*(mid-l+1);
        tr[u<<1|1]+=t[u]*(r-mid);
        t[u<<1]+=t[u];
        t[u<<1|1]+=t[u];
        t[u]=0;
    }
}
void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
ll sum(int u,int l,int r,int s,int e)
{
    if(s<=l&&e>=r)return tr[u];
    int mid=l+r>>1;
    pushdown(u,l,r);
    ll res = 0;
    if(s<=mid)res+=sum(u<<1,l,mid,s,e);
    if(e>=mid+1)res+=sum(u<<1|1,mid+1,r,s,e);
    return res;
}
void update(int u,int l,int r,int s,int e,ll c)
{
    if(s<=l&&e>=r)
    {
        tr[u]+=c*(r-l+1);
        t[u]+=c;
        return ;
    }
    int mid = l+r>>1;
    pushdown(u,l,r);
    if(s<=mid)update(u<<1,l,mid,s,e,c);
    if(e>=mid+1)update(u<<1|1,mid+1,r,s,e,c);
    pushup(u);
}

筛质数

int v[N];
void primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (v[i]) continue;
        cout << i << endl;
        for (int j = i; j <= n/i; j++) v[i*j] = 1;
    }
}

线性筛

int primes[N], cnt;
bool st[N];
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;
        }
    }
}

拓扑排序

queue<int> q;
for(int i=1;i<=n;i++)
    if (!indegree.count(i))
    {
        indegree[i] = 0;
        q.push(i);
    }
while(q.size())
{
    node = q.front();
    res.push_back(node);
    q.pop();
    for (auto ne:pre[node])
    {
        indegree[ne]--;
        if (indegree[ne]==0) q.push(ne);
    }
}
if (res.size()!=n) cout << -1;
else{
    for (int i=0;i<res.size();i++)
    {
        cout << res[i] << ' ';
    }
}

最短路

dijskra+heap

void dijkstra() {
typedef pair<int, int> PII;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    pq.push({0, 1});
    while (pq.size()) {
        int x = pq.top().second;
        pq.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                pq.push({d[y], y});
            }
        }
    }
}

spfa

void spfa() {
    queue<int> q;
    memset(d, 0x3f, sizeof d);
    d[1] = 0, v[1] = 1;
    q.push(1);
    while (q.size()) {
        int x = q.front();
        q.pop();
        st[x] = 0;
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                if (!v[y]) q.push(y), v[y] = 1;
            }
        }
    }
}

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

最小生成树

prim

void prim() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i = 1; i < n; i++) {
        int x = 0;
        for (int j = 1; j <= n; j++) {
            if (!v[j] && (x == 0 || d[j] < d[x]))
                x = j;
        }
        v[x] = 1;
        for (int y = 1; y <= n; y++) {
            if (!v[y]) d[y] = min(d[y], a[x][y]);
        }
    }
}

kruskal

struct edge {
    int x, y, w;
    bool operator<(const edge& b) {
        return w < b.w;
    }
} e[M];
sort(e + 1, e + m + 1);
// 并查集
for (int i = 1; i <= n; i++) f[
int find(int x)
{
    if(x!=f[x])f[x]=find(f[x]);
    return f[x];
}
for (int i = 1; i <= m; i++) {
    int x = find(e[i].x);
    int y = find(e[i].y);
    if (x == y) continue;
    f[x] = y;
    ans += e[i].z;
}

kmp

p为模板串
s为目标串
int n=p.size(),m=s.size();
void calcne() {
    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;
    }
}
for (int i = 1, j = 0; i <= m; i++) {
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j++;
    if (j == n) {
        printf("%d ", i - n);
    }
}

manacher

int manacher() {
    n = strlen(s);
    str[0] = '!', str[1] = '#';
    for (int i = 0; i < n; i++) {
        str[i * 2 + 2] = s[i];
        str[i * 2 + 3] = '#';
    }
    m = n * 2 + 1;
    str[m + 1] = '@'; 

    int rt = 0, mid = 0;
    int res = 0;
    for (int i = 1; i <= m; i++) {
        p[i] = i < rt ? min(p[2 * mid - i], rt - i) : 1;
        while (str[i + p[i]] == str[i - p[i]]) p[i]++;
        if (i + p[i] > rt) {
            rt = i + p[i];
            mid = i;
        }
        res = max(res, p[i] - 1);
    }
    return res;
}

dp

背包dp

for(int i=1;i<=n;i++)//遍历物品
{
    for(int j=V;j>=v[i];j--)//遍历体积 只能用一次反向遍历，无限用正向遍历
    {
        dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    }
}

数位dp

typedef long long ll

int k[n.length];   
ll f[n.length];    
ll dfs(int pos,int lead,int limit){
    if(!pos){return 1;} 
    if(!limit&&!lead&&f[pos]!=-1)return f[pos];
    int up=limit?k[pos]:9;
    int res=0;
    for(int i=0;i<=up;++i){
        if(){}
        else if(){}
        ans+=dfs(pos-1,limit&&i==up,lead&&i==0);
    }
    if(!limit&&!lead)f[pos]=res;
    return res;
}
ll dp(int x){//获取n的上界数组
    int pos=0;
    while(x){
        k[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,true,true);
}
int cntnums(int n) {
    memset(f,-1,sizeof f);
    return f(n);
}

最长上升子序列dp

for(int i=0;i<n;i++)
    {
        dp[i]=1;//以i结尾 的最大上升子序列长度
        for(int j=0;j<=i;j++)
        {
            if(q[i]>q[j])
            {
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
    }

二分优化$O(nlogn)$

stk.push_back(q[0]);
    for(int i=1;i<n;i++)
    {
        if (q[i]>stk.back())
            stk.push_back(q[i]);
        else
        {
            int l=0,r=stk.size();
            while(l<r)
            {
                int mid=(l+r)/2;
                if(stk[mid]<q[i]) l=mid+1;
                else r=mid;
            }
            stk[l] = q[i];
        }
    }

状压dp

枚举子集

for(int subset=set;subset!=0;subset=(subset-1)&set)
{
    f[set] = f[subset] + 转移规则
}
subset = set
while(subset):
    f[set] = f[subset] + 转移规则 
    subset = (subset-1)&set

状态转移

for(int cur=0;cur<1<<N;cur++):
{
    for(int i=0;i<N;i++)
    {
        if (state>>i)&1:
        {
            for(int j=0;j<N;j++)
            {
                if(j!=i && (state>>j)&1)
                {
                    f[cur] += f[cur-1<<i-1<<j];
                }
            }
        }
    }
}
    
return f[(1<<N)-1]

树形dp

void dfs(int u)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u] += max(f[u],f[j]);
    }
}

Leopold

https://leopoldacc.github.io/Blogs/Blogs/2021/04/21/%E6%A8%A1%E6%9D%BF%E6%80%BB%E7%BB%93/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Leopold !

模板

Bayesian network贝叶斯神经网络及其改进

2021-09-20 深度学习

深度学习神经网络贝叶斯方法

区间DP

2020-12-25 数据结构与算法

区间型动态规划

二分答案(性质与自变量存在连续性及单调性)

反转链表

快速幂

最大公约数

快速排序

归并排序(逆序对)

单调队列

单调栈

Trie树

并查集

树状数组

线段树

筛质数

线性筛

拓扑排序

最短路

dijskra+heap

spfa

floyd

最小生成树

prim

kruskal

kmp

manacher

dp

背包dp

数位dp

最长上升子序列dp

状压dp

树形dp

你的赏识是我前进的动力