瓜瓜头条

算法竞赛：初级算法（第一章：基础数据结构）

2024-01-19 00:43 由 嗷呜ニャー～ 发表于 #其他

第一章：基础数据结构

1、链表

  • 动态链表

    • 动态链表需要临时分配链表节点，使用完毕后释放。

    • 优点：能及时释放空间，不使用多余内存

    • 缺点：需要管理空间，容易出错（竞赛一般不用动态链表）

    • #include<iostream>
using namespace std;

// n 个人围成一圈，从第一个人开始报数,数到m 的人出列，再由下一个人重新从1 开始报数，
// 数到m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

// 用动态链表实现

// 结构
struct Node {
    int data;       // 存储编号
    Node* next;     // 指向下一个节点的指针
};
typedef Node* pN;   // 定义指向Node的指针类型为pN

int main() {
    int n, m;
    cin >> n >> m;

    // 建立循环链表
    pN head = new Node; // 创建头节点
    head->data = 1;
    head->next = nullptr;
    pN pCurrent = head; // 当前节点指针

    // 依次创建节点，构建循环链表
    for (int i = 2; i <= n; i++) {
        pN p = new Node;
        p->data = i;
        p->next = nullptr;
        pCurrent->next = p;
        pCurrent = p;
    }

    pCurrent->next = head; // 将链表闭合成循环

    // 循环计数、出列
    int k = 1;
    while (pCurrent != pCurrent->next) {
        if (k == m) {
            pN p = pCurrent->next;
            cout << p->data << " "; // 输出出列人的编号
            pCurrent->next = p->next;
            delete p; // 释放出列人的节点
            k = 1;
        } else {
            k++;
            pCurrent = pCurrent->next;
        }
    }
    cout << pCurrent->data; // 输出最后一个出列人的编号
    delete pCurrent; // 释放最后一个节点

    return 0;
}

  • 静态链表

    • 静态链表使用预先分配的一段连续空间存储链表，这种链表在逻辑上是成立的。

    • 有两种做法：

      • 定义链表结构体数组，和动态链表差不多。
      • 使用一维数组，直接在静态数组上实现。

    • 用结构体数组实现单向静态链表

      #include<iostream>
using namespace std;

// n 个人围成一圈，从第一个人开始报数,数到m 的人出列，再由下一个人重新从1 开始报数，
// 数到m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

const int N = 105;

// 结构体定义
struct Node {
    int id;        // 编号
    int nextid;    // 下一个节点的编号
} nodes[N];

int main() {
    int n, m;
    cin >> n >> m;

    // 初始化单向静态链表
    for (int i = 0; i < n - 1; i++) {
        nodes[i].id = i + 1;
        nodes[i].nextid = i + 1;
    }
    nodes[n - 1].id = n;
    nodes[n - 1].nextid = 0;

    int i = n - 1;
    int k = 1;

    // 循环计数、出列
    while (nodes[i].nextid != i) {
        if (k == m) {
            int j = nodes[i].nextid;
            nodes[i].nextid = nodes[j].nextid;
            cout << nodes[j].id << " "; // 输出出列人的编号
            k = 1;
        } else {
            k++;
            i = nodes[i].nextid;
        }
    }

    cout << nodes[i].id; // 输出最后一个出列人的编号
    return 0;
}

    • 用一维数组实现单向静态链表

      #include<iostream>
using namespace std;

// n 个人围成一圈，从第一个人开始报数,数到m 的人出列，再由下一个人重新从1 开始报数，
// 数到m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

// 用一维数组实现单向静态链表
// 定义一个 nodes[] 数组，nodes[i] 中的 i 就是结点的值，nodes[i] 里的数就是下一个节点
int nodes[150];

