单链表

利用数组模拟链表，相当于链式前向星。head表示头结点的下标，e[i]表示i节点的值，ne[i]表示i节点指向的下一个节点的下标，idx表示当前可用的最后一个下标；因为idx从0开始不是从1开始，所以题目输入的k在用的时候需要-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
using namespace std;
const int N = 100010;
int head, e[N], ne[N], idx;
void Init()//初始化
{
    head = -1;
    idx = 0;
}
void add_to_head(int x)//头结点的插入
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}
void add(int k, int x)//任意节点的插入
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}
void delete_k(int k)
{
    ne[k] = ne[ne[k]];
}
int main()
{
    int n;
    cin >> n;
    Init();
    while(n--)
    {
        char x;	cin >> x;
        int k, val;
        if(x == 'H')
        {
            cin >> val;
            add_to_head(val);
        }
        else if(x == 'I')
        {
            cin >> k >> val;
            add(k - 1, val);
        }
        else if(x == 'D')
        {
            cin >> k;
            if(!k) head = ne[head];//如果k==0
            else delete_k(k - 1);
        }
    }
    for(int i = head; i != -1; i = ne[i])
        cout << e[i] << " ";
    return 0;
}

双链表

根据单链表的经验，双链表只需要添加指向前一个结点的数组即可；这里我们省略head和tail，让0是左端点，1是右端点，那么idx就从2开始；在初始的时候head指向tail，tail指向head，因为前后节点都知道，所以只需要写一个插入函数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
using namespace std;
const int N = 100010;
int e[N], le[N], re[N], idx;
void Init()//初始化，头尾是没有值的，只是标记
{
    le[1] = 0;//尾节点的前一个节点是头结点
    re[0] = 1;//头结点的后一个节点是尾节点
    idx = 2;
}
void Insert(int k, int x)//插入到k的后面
{
    e[idx] = x;
    le[idx] = k;
    re[idx] = re[k];
    le[re[k]] = idx;
    re[k] = idx;
    idx++;
}
void Delete(int k)
{
    re[le[k]] = re[k];
    le[re[k]] = le[k];
}
int main()
{
    int m;
    cin >> m;
    Init();
    while(m--)
    {
        string s;
        cin >> s;
        int x, k;
        if(s == "L")
        {
            cin >> x;
            Insert(0, x);//头插，0是头，插到0的后面
        }
        else if(s == "R")
        {
            cin >> x;
            Insert(le[1], x);//1是尾，插入到尾的前面
        }
        else if(s == "D")
        {
            cin >> k;
            Delete(k + 1);//因为idx从2开始，所以要+1
        }
        else if(s == "IL")
        {
            cin >> k >> x;
            Insert(le[k + 1], x);
        }
        else if(s == "IR")
        {
            cin >> k >> x;
            Insert(k + 1, x);
        }
    }
    for(int i = re[0]; i != 1; i = re[i])
        cout << e[i] << " ";
    return 0;
}

表达式求值

建两个栈，一个存数字，一个存运算符

需要注意：

  1. 遇到一个字符是数字，需要判断后面是不是接着是数字，将字符串转换成数字
  2. 结束条件之一是没有剩余的运算符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <stack>
#include <unordered_map> 
#include <string>
using namespace std;
const int N = 1e5 + 10;
stack<int> num;
stack<char> sg;
unordered_map<char, int> mp{ {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };//用来存储各运算符的优先级

void eval()//进行运算
{
    int a = num.top();	num.pop();
    int b = num.top();	num.pop();
    char op = sg.top();	sg.pop();
    int r = 0;//计算结果
    if(op == '+')  r = b + a;
    else if(op == '-') r = b - a;
    else if(op == '*') r = b * a;
    else r = b / a;
    num.push(r);
}
int main()
{
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++)
    {
        if(isdigit(s[i])) //如果是数字
        {
            int j = i, x = 0;
            while(j < s.size() && isdigit(s[j]))//判断后面是否有跟着的数字
            {
                x = x * 10 + s[j] - '0';
                j++;
            }
            num.push(x);
            i = j - 1;
        }
        else if(s[i] == '(')//左括号直接入栈
        {
            sg.push(s[i]);
        }
        else if(s[i] == ')')
        {
            while(sg.top() != '(')//右括号计算到左括号为止
                eval();
            sg.pop();
        }
        else 
        {
            //还有没有用的运算符并且栈顶的优先级高，就计算
            while(sg.size() && mp[sg.top()] >= mp[s[i]])
                eval();
            sg.push(s[i]);
        }
    }
    while(sg.size()) eval();//计算剩下的表达式
    cout << num.top();
    return 0;
}

