Skip to content

Latest commit

 

History

History
444 lines (307 loc) · 7.77 KB

算法思想.md

File metadata and controls

444 lines (307 loc) · 7.77 KB
Raw

链表与邻接表

单链表：邻接表（存储图和树）

算法模板
void init() {
    head = -1;
    idx = 0;
}

void add_to_head(int x) {
    e[idx] = x, ne[idx] = head, head = idx++;
}

void add(int k, int x) {
	e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}

void remove(int k) {
    ne[k] = ne[ne[k]];
}

双链表：

算法模板
void init() {
    r[0] = 1, l[1] = 0;
    idx = 2;
}

void add_to_head(int x) {
    e[idx] = x;
    l[idx] = 0;
    r[idx] = r[0];
    r[0] = idx++;
}

void add_to_back(int x) {
    e[idx] = x;
    r[idx] = 1;
    l[idx] = l[1];
    l[1] = idx++;
}

void addR(int k, int x) {
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx++;
}

void addL(int k, int x) {
    e[idx] = x;
    l[idx] = l[k];
    r[idx] = k;
    r[l[k]] = idx;
    l[k] = idx++;
}

void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

栈与队列

栈模板

int stk[N], tt;

void push(int x) {
	stk[++tt] = x;    
}

void pop() {
    --tt;
}

bool empty() {
    return tt > 0;
}

int top() {
    return stk[tt];
}

单调栈

给定一个序列，求每一个数的左边，离他最近的满足某种性质的数的位置

这里是找离他最近的并且 自己 大于他的位置

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int stk[N], tt;

int main() {
    int n, x;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cin >> x;
        
        while (tt > 0 && stk[tt] >= x) tt--;
        if (tt) cout << stk[tt] << ' ';
        else cout << "-1 ";
        
        stk[++tt] = x;
    }
}

队列模板

int q[N], hh, tt = -1;

void push(int x) {
    q[++tt] = x;
}

void pop() {
    hh++;
}

bool empty() {
    return hh <= tt;
}

int front() {
    return q[hh];
}

int back() {
    return q[tt];
}

单调队列

求滑动窗口里的最值

#include <iostream>
using namespace std;

const int N = 1e6 + 10;

int q[N], tt = - 1, hh;
int a[N];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i - q[hh] >= k) hh++;
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = a[i];
        if (i >= k - 1) cout <<  q[hh] << " ";
    }
    cout << endl;
    tt = -1, hh = 0;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i - q[hh] >= k) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = a[i];
        if (i >= k - 1) cout << q[hh] << " ";
    }
}

KMP

朴素做法

int find(const string & s, const string & p) {
    int n = s.size(), m = p.size();
    for (int i = 1; i <= n; i++) {
        bool flag = true;
        for (int j = 1; j <= m; j++)
            if (s[i + j - 1] != p[j]) {
                flag = flase;
                break;
            }
        if (flag) return i;
    }
    return -1;
}

算法思想

求模式串的最长前缀后缀长度，是每次失匹能少移动

如 ASDFASDF ，对应的前缀后缀长度为 00001233

这样如果在 第二个 S 失匹，只需要把字符串移动到 ASD ，让 D 与 文本串的字符去对比，尽可能利用已经匹配的信息

如何求模式串的最长前缀后缀长度？

自己和自己匹配

算法模板

for (int i = 2, j = 0; i <= m; i++) {
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == [j + 1]) j++;
    ne[i] = j;
}

for (int i = 1, j = 0; i <= n; i++) {
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j++;
    if (j == m) return i - m + 1;
}

Trie 树

作用：高效存储和查找字符串集合
注意： 空间开大点

数据结构模板

int son[N][26], cnt[N], idx;

void insert(const string & str) {
    int p = 0;
    for (char ch : str) {
        if (!son[p][ch - 'a']) son[p][ch - 'a'] = ++idx;
        p = son[p][ch - 'a'];
    }
    cnt[p]++;
}

int query(const string & str) {
    int p = 0;
    for (char ch : str) {
        if (!son[p][ch - 'a']) return 0;
    	p = son[p][ch - 'a'];
    }
    return cnt[p];
}

并查集

算法模板
int p[N];
int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}

void join(int x, int y) {
    p[find(x)] = find(y);
}

堆

堆结构是一种数组对象，它可以被看作为一颗完全二叉树。树中的每个结点与数组中存放该结点中值的那个元素相对应。

性质

设数组A的长度为len，二叉树的节点个数为size，size$<=$len,则A[i]存储二叉树中编号为i的节点值$(1<=i<=size)$而A[size]以后的元素并不属于相应的堆，树的根为A[1]，并且利用完全二叉树的性质，我们很容易求得第i个结点得父亲结点左孩子结点和右孩子结点
更重要的是，堆具有这样的一个性质，对除跟以外的每个结点i，A[parent[i]]>=a[i]。也就是说除根结点以外，所有结点的值都不能超过父亲的值，这样就推出，堆中最大的元素存放在根节点中这种堆被称为大根堆反之被成为小根堆

完全二叉树

  1. 若i=1，其为根结点无父亲结点，否则对任意结点i，其父亲结点都为i/2
  2. 若2*i>n其没有左孩子，也没有右孩子，否则左孩子编号为 2i；
  3. 若2*i+1>n,则结点i无右孩子，否则右孩子为2i+1

堆的操作

用堆关键部分是2个操作 put操作既往堆中加入一个元素，get操作，从堆中取出并删除一个元素

扩展操作

  1. 删除任意一个元素
  2. 修改任意一个元素
算法模板
void up(int u) {
    while (u >> 1 && h[u >> 1] > h[u]) {
        swap(h[u[, h[u >> 1]);
        u >>= 1;
    }
}

void down(int u) {
    int v = u;
    if (lc(u) <= idx && h[lc(u)] < h[v]) v = lc(u);
    if (rc(u) <= idx && h[rc(u)] < h[v]) v = rc(u);
    if (v != u) {
        swap(h[u], h[v]);
        down(v);
    }
}

哈希表

算法模板
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 3;

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

inline int hash_(int x) {
    return ((x % N) + N) % N;
}

void insert(int x) {
    int k = hash_(x);
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool query(int x) {
    int k = hash_(x);
    for (int i = h[k]; i != -1; i = ne[i]) if (e[i] == x) return true;
    return false;
}

int main() {
    int n, x;
    char op;
    cin >> n;
    
    memset(h, -1, sizeof(h));
    
    while (n--) {
        cin >> op >> x;
        if (op == 'I') insert(x);
        else cout << (query(x) ? "Yes" : "No") << endl;
    }
}

字符串哈希

算法原理

字符串前缀映射成 P 进制数

不能把某个字母映射成0，会导致 "A" == "AA"

算法模板

#include <iostream>
#include <string>
using namespace std;

typedef unsigned long long ull;
const int N = 1e5 + 10;

ull h[N], p[N];

ull get_hash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1]; 
}

int main() {
    string str;
    int n, m;
    cin >> n >> m >> str;
    p[0] = 1;
    for (int i = 1; i <= str.size(); i++) {
        p[i] = p[i - 1] * 131;
        h[i] = h[i - 1] * 131 + (str[i - 1] - 'A' + 1);
    }
    
    int l1, r1, l2, r2;
    while (m--) {
        cin >> l1 >> r1 >> l2 >> r2;
        cout << (get_hash(l1, r1) == get_hash(l2, r2) ? "Yes" : "No") << endl;
    }
}