int main() {
    int n, m;
    cin >> n >> m;

    // 初始化单向静态链表
    for (int i = 1; i < n; i++) {
        nodes[i] = i + 1;
    }
    nodes[n] = 1;

    int now = n, prev = 1;

    // 循环计数、出列
    while (nodes[now] != now) {
        if (prev == m) {
            cout << nodes[now] << " "; // 输出出列人的编号
            nodes[now] = nodes[nodes[now]]; // 跳过当前出列的节点
        } else {
            prev++;
            now = nodes[now];
        }
    }

    return 0;
}

  • STL list

    • 在算法竞赛或工程项目中经常使用C++STL list。它是双向链表，由标准模板库管理。通过迭代器访问节点数据，高效的删除和插入。

    • list的一些重要函数：

      • list容器的创建：假设是int型
        • 创建空容器：std::list<int> values;
        • 创建包含n个元素的容器：std::list<int> values(10);
        • 创建包含n个元素，并都赋初值的容器：std::list<int> values(10, 5);
        • 拷贝已有list容器：std::list<int> values2(values1);
      • 返回指向容器中第一个元素的双向迭代器：values.begin();
      • 返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器：values.end();
      • 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false：values.empty();
      • 返回当前容器实际包含的元素个数：values.size();
      • 返回第一个元素的引用：values.front();
      • 返回最后一个元素的引用：values.back();
      • 在容器头部或尾部插入一个元素：values.push_front(); values.push_back();
      • 删除容器头部或尾部的一个元素：vlaues.pop_front(); values.pop_back();
      • 在容器中的指定位置插入元素：vlaues.insert();
      • 删除容器中一个或某区域内的元素：vlaues.erase();
    • #include<iostream>
#include<list>
using namespace std;

// n 个人围成一圈，从第一个人开始报数,数到m 的人出列，再由下一个人重新从1 开始报数，
// 数到m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

// STL模板库list实现功能

int main() {
    int n, m;
    cin >> n >> m;

    // 使用STL模板库中的list作为链表
    list<int> node;

    // 初始化链表
    for (int i = 1; i <= n; i++) {
        node.push_back(i);
    }

    // 迭代器指向链表头部
    list<int>::iterator it = node.begin();

    // 循环直到链表中只剩一个元素
    while (node.size() > 1) {
        // 循环报数，找到第m个元素
        for (int i = 1; i < m; i++) {
            it++;
            // 如果迭代器达到链表末尾，将其置为链表头部
            if (it == node.end())
                it = node.begin();
        }

        // 输出出列的人的编号
        cout << *it << " ";

        // 获取下一个元素的迭代器
        list<int>::iterator next = ++it;

        // 如果下一个迭代器达到链表末尾，将其置为链表头部
        if (next == node.end())
            next = node.begin();

        // 删除出列的人
        node.erase(--it);

        // 更新迭代器为下一个元素
        it = next;
    }

    // 输出最后剩下的人的编号
    cout << *it;

    return 0;
}

2、队列

​ 竞赛一般用STL queue或手写静态数组实现队列

  • STL queue

    • STL queue的主要操作：

      • 创建队列：queue<int> q;
      • 将item插入队列：q.push(item);
      • 返回队首元素：q.front();
      • 删除队首元素：q.pop();
      • 返回队尾元素：q.back();
      • 返回元素个数：q.size();
      • 检查队列是否为空：q.empty();
    • #include<iostream>
#include<queue>
using namespace std;

// 假设内存中有 M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M−1，
// 软件会将新单词存入一个未使用的内存单元；若内存中已存入 M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
// 假设一篇英语文章的长度为 N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

// 使用哈希表和队列存单词，查单词用哈希表查，用队列腾出单元

int Hash[1000] = { 0 };

int main() {
    int m, n;
    cin >> m >> n;
    int cnt = 0;

    // 使用队列保存内存中的单词顺序
    queue<int> q;

    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;

        // 如果单词未在内存中，将其存入内存
        if (Hash[t] == 0) {
            cnt++;
            Hash[t] = 1;
            q.push(t);

            // 如果内存中单词数超过 M，腾出最早进入内存的单元
            if (q.size() > m) {
                Hash[q.front()] = 0;
                q.pop();
            }
        }
    }

    // 输出外存查找次数
    cout << cnt;

    return 0;
}

  • 手写循环队列

    • 下面是循环队列的手写模板，竞赛一般用静态分配空间

    • #include<iostream>