单调栈

解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int st[N], tt = 0;
int main()
{
    int n;  cin >> n;
    while(n--)
    {
        int x;  cin >> x;
        while(tt && st[tt] >= x) tt--;//如果栈不为空，并且栈顶元素比当前元素大，就出栈
        if(!tt) cout << -1 << " ";
        else cout << st[tt] << " ";
        st[++tt] = x;//当前元素入栈，先++，保证tt==0的时候栈为空
    }
    return 0;
}

单调队列

首先根据题意我们知道可以用队列模拟滑动窗口，但是如果直接暴力的话，时间复杂度是O(nk)，显然会超时，这时候就可以用单调队列优化，即将不需要的数字删去，看最后队列中的数是否具有单调性，如果有，就可以用单调队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N], a[N];//q是队列，a是存储数据的数组
int main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    //最小值
    int hh = 0, tt = -1;
    for(int i = 0; i < n; i++)
    {
        //判断需不需要让窗口往后移
        if(hh <= tt && i - k + 1 > q[hh]) ++hh;
        //因为是找最小值，所以如果新出现的元素比左边的元素小，那么在窗口右移的过程中，左边的那个更大的元素必定用不到，所以删去
        while(hh <= tt && a[i] <= a[q[tt]]) --tt;
        q[++tt] = i;//将新元素加进队列
        //整个队列单调增，所以hh位置元素最小
        if(i >= k - 1) cout << a[q[hh]] << " ";
    }
    cout << '\n';
    
    //最大值
    hh = 0, tt = -1;
    for(int i = 0; i < n; i++)
    {
        //如果当前队列中的元素个数大于k，需要队首出队
        if(hh <= tt && i - k + 1 > q[hh]) ++hh;
        //因为找最大值，所以如果新出现元素更大，同上，删去左边的元素
        while(hh <= tt && a[i] >= a[q[tt]]) --tt;
        q[++tt] = i;//在队列里面存下标
        //整个队列单调减，hh位置元素最大
        if(i >= k - 1) cout << a[q[hh]] << " ";
    }
    return 0;
}

KMP算法

  1. 暴力，i指针遍历s字符串，j指针遍历p字符串；如果遍历不成功i就会回退，时间复杂度是O(mn)会超时
  2. KMP优化，利用next数组，让i指针不回退，如果不成功就让j根据next数组跳转，next跳转的位置前面的字符串应该与当前匹配到的位置前面的字符串一致；时间复杂度O(m + n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
char s[M], p[N];
int ne[N];
int main()
{
    int n, m;
    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];
 //前面有字符串并且当前字符串不匹配，就让j跳转到有相同前缀的子串后面，比如字符串abcabab，在倒数第二个a后面的b不匹配的时候跳转到第一个a
        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];//不匹配就让j跳转
        if(p[j + 1] == s[i]) j++;
        if(j == n) 
        {
            cout << i - n << " ";//因为题目要求的下标从0开始，但是程序写的时候是从1开始
            j = ne[j];//如果已经匹配完成，看要匹配的字符串里面有没有相同的前后缀，避免二次匹配，所以跳转到ne[j]
        }
    }
    return 0;
}

Trie树

高效存储和查找字符串集合的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include<string>
using namespace std;
const int N = 1e5 + 10;//注意！N是最长字符串的长度！！！！！！！！
int son[N][26], cnt[N], idx;
//son的第一维表示编号，一条一条递增，第二维表示字母；总体表示trie树
//cnt用来标记字符串的结尾，以及有几个字符串以这个字母结尾
//idx用来表示当前的编号

