二叉树的struct

  • 二叉树的题必须要完成的第一步：设置一个struct,表示二叉树结点
1
2
3
4
5
6
7
struct node
{
    int value;
    node *left;
    node *right;
    node(int v) : value(v), left(NULL), right(NULL) {}
};

二叉树的输出

  • 先判断边界

深度优先遍历输出

  • 核心思想是递归。按照先根次序、中跟次序、后根次序将value在不同位置输出
1
2
3
4
5
6
7
8
9
10
11
void out_preorder(node *root)
{
    if (root == nullptr)
    {
        return;
    }
    cout << root->value << " ";
    out_preorder(root->left);
    out_preorder(root->right);
    delete root;
}

宽度优先遍历输出

  • 核心思想是队列：利用辅助队列加入树中的元素并且按层次输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void out_tree(node *root)
{
    if (root == nullptr)
    {
        return;
    }
    queue<node *> q;
    q.push(root);
    while (!q.empty())
    {
        node *current = q.front();
        q.pop();
        cout << current->val << " ";
        if (current->left != nullptr)
        {
            q.push(current->left);
        }
        if (current->right != nullptr)
        {
            q.push(current->right);
        }
    }
}

建立堆

建立最大值堆

1
2
3
#include <queue>

priority_queue<int> maxHeap;

建立最小值堆

1
2
3
#include <queue>

priority_queue<int,vector<int>,greater<int>> minHeap;

建立二叉搜索树

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
node *insert(node *root, int v)
{
    if (root == nullptr)
    {
        node *root1 = new node(v);
        return root1;
    }
    if (v < root->val)
    {
        root->left = insert(root->left, v);
    }
    else if (v > root->val)
    {
        root->right = insert(root->right, v);
    }
    return root;
}