using namespace std;

// 假设内存中有 M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M−1，
// 软件会将新单词存入一个未使用的内存单元；若内存中已存入 M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
// 假设一篇英语文章的长度为 N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

// 使用哈希表和手写循环队列存单词，查单词用哈希表查，用队列腾出单元

const int N = 1000;
int Hash[N] = { 0 };

// 手写循环队列结构体
struct my_queue {
    int data[N];
    int head, rear;

    // 构造队列
    my_queue() : head(0), rear(0) {};

    // 返回队列长度
    int size() { return (rear - head + N) % N; }

    // 判空操作
    bool empty() {
        return size() == 0;
    }

    // 入队
    bool push(int e) {
        if ((rear + 1) % N == head)
            return false;
        data[rear] = e;
        rear = (rear + 1) % N;
        return true;
    }

    // 出队
    bool pop() {
        if (head == rear) {
            return false;
        }
        head = (head + 1) % N;
        return true;
    }

    // 返回队头元素
    int front() {
        return data[head];
    }
} q;

int main() {
    int m, n;
    cin >> m >> n;
    int cnt = 0;

    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        if (Hash[t] == 0) {
            cnt++;
            Hash[t] = 1;
            q.push(t);

            // 如果队列长度超过 M，腾出最早进入队列的元素
            if (q.size() > m) {
                Hash[q.front()] = 0;
                q.pop();
            }
        }
    }

    // 输出外存查找次数
    cout << cnt;

    return 0;
}

  • 双端队列和单调队列

    • 双端队列和单调队列的概念

      • 双端队列是具有队列和栈性质的数据结构，它能且只能在两端插入或删除
      • STL的双端队列deque的用法如下：
        • 创建双端队列：deque<int> dq;
        • 返回队头：dq.front();
        • 返回队尾：dq.back();
        • 删除队头：dq.pop_front();
        • 删除队尾：dq.pop_back();
        • 在队头添加一个元素e：dq.push_front(e);
        • 在队尾添加一个元素e：dq.push_back(e);
      • 单调队列是双端队列的经典应用，单调队列里的元素是单调有序的
      • 单调队列里的元素的顺序和原来在序列中的顺序是一致的；

    • 单调队列的应用：滑动窗口：

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

// 有一个长为 n 的序列 a，以及一个大小为 k 的窗口。窗口从左边开始向右滑动，
// 每次滑动一个单位，求每次滑动后窗口中的最大值和最小值。

// 如果每次移动窗口，都要检查 k 个数来计算最大值和最小值，那么它就要检查 O(nk) 次。
// 可以使用单调队列来优化移动窗口，每次移动窗口时，对应的单调队列就要丢弃和增加相应元素，并输出最大值和最小值（需要两个单调队列）。
// 优化后只需要检查 3n 次。

// 单调递增队列，保存元素下标
deque<int> maxDeque;
// 单调递减队列，保存元素下标
deque<int> minDeque;