void Insert(string s)
{
    int p = 0;//相当于指针
    for(int i = 0; s[i]; i++)
    {
        int u = s[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];//让p到子节点的位置，寻找子节点的子节点
    }
    cnt[p]++;//尾节点标记
}
int Query(string s)
{
    int p = 0;
    for(int i = 0; s[i]; i++)
    {
        int u = s[i] - 'a';
        if(son[p][u]) p = son[p][u];//如果有这个字母，就接着往下遍历
        else return 0;//否则不存在这个字符串
    }
    return cnt[p];
}
int main()
{
    char x;
    string s;
    int n;  cin >> n;
    while(n--)
    {
        cin >> x >> s;
        if(x == 'I') Insert(s);
        else cout << Query(s) << endl;
    }
    return 0;
}

最大异或对

利用Trie树，从高位到低位存储每一个数的二进制形式；利用遍历，尽量找每一位都不一样的数，从而找到每一个数与其他数异或中的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 31 * N;
int a[N], son[M][2], idx;

void Insert(int x)//建立Trie树
{
    int p = 0;
    for(int i = 30; ~i; i--)//~i相当于i >= 0
    {
        int u = x >> i & 1;//判断这一位是0/1
        if(!son[p][u]) son[p][u] = ++idx;///建树
        p = son[p][u];
    }
}
int Query(int x)
{
    int p = 0;
    int res = 0;
    for(int i = 30; ~i; i--)
    {
        int u = x >> i & 1;
        if(son[p][!u])//看是否有和这一位01相反的数
        {
            p = son[p][!u];
            res = 2 * res + 1;//如果有，在结果中这一位是1，所以+1
        }
        else
        {
            p = son[p][u];
            res = 2 * res + 0;
        }
    }
    return res;
}
int main()
{
    int n;  cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        Insert(a[i]);
    }
    int res = 0;
    for(int i = 0; i < n; i++)
        res = max(res, Query(a[i]));//遍历判断
    cout << res;
    return 0;
}

并查集

  1. 将两个集合合并
  2. 询问两个元素是否在同一个集合中

用p数组表示该集合中元素的父节点，当p[i] == i的时候，i是根节点

合并集合：让两个数的根节点合并