int main()
{
    node *root = nullptr;
    for (int i = 0; i < input.size(); i++)
    {
        root = insert(root, input[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
36
37
38
39
40
41
42
43
44
45
class Unionfind
{
public:
    vector<int> parent;
    vector<int> height;
    Unionfind(int n)
    {
        parent.resize(n);
        for (int i = 0; i < n; i++)
        {
            parent[i] = i; // 初始化成自己的父结点
        }
        height.resize(n, 0);
    }
    int find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    void unionsets(int x, int y)
    {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY)
        {
            if (height[rootX] > height[rootY])
            {
                parent[rootY] = rootX;
            }
            else if (height[rootX] < height[rootY])
            {
                parent[rootX] = rootY;
            }
            else
            {
                parent[rootY] = rootX;
                height[rootX]++;
            }
        }
    }
};

合并并且考察一共有多少个并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Unionfind a(n);
for (int k = 0; k < m; k++)
{
    int i, j;
    cin >> i >> j;
    a.unionsets(i - 1, j - 1);
}
int total = 0;
for (int i = 0; i < n; ++i)
{
    if (a.find(i) == i)
    {
        total++;
    }
}

KMP算法

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
int* findNext(string P)
{
    int i = 0;
    int k = -1;
    int m = P.length();                 // m为字符串P的长度
    assert(m > 0);                      // m=0退出
    int * next = new int[m];            // 动态存储区开辟整数数组
    assert(next != 0)                   // 若开辟存储区域失败，退出
    next[0] = -1;
    while (i < m)
    {   //计算i=1...m-1的next值
        while (k >= 0 && p[i] != p[k])  // 求最大首尾子串
        {
            k = next[k];
        }
        i++;
        k++;
        if (i == m)
        {
            break;
        }
        if (p[i] == p[k])
        {
            next[i] = next[k];          // p[i]和p[k]相等，优化
        }
        else
        {
            next[i] = k;                // 不需要优化，就是位置i的首尾子串长度
        }
    }
    return next;
}
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
int KMPStrMatching (const String & T,const String & P,int * N)
{
    int i = 0;
    int j = 0;
    int pLen = P.length();
    int tLen = T.length();
    if (tLen < pLen)
    {
        return -1;
    }
    while (i < pLen && j < tLen)
    {
        if (i == -1 || T[j] == P[j])
        {
            i++;
            j++;
        }
        else
        {
            i = N[i];
        }
    }
    if (i >= pLen)
    {
        return j - pLen + 1;
    }
    else
    {
        return -1;
    }
}

计算前缀函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> computePrefixFunction(const string &s)
{
    int n = s.length();
    vector<int> pi(n, 0);   // 如果没有(n, 0)就会错误
    for (int i = 1; i < n; i++)
    {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
        {
            j = pi[j - 1];
        }
        if (s[i] == s[j])
        {
            j++;
        }
        pi[i] = j;
    }
    return pi;
}

循环串需要添加的字符数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> pi = computePrefixFunction(s);
int n = s.size();

// 根据前缀函数计算潜在的周期长度 p
int p = n - pi[n - 1];

// 如果 n % p != 0，说明当前字符串不是一个循环串
// 我们需要加上 p - (n % p) 个字符，才能形成循环串
if (n % p == 0)
{
    if (pi[n - 1] == 0)
    {
        cout << p << endl;
    }
    else
    {
        cout << 0 << endl;
    }
}
else
{
    cout << p - (n % p) << endl; // 添加的字符数
}

建立一个哈希表

一维匹配查找去重问题——unordered_set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <vector>
#include <unordered_set>

int main()
{
    unordered_set<int> seen;
    vector<int> result;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        if (seen.find(a[i]) == seen.end())  // 说明不重复，加入哈希表中
        {
            seen.insert(a[i]);
            result.push_back(a[i]);
        }
    }
}

二维匹配查找问题——unordered_map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <unordered_map>

int main()
{
    unordered_map<string, string> mp;
    string english, foreign;
    dic[foreign] = english;

    string word;
    while (cin >> word)
    {
        if (dic.find(word) == dic.end())
        {
            cout << "eh" << endl;
            continue;
        }
        else
        {
            cout << dic[word] << endl;
        }
    }
}

用最大堆和最小堆维护求中位数

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 <queue>

int main()
{
    priority_queue<int> maxheap;
    priority_queue<int,vector<int>,greater<int>> minheap;
    for (int i = 0; i < n; i++)
    {
        if (maxheap.empty() || a[i] <= maxheap.top())
        {
            maxheap.push(a[i]);
        }
        else
        {
            minheap.push(a[i]);
        }
        if (maxheap.size() > minheap.size() + 1)
        {
            minheap.push(maxheap.top());
            maxheap.pop();
        }
        if (maxheap.size() < minheap.size())
        {
            maxheap.push(minheap.top());
            minheap.pop();
        }
        if ((i % 2) == 0)
        {
            cout << maxheap.top() << endl;
        }
    }
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
double maxsize(double pies[], int N, int F)
{
    double left = 1;
    double right = pies[N-1];
    double result = 0.0;
    while (right - left > 0.00001)
    {
        double mid = (left + right) / 2.00;
        if (check(pies, N, F, mid))
        {
            left = (left + right) / 2.00;
        }
        else
        {
            right = (left + right) / 2.00;
        }
    }
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Find(int L, int distance[], int N, int M)
{
    sort(distance, distance + N);
    int left = 1;
    int right = L;
    int min = 0;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (check(mid, L, distance, N, M))
        {
            min = mid;
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return min;
}

归并排序

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*描述
对于一个长度为N的整数序列A，满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序
请求出整数序列A的所有逆序对个数
输入
输入包含多组测试数据，每组测试数据有两行
第一行为整数N(1 <= N <= 20000)，当输入0时结束
第二行为N个整数，表示长为N的整数序列
输出
每组数据对应一行，输出逆序对的个数
样例输入
5
1 2 3 4 5
5
5 4 3 2 1
1
1
0
样例输出
0
10
0*/

#include <iostream>  // 引入输入输出流库
#include <vector>    // 引入向量库
#include <algorithm> // 引入算法库，提供排序等函数
using namespace std; // 使用标准命名空间，避免每次都写 std::

int N, ans = 0;           // N表示序列长度，ans存储逆序对的数量
int a[20005], tmp[20005]; // a用于存储输入的整数序列，tmp用于辅助排序

// mergeSort 函数：递归进行归并排序，并在合并过程中统计逆序对
void mergeSort(int l, int r)
{
    if (l == r) // 如果左指针等于右指针，说明这个区间已经是单元素，不需要继续分割
        return;

    int mid = (l + r) / 2;
    mergeSort(l, mid);     // 递归对左半部分排序
    mergeSort(mid + 1, r); // 递归对右半部分排序

    int i = l, j = mid + 1, k = l; // i指向左半部分的起始位置，j指向右半部分的起始位置，k指向临时数组的起始位置

    // 合并过程，同时计算逆序对
    while (i <= mid && j <= r) // 当左右子序列都有元素时，进行合并
    {
        if (a[i] <= a[j])      // 如果左边的元素小于等于右边的元素
            tmp[k++] = a[i++]; // 将左边的元素放到临时数组中，i指针后移
        else                   // 否则，右边的元素小于左边的元素
        {
            tmp[k++] = a[j++];  // 将右边的元素放到临时数组中，j指针后移
            ans += mid - i + 1; // 计算逆序对：左侧有 mid - i + 1 个元素，它们都大于 a[j]
        }
    }

    // 将剩余部分填充到临时数组
    while (i <= mid)       // 如果左边部分还有剩余
        tmp[k++] = a[i++]; // 将左边剩余的元素放入临时数组
    while (j <= r)         // 如果右边部分还有剩余
        tmp[k++] = a[j++]; // 将右边剩余的元素放入临时数组

    // 将临时数组中的数据拷贝回原数组a
    for (int i = l; i <= r; ++i)
        a[i] = tmp[i]; // 这一步将排序后的数据复制回原数组a中

    return;
}

int main()
{
    // 主程序循环，处理多组测试数据
    while (cin >> N && N != 0) // 每次输入N，并且当N为0时结束
    {
        ans = 0; // 重置逆序对计数器

        // 输入整数序列a
        for (int i = 1; i <= N; i++) // 从1到N输入序列
        {
            cin >> a[i]; // 输入a数组的每个元素
        }

        // 调用mergeSort函数，对数组a进行排序，并统计逆序对数
        mergeSort(1, N); // 从1到N进行归并排序

        // 输出当前测试数据的逆序对个数
        cout << ans << endl; // 输出结果
    }

    return 0; // 程序结束
}

Dijkstra算法

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
class Dist 
{ // Dist类，用于保存最短路径信息
public:
    int index; // 结点的索引值，仅Dijkstra算法用到
    int length; // 当前最短路径长度
    int pre; // 路径最后经过的结点
};

void Dijkstra(Graph& G, int s, Dist* &D) 
{ // s是源点
    D = new Dist[G. VerticesNum()]; // 记录当前最短路径长度
    for (int i = 0; i < G.VerticesNum(); i++) 
    { // 初始化
        G.Mark[i] = UNVISITED;
        D[i].index = i; D[i].length = INFINITE; D[i].pre = s;
    }
    D[s].length = 0; // 源点到自身的路径长度置为0
    MinHeap<Dist> H(G. EdgesNum()); // 最小值堆用于找出最短路径
    H.Insert(D[s]);
    for (i = 0; i < G.VerticesNum(); i++) 
    {
        bool FOUND = false;
        Dist d;
        while (!H.isEmpty()) 
        {
            d = H.RemoveMin(); //获得到s路径长度最小的结点
            if (G.Mark[d.index] == UNVISITED) 
            { //如果未访问过则跳出循环
                FOUND = true; break;
            } 
        }
        if (!FOUND) break; // 若没有符合条件的最短路径则跳出本次循环
        int v = d.index;
        G.Mark[v] = VISITED; // 将标记位设置为 VISITED
        for (Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)) // 刷新最短路
            if (D[G.ToVertex(e)].length > (D[v].length+G.Weight(e))) 
            {
                D[G.ToVertex(e)].length = D[v].length + G.Weight(e);
                D[G.ToVertex(e)].pre = v;
                H.Insert(D[G.ToVertex(e)]);
            } 
    }
}
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/*描述
很久很久之前，森林里住着一群兔子。有一天，兔子们希望去赏樱花，但当他们到了上野公园门口却忘记了带地图。现在兔子们想求助于你来帮他们找到公园里的最短路。
输入
输入分为三个部分。
第一个部分有P+1行（P<30），第一行为一个整数P，之后的P行表示上野公园的地点, 字符串长度不超过20。
第二个部分有Q+1行（Q<50），第一行为一个整数Q，之后的Q行每行分别为两个字符串与一个整数，表示这两点有直线的道路，并显示二者之间的矩离（单位为米）。
第三个部分有R+1行（R<20），第一行为一个整数R，之后的R行每行为两个字符串，表示需要求的路线。
输出
输出有R行，分别表示每个路线最短的走法。其中两个点之间，用->(矩离)->相隔。
样例输入
6
Ginza
Sensouji
Shinjukugyoen
Uenokouen
Yoyogikouen
Meijishinguu
6
Ginza Sensouji 80
Shinjukugyoen Sensouji 40
Ginza Uenokouen 35
Uenokouen Shinjukugyoen 85
Sensouji Meijishinguu 60
Meijishinguu Yoyogikouen 35
2
Uenokouen Yoyogikouen
Meijishinguu Meijishinguu
样例输出
Uenokouen->(35)->Ginza->(80)->Sensouji->(60)->Meijishinguu->(35)->Yoyogikouen
Meijishinguu*/

// map 和数组分别用于节点名称到编号和反向映射
map<string, int> q; // string -> 节点编号
map<int, string> p; // 节点编号 -> string（名称）

// 邻接矩阵，mapp[i][j]表示从i到j的路径权重
int mapp[100][100];

// 记录是否访问过某节点的标记数组
int vis[10010];

// 记录到每个节点的最短距离
int low[5000];

// 记录从某节点出发的路径
int path[100010];

// 记录从每个节点的最短路径的反向路径
int re[10010];

// 节点数目和边数
int n, m, r;

// 读取的地点名称
string s1, s3, s2, s4, str;

// Dijkstra 算法实现
void dijkstra(int x)
{
    // 初始化访问数组和路径数组
    memset(vis, 0, sizeof(vis));
    memset(path, 0, sizeof(path));

    // 初始化每个节点的最短路径为无穷大，路径为自己
    for (int i = 1; i <= n; i++)
    {
        low[i] = 1e7; // 无穷大，表示当前没有路径
        path[i] = x;  // 起点的路径是它本身
    }

    // 起点的距离为0
    low[x] = 0;

    // Dijkstra 主循环
    for (int i = 1; i <= n; i++)
    {
        int u = -1;

        // 在未访问的节点中，找到距离起点最近的节点
        for (int j = 1; j <= n; j++)
        {
            if ((u == -1 || low[j] < low[u]) && vis[j] == 0)
            {
                u = j; // u 为当前未访问节点中，距离起点最近的节点
            }
        }

        // 标记u节点为已访问
        vis[u] = 1;

        // 更新从u节点出发的所有邻接节点的最短距离
        for (int k = 1; k <= n; k++)
        {
            if (vis[k] == 0 && low[k] > low[u] + mapp[u][k]) // 未访问的邻接节点
            {
                low[k] = low[u] + mapp[u][k]; // 更新最短距离
                path[k] = u;                  // 记录从哪个节点到达当前节点
            }
        }
    }
}

最小生成树Prim算法

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// Prim算法
/*描述
很久很久以前，森林里住着一群兔子。兔子们无聊的时候就喜欢研究星座。如图所示，天空中已经有了n颗星星，其中有些星星有边相连。
兔子们希望删除掉一些边，然后使得保留下的边仍能是n颗星星连通。他们希望计算，保留的边的权值之和最小是多少？
输入
第一行只包含一个表示星星个数的数n，n不大于26，并且这n个星星是由大写字母表里的前n个字母表示。接下来的n-1行是由字母表的前n-1个字母开头。
最后一个星星表示的字母不用输入。对于每一行，以每个星星表示的字母开头，然后后面跟着一个数字，表示有多少条边可以从这个星星到后面字母表中的星星。
如果k是大于0，表示该行后面会表示k条边的k个数据。每条边的数据是由表示连接到另一端星星的字母和该边的权值组成。权值是正整数的并且小于100。
该行的所有数据字段分隔单一空白。该星星网络将始终连接所有的星星。该星星网络将永远不会超过75条边。
没有任何一个星星会有超过15条的边连接到其他星星（之前或之后的字母）。在下面的示例输入，数据是与上面的图相一致的。
输出
输出是一个整数，表示最小的权值和
样例输入
9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
样例输出
216
提示
考虑看成最小生成树问题，注意输入表示。*/
#include <iostream>
#include <set>
using namespace std;
int main()
{
    int sum = 0;
    set<int> edge;
    int n;
    cin >> n;
    int dis[30];
    int A[30][30];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            A[i][j] = 1e6;
        }
        dis[i] = 1e6;
    }

    for (int i = 0; i < n - 1; i++)
    {
        int k;
        char c1;
        cin >> c1 >> k;
        int p1 = c1 - 'A';
        for (int j = 0; j < k; j++)
        {
            char c2;
            int d;
            cin >> c2 >> d;
            int p2 = c2 - 'A';
            A[p1][p2] = d;
            A[p2][p1] = d;
        }
    }

    edge.insert(0);
    for (int i = 0; i < n; i++)
    {
        dis[i] = min(dis[i], A[0][i]);
    }
    dis[0] = -1;

    while (edge.size() < n)
    {
        int min_num;
        int min_d = 1e6;
        for (int i = 0; i < n; i++)
        {
            if (dis[i] < min_d && dis[i] > 0)
            {
                min_num = i;
                min_d = dis[i];
            }
        }
        edge.insert(min_num);
        for (int i = 0; i < n; i++)
        {
            dis[i] = min(dis[i], A[min_num][i]); 
        }
        dis[min_num] = -1;
        sum += min_d;
    }
    cout << sum << endl;
    return 0;
}

在已排序的数组中查找值

已排序数组中查找第一个不小于某个值的位置

1
2
sort(a.begin(),a.end());
lower_bound(a.begin(), a.end(), val);

已排序数组中查找第一个大于某个值的元素的位置

1
2
sort(a.begin(),a.end());
upper_bound(a.begin(), a.end(), val);

复杂输入处理之连续整行数据

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
/*
输入
首先输入一个词典，词典中包含不超过100000个词条，每个词条占据一行。每一个词条包括一个英文单词和一个外语单词，两个单词之间用一个空格隔开。
而且在词典中不会有某个外语单词出现超过两次。词典之后是一个空行，然后给出一个由外语单词组成的文档，文档不超过100000行，而且每行只包括一个外语单词。
输入中出现单词只包括小写字母，而且长度不会超过10。
样例输入
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay
*/

// 整行的读入用while(true) 和 getline
// getline(cin, s) 会读取一行输入直到遇到换行符（\n）为止，将这行文本存入字符串 s 中，同时丢弃换行符
string s;
while (true)
{
    getline(cin, s);
    if (s.empty())  // 遇到空行，表示词典输入完毕
    {
        break;
    }
    // ...
    int pos = s.find(' ');
    english = s.substr(0, pos);
    foreign = s.substr(pos + 1);
    mp[foreign] = english;
}

记录路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <vector>

vector<type> res,ans;
if (terminal())
{
    if (ans.size() == 0 && res.size() < ans.size())
    {
        ans = res;
    }
}
// ...
res.push_back(x);
dfs(x + 1);
//...
res.pop_back(x);

int main()
{
    for (int i : ans)
    {
        cout << i << endl;
    }
}