// 主函数
int main() {
    // 输入序列长度和窗口大小
    int n, k;
    cin >> n >> k;
    
    // 输入序列
    int list[1000000];
    for (int i = 0; i < n; i++) {
        cin >> list[i];
    }

    int head = 0, rear = 0;

    // 处理单调递增队列
    for (; rear <= k - 1; rear++) {
        int t = list[rear];
        // 保持队列单调递增，丢弃比当前元素小的元素
        while (!maxDeque.empty() && list[maxDeque.back()] < t) {
            maxDeque.pop_back();
        }
        maxDeque.push_back(rear);  // 将当前元素下标加入队列
    }
    cout << list[maxDeque.front()] << " ";  // 输出当前窗口的最大值
    rear--;

    // 继续处理后续窗口
    while (rear != n - 1) {
        rear++;
        int t = list[rear];
        // 保持队列单调递增，丢弃比当前元素小的元素
        while (!maxDeque.empty() && list[maxDeque.back()] < t) {
            maxDeque.pop_back();
        }
        maxDeque.push_back(rear);  // 将当前元素下标加入队列
        // 检查队首元素是否仍在当前窗口内，不在则出队
        if (maxDeque.front() == head) {
            maxDeque.pop_front();
        }
        cout << list[maxDeque.front()] << " ";  // 输出当前窗口的最大值
        head++;
    }
    cout << endl;

    head = rear = 0;

    // 处理单调递减队列
    for (; rear <= k - 1; rear++) {
        int t = list[rear];
        // 保持队列单调递减，丢弃比当前元素大的元素
        while (!minDeque.empty() && list[minDeque.back()] > t) {
            minDeque.pop_back();
        }
        minDeque.push_back(rear);  // 将当前元素下标加入队列
    }
    cout << list[minDeque.front()] << " ";  // 输出当前窗口的最小值
    rear--;

    // 继续处理后续窗口
    while (rear != n - 1) {
        rear++;
        int t = list[rear];
        // 保持队列单调递减，丢弃比当前元素大的元素
        while (!minDeque.empty() && list[minDeque.back()] > t) {
            minDeque.pop_back();
        }
        minDeque.push_back(rear);  // 将当前元素下标加入队列
        // 检查队首元素是否仍在当前窗口内，不在则出队
        if (minDeque.front() == head) {
            minDeque.pop_front();
        }
        cout << list[minDeque.front()] << " ";  // 输出当前窗口的最小值
        head++;
    }

    return 0;
}

  • 优先队列

    • 优先队列由堆组成，有最小优先队列和最大优先队列，每个出队元素都是队内最小或最大值。
    • STL优先队列的操作：
      • 大顶堆的创建：priority_queue<int> max_pq;
      • 小顶堆的创建：priority_queue<int, vector<int>, greater<int>> min_pq;
      • 将元素插入到优先队列中：max_pq.push(item);
      • 弹出优先队列堆顶：max_pq.pop();
      • 返回优先队列堆顶元素：max_pq.top();
      • 返回优先队列中的元素个数：max_pq.size();
      • 检查优先队列是否为空：max_pq.empty();

3、栈

  • STL stack

    • 竞赛一般直接用STLstack，或这自己手写静态栈。

    • STL stack的有关操作：

      • 栈的创建：stack<int> s;
      • 将元素存入栈顶：s.push(item);
      • 返回栈顶元素：s.top(item);
      • 删除栈顶元素：s.pop(item);
      • 返回栈中元素个数：s.size();
      • 检查栈是否为空：s.empty();
    • #include<iostream>
#include<stack>
using namespace std;

// 反转字符串
// 使用 STL stack 来完成操作

int main() {
    stack<char> s;
    char c;

    // 从标准输入逐字符读取，直到遇到换行符
    c = getchar();
    while (c != '\n') {
        if (c == ' ' && !s.empty()) {
            // 如果遇到空格且栈非空，输出栈内字符，并加上空格
            while (!s.empty()) {
                char t;
                t = s.top();
                s.pop();
                cout << t;
            }
            cout << " ";
        }
        else {
            // 非空格字符入栈
            s.push(c);
        }
        // 继续读取下一个字符
        c = getchar();
    }

    // 处理最后一个单词
    if (!s.empty()) {
        while (!s.empty()) {
            char t;
            t = s.top();
            s.pop();
            cout << t;
        }
        cout << " ";
    }

    return 0;
}

  • 手写栈

    • 手写静态栈代码简单且节省空间

    • #include<iostream>
using namespace std;

//反转字符串