是否在同一个集合：判断根节点是否相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N];
int find(int x)//找到根节点
{
    //递归到根节点并且做路径压缩，让这条路上的所有结点直接指向根节点
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
void Merge(int a, int b)//合并
{
    p[find(a)] = find(b);
}
string Query(int a, int b)//判断
{
    if(find(a) == find(b)) return "Yes";
    else return "No";
}
int main()
{
    char x; 
    int a, b;
    int n, m;  cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;//不要忘记初始化！！！
    while(m--)
    {
        cin >> x >> a >> b;
        if(x == 'M')
            Merge(a, b);
        else
            cout << Query(a, b) << endl;
    }
    return 0;
}

食物链

  1. 根据分析，如果将整个食物链连成一棵树，那么到根节点距离
    • 除3余0，就跟根节点为同类
    • 除3余1，就被根节点吃
    • 除3余2，就吃根节点
  2. 返回值为bool的函数，一定要保证每条路径有返回值
  3. 找到x， y的根节点，如果根节点不一样，则跟前面的话不可能冲突，所以一定是真话，将二者的关系加上即可；如果一样就通过到根节点的距离除3的余数判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
using namespace std;
const int N = 5e4 + 10, M = 3;
int d[N], fa[N];
int find(int x)
{
    if (x != fa[x])
    {
        int t = find(fa[x]);//找到fa[x]的根节点
        //设置一个新的变量t而不是直接更新x的父节点是根节点是因为后面更新d[x]需要用到x的fa[x]的距离值
        d[x] += d[fa[x]];//更新d[x]的距离，d[x]表示x到其父节点的距离
        fa[x] = t;//更新x的父节点为根节点
    }
    return fa[x];
}
bool D1(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx == fy && (d[y] - d[x] + M) % M) return false;//因为d mod 3的余数相同表示是同一类，+M是怕d[y] - d[x] < 0
    else if (fx != fy)//表示二者没有关系，一定不是假话，让x, y变成同类
    {
        fa[fx] = fy;
        //(d[x] + ?) % 3 == d[y] % 3，其中?表示fx到fy的距离，即d[fx]
        d[fx] = d[y] - d[x];
        return true;//返回true！！！！！！！！！
    }
    return true;//返回true！！！！！！！！！
}
bool D2(int x, int y)//x吃y
{
    int fx = find(x), fy = find(y);
    if (fx == fy && (d[y] - d[x] - 1 + M) % M)//第0代吃第1代...，第二项等于0表示X吃Y
        return false;
    else if (fx != fy)
    {
        fa[fx] = fy;
        d[fx] = (d[y] - 1 - d[x] + M) % M;//画个图，x吃y，可以知道x距离根节点比y距离根节点多1
        return true;//返回true！！！！！！！！！
    }
    else return true;//返回true！！！！！！！！！
}
int main()
{
    int n, k;   cin >> n >> k;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        d[i] = 0;
    }
    while (k--)
    {
        int D, x, y;
        cin >> D >> x >> y;
        if (x > n || y > n)
        {
            cnt++;
            continue;
        }
        int fx = find(x), fy = find(y);
        if (D == 1)
            if(!D1(x, y)) cnt++;
        if (D == 2)
            if (!D2(x, y)) cnt++;
    }
    cout << cnt;
    return 0;
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N];
void down(int p, int n)
{
    int c = p * 2;
    while (c <= n)
    {
        if (c + 1 <= n && a[c] > a[c + 1]) c++;
        if (a[c] < a[p])
        {
            swap(a[c], a[p]);
            p = c;
            c = p * 2;
        }
        else break;
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int cnt = n;
    for (int i = n / 2; i; i--)  down(i, n);
    while (m--)
    {
        cout << a[1] << " ";
        a[1] = a[cnt--];
        down(1, cnt);
    }
}

模拟散列表

链地址法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 3;//大于1e5的质数
int h[N], ne[N], e[N], idx;//链式前向星
void Insert(int x)
{
    int k = (x % N + N) % N;//将x映射到0~N
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}
string Query(int x)
{
    int k = (x % N + N) % N;
    for(int i = h[k]; i != -1; i = ne[i])
    {
        if(e[i] == x) return "Yes";
    }
    return "No";
}
int main()
{
    memset(h, -1, sizeof h);
    int n;  cin >> n;
    while(n--)
    {
        char op; cin >> op;
        if(op == 'I')
        {
            int x;  cin >> x;
            Insert(x);
        }
        else if(op == 'Q')
        {
            int x;  cin >> x;
            cout << Query(x) << endl;;
        }
    }
    return 0;
}

开放寻址法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5 + 3;
const int null = 0x3f3f3f3f;
int h[N];
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;    
}
int main()
{
    memset(h, null, sizeof h);
    int n;  cin >> n;
    while(n--)
    {
        char op;    
        int x;
        cin >> op >> x;
        if(op == 'I')
        {
            h[find(x)] = x;
        }
        else 
        {
            if(h[find(x)] == null) cout << "No" << endl;
            else cout << "Yes" << endl;
        }
    }
    return 0;
}

字符串哈希

将字符串假设成为p进制的数，经过实验发现，当p=131或者p=1331的时候，可以当做没有冲突；然后就可以将字符串（p进制）转化成十进制数字，用p数组表示p的n次方，h数组存储前n个字符组成的字符串转换成的数字；可以利用前缀和的思想，发现h[s[l, r] ]= h[r] - h[l - 1] * p[r - l + 1];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
//冲突问题：通过巧妙设置P (131 或 13331) , Q (2^64)的值，一般可以理解为不产生冲突。
const int P = 131;
typedef unsigned long long ULL;
ULL h[N], p[N];
char s[N]; 
ULL Query(int l, int r)
{
    return h[r] - h[l - 1]* p[r - l + 1];
}
int main()
{
    int n, m;   cin >> n >> m;
     
    for(int i = 1; i <= n; i++) cin >> s[i];
    p[0] = 1, h[0] = 0;//p[i]表示p的i次方
    for(int i = 1; i <= n; i++)
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + s[i]; 
    }
    while(m--)
    {
        int l1, l2, r1, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(Query(l1, r1) == Query(l2, r2)) cout << "Yes" << endl;//如果两个字符串的哈希值相等，那么就说明两个字符串相等
        else cout << "No" << endl;
    }
    return 0;
}