//使用STLstack来完成操作
const int N = 100100;
struct my_stack {
	char a[N];
	int t = 0;
	void push(char x) { a[++t] = x; }
	void pop() { t--; }
	char top() { return a[t]; }
	int empty() { return t == 0 ? 1 : 0; }
}s;
int main() {
	char c;
	c = getchar();
	while (c != '\n') {
		if (c == ' ' && !s.empty()) {
			while (!s.empty()) {
				char t;
				t = s.top();
				s.pop();
				cout << t;
			}
			cout << " ";
		}
		else {
			s.push(c);
		}
		c = getchar();
	}
	if (!s.empty()) {
		while (!s.empty()) {
			char t;
			t = s.top();
			s.pop();
			cout << t;
		}
		cout << " ";
	}
	return 0;
}

  • 单调栈

    • 单调栈中的元素是单调递增或单调递减的，比如递减栈从栈顶到栈底是从大到小排序的。

    • 单调栈的操作：比如递减栈，当一个元素入栈时，与栈顶比较，若比栈顶小，则入栈，若比栈顶大，这弹出栈顶，直到比栈顶元素小，则入栈。注意，每个数都会入栈。

    • #include<iostream>
#include<stack>
using namespace std;

// N(1 << N << 10^5)头奶牛站成一排，奶牛i的身高为Hi(1 <= Hi <= 1000000)。
// 现在，每头奶牛都在向右看齐。对于奶牛i，如果奶牛j满足i < j 且Hi < Hj，我们就说奶牛i仰望奶牛j。
// 求出每头奶牛离他最近的仰望对象

// 暴力解法：遍历序列，在每个奶牛的序列右边找到它的仰望对象，复杂度在所有奶牛都没有仰望对象的情况下是O(nlog2N)

// 单调栈优化：由于单调栈的特性是每个元素都入栈，且栈内元素都是单调性的，所有可以用它来优化暴力
// 从后往前遍历序列，每次将元素压入单调栈时，栈顶元素就是该元素的仰望对象，栈空返回0，复杂度是O(n)

int a[100001]; // 存储奶牛的身高
int b[100001]; // 存储每头奶牛的仰望对象

int main() {
    int n;
    cin >> n;

    // 输入每头奶牛的身高
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        a[i] = t;
    }

    stack<int> s; // 单调栈，用于存储奶牛的序号

    // 从后往前遍历奶牛序列，求解每头奶牛的仰望对象
    for (int i = n; i >= 1; i--) {
        // 单调栈维护单调递减的序号
        while (!s.empty() && a[s.top()] <= a[i]) {
            s.pop();
        }

        // 如果栈为空，表示没有比当前奶牛更高的奶牛，仰望对象为0
        if (s.empty()) {
            b[i] = 0;
            s.push(i);
        } else {
            // 栈顶元素即为当前奶牛的仰望对象
            b[i] = s.top();
            s.push(i);
        }
    }

    // 输出每头奶牛的仰望对象
    for (int i = 1; i <= n; i++) {
        cout << b[i] << " ";
    }

    return 0;
}

4、二叉树和哈夫曼树

  • 二叉树的存储结构

    • 动态二叉树

      • struct Node{
    int value;	//节点的值
    node* lson, *rson;	//指向左右孩子的指针
};

      • 动态新建一个Node时，需要手动分配内存，使用完毕后，还要释放它，以防内存泄漏。

      • 动态二叉树的优点是不浪费空间，缺点是需要管理，容易出错。

    • 静态二叉树

      • struct Node{
    char value;		//节点的值
    int lson, rson;	//左右孩子的坐标
}tree[N];

      • 由于静态二叉树编码简单，在算法竞赛中一般使用静态二叉树。

      • 编码时一般不用tree[0]，因为0被用来表示空节点，当一个节点的左右子树为空时就可以表示为lson = rson = 0;

      • 特别的，当用数组实现完全二叉树时，可以不用定义lson,rson。一颗节点总数为k的完全二叉树，设一号节点为根节点，有以下性质：

        • 编号i > 1的节点，其父结点编号是i / 2。
        • 如果2i > k，说明节点 i 没有孩子；如果2i + 1 > k, 那么节点 i 没有右孩子。
        • 如果节点 i 有孩子，那么它的左孩子是2i，它的右孩子是2i + 1。

    • 多叉树转化为二叉树

      • 将多叉树的第一个孩子作为右孩子，将其兄弟孩子作为右孩子。

  • 哈夫曼编码以及哈夫曼树

    • 哈夫曼编码是一种用于数据压缩的算法，该编码算法基于一种称为哈夫曼树的数据结构，通过根据输入文本中字符的出现频率构建一棵二叉树，并将频率较高的字符用较短的二进制码表示，频率较低的字符用较长的二进制码表示，以实现对数据的高效压缩。

    • 哈夫曼编码的主要步骤如下：

      • 统计输入文本中每个字符的出现频率。

      • 将每个字符及其频率构建为一个包含单节点的二叉树。

      • 将这些二叉树合并为一棵哈夫曼树，合并过程中频率较低的树作为新树的左子树，频率较高的树作为右子树。

      • 在哈夫曼树的叶子节点上的每个字符都被赋予一个唯一的二进制编码，路径的左分支表示0，右分支表示1。

      • 使用得到的编码对输入文本中的每个字符进行替换，生成压缩后的二进制数据。

    • 由于哈夫曼编码的构建过程保证了没有编码是另一个编码的前缀，所以在解码时不会出现歧义。哈夫曼编码在信息论和数据压缩领域有广泛应用，例如在无损压缩算法中，以及在通信领域中的数据传输和存储中。

    • 哈夫曼树的性质：

      • 哈夫曼树的所有叶子节点相加就是字符串长度
      • 哈夫曼树的所有非叶子节点相加就是字符串的哈夫曼编码长度
    • #include<iostream>
#include<queue>
#include<string>
using namespace std;

// 输入一个字符串，分别用普通ASCII编码（每个字符8bit）和哈夫曼编码
// 输出编码前后的长度，并输出压缩比

// 本题的核心问题是求字符串的哈夫曼编码长度
// 在哈弗曼树中，所有非叶子节点相加即为字符串的哈夫曼编码长度
// 题目没有要求输出哈夫曼编码，因此不必真的构造哈夫曼树
// 只需要一个变量，初始值为0，每次将两个最小频率的字符的频率之和加到变量中
// 直到所有字符都加完，最后的变量值就是字符串的哈夫曼编码长度

// 计算字符串中每个字符的频率
// 将字符串存入字符数组中，对数组进行排序
// 从前往后读字符，读到相同的字符频率加一，直到读到不同的字符结束
// 此时的频率就是字符的频率

// 哈夫曼编码长度的计算
// 构造一个小顶堆优先队列（可以直接使用STL优先队列）
// 每次计算完一个频率就放入优先队列，直到处理完所有字符
// 设定一个变量，初始值为0
// 每次出队两个频率，将这两个频率相加再放入队列
// 令变量等于频率之和加上这个变量，直到优先队列为空
// 此变量就是哈夫曼长度

int main() {
    priority_queue<int, vector<int>, greater<int>> q; // 小顶堆优先队列，用于构建哈夫曼编码
    string s;
    cin >> s;
    
    while (s != "END") {
        sort(s.begin(), s.end()); // 将字符串排序以便统计字符频率

        int num = 1;
        // 统计字符频率
        for (int i = 1; i <= s.size(); i++) {
            if (s[i] != s[i - 1]) {
                q.push(num);
                num = 1;
            } else {
                num++;
            }
        }

        int ans = 0;
        // 计算哈夫曼编码长度
        while (q.size() != 1) {
            int a = q.top();
            q.pop();
            a = a + q.top();
            q.pop();
            q.push(a);
            ans += a;
        }
        q.pop();

        // 输出编码前后的长度和压缩比
        cout << "Original Length: " << s.size() * 8 << " bits, Huffman Length: " << ans
             << " bits, Compression Ratio: " << (double)s.size() * 8 / (double)ans << endl;

        cin >> s; // 读取下一个字符串
    }

    return 0;
}

热门相关：官策   官策   随身英雄杀   官策   大明武夫