Quixon⌨️C++个人总结
type
status
date
slug
summary
tags
category
icon
password
第一部分 标准库
vector与array
vector与array两者都是用于存储数组型数据结构的一种容器，其关键区别就在于前者是动态存储的而后者是在定义的时候就预先分配好了的。
以下是
<vector> 中的一些常用成员函数：函数 | 说明 |
push_back(const T& val) | 在末尾添加元素 |
pop_back() | 删除末尾元素 |
at(size_t pos) | 返回指定位置的元素，带边界检查 |
operator[] | 返回指定位置的元素，不带边界检查 |
front() | 返回第一个元素 |
back() | 返回最后一个元素 |
size() | 返回当前元素数量 |
resize(size_t n) | 将元素数量调整为 n |
clear() | 清空所有元素 |
insert(iterator pos, val) | 在指定位置插入元素 |
erase(iterator pos) | 删除指定位置的元素 |
begin() / end() | 返回起始/结束迭代器 |
deque
deque是Double-ended queue的缩写，指双端队列的实现，允许在两端进行各类操作。
下面是 std::deque 容器的一些常用成员函数：
函数名称 | 功能描述 |
deque() | 默认构造函数，创建一个空的 deque 容器。 |
deque(size_type n) | 创建一个包含 n 个默认值元素的 deque 容器。 |
deque(size_type n, const T& value) | 创建一个包含 n 个值为 value 的 deque 容器。 |
deque(initializer_list<T> il) | 使用初始化列表 il 构造 deque 容器。 |
operator= | 赋值操作符，赋值给 deque 容器。 |
assign() | 用新值替换 deque 容器中的所有元素。 |
at(size_type pos) | 返回 pos 位置的元素，并进行范围检查。 |
operator[](size_type pos) | 返回 pos 位置的元素，不进行范围检查。 |
front() | 返回第一个元素的引用。 |
back() | 返回最后一个元素的引用。 |
begin() | 返回指向第一个元素的迭代器。 |
end() | 返回指向末尾元素后一位置的迭代器。 |
rbegin() | 返回指向最后一个元素的逆向迭代器。 |
rend() | 返回指向第一个元素之前位置的逆向迭代器。 |
empty() | 检查容器是否为空。 |
size() | 返回容器中的元素个数。 |
max_size() | 返回容器可容纳的最大元素个数。 |
clear() | 清除容器中的所有元素。 |
insert(iterator pos, const T& value) | 在 pos 位置插入 value 元素。 |
erase(iterator pos) | 移除 pos 位置的元素。 |
push_back(const T& value) | 在容器末尾添加 value 元素。 |
pop_back() | 移除容器末尾的元素。 |
push_front(const T& value) | 在容器前端添加 value 元素。 |
pop_front() | 移除容器前端的元素。 |
resize(size_type count) | 调整容器大小为 count，多出部分用默认值填充。 |
swap(deque& other) | 交换两个 deque 容器的内容。 |
get_allocator() | 返回一个用于构造双端队列的分配器对象的副本。 |
priority_queue
优先队列，用于常规的队列或者栈，每个元素都有一个自己的“优先级”，或者说“key”值；在优先队列中，优先级“最高”的值总是先被移除。
priority_queue的基本语法
常用操作
empty(): 检查队列是否为空。
size(): 返回队列中的元素数量。
top(): 返回队列顶部的元素（不删除它）。
push(): 向队列添加一个元素。
pop(): 移除队列顶部的元素。
底层实现
C++ 的
priority_queue 通常基于以下两个组件实现：- 底层容器：默认使用
vector，也可以使用deque
- 堆算法：使用
<algorithm>中的堆操作函数（make_heap,push_heap,pop_heap）
优先队列本质上是一个用vector存储的完全二叉树
第二部分 一些算法
数组排序算法
1. 冒泡排序 (Bubble Sort)
- 时间复杂度：O(n²) 最坏和平均情况，O(n) 最佳情况（已排序）
- 空间复杂度：O(1)
- 稳定排序
2. 选择排序 (Selection Sort)
- 时间复杂度：O(n²) 所有情况
- 空间复杂度：O(1)
- 不稳定排序
3. 插入排序 (Insertion Sort)
- 时间复杂度：O(n²) 最坏和平均情况，O(n) 最佳情况（已排序）
- 空间复杂度：O(1)
- 稳定排序
4. 希尔排序 (Shell Sort)
- 时间复杂度：取决于间隔序列，最佳O(n log n)，最坏O(n²)
- 空间复杂度：O(1)
- 不稳定排序
5. 归并排序 (Merge Sort)
- 时间复杂度：O(n log n) 所有情况
- 空间复杂度：O(n)
- 稳定排序
6. 快速排序 (Quick Sort)
- 时间复杂度：O(n log n) 平均情况，O(n²) 最坏情况（已排序）
- 空间复杂度：O(log n) 递归栈空间
- 不稳定排序
7. 堆排序 (Heap Sort)
- 时间复杂度：O(n log n) 所有情况
- 空间复杂度：O(1)
- 不稳定排序
8. 计数排序 (Counting Sort)
- 时间复杂度：O(n + k) 其中k是范围
- 空间复杂度：O(n + k)
- 稳定排序
9. 基数排序 (Radix Sort)
- 时间复杂度：O(d(n + k)) 其中d是位数，k是基数（通常10）
- 空间复杂度：O(n + k)
- 稳定排序
10. 桶排序 (Bucket Sort)
- 时间复杂度：O(n) 平均情况，O(n²) 最坏情况
- 空间复杂度：O(n + k)
- 稳定排序
总结表
排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最佳时间复杂度 | 空间复杂度 | 稳定性 |
冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
希尔排序 | O(n log n) | O(n²) | O(n log n) | O(1) | 不稳定 |
归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 |
堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 稳定 |
基数排序 | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 |
桶排序 | O(n + k) | O(n²) | O(n) | O(n + k) | 稳定 |
注：k表示输入的范围或桶的数量，d表示数字的位数。
链表排序算法
1. 冒泡排序 (Bubble Sort)
- 时间复杂度：O(n²) 最坏和平均情况，O(n) 最佳情况（已排序）
- 空间复杂度：O(1)
- 稳定排序
2. 选择排序 (Selection Sort)
- 时间复杂度：O(n²) 所有情况
- 空间复杂度：O(1)
- 不稳定排序
3. 插入排序 (Insertion Sort)
- 时间复杂度：O(n²) 最坏和平均情况，O(n) 最佳情况（已排序）
- 空间复杂度：O(1)
- 稳定排序
4. 归并排序 (Merge Sort)
- 时间复杂度：O(n log n) 所有情况
- 空间复杂度：O(log n) 递归栈空间
- 稳定排序
5. 快速排序 (Quick Sort)
- 时间复杂度：O(n log n) 平均情况，O(n²) 最坏情况（已排序）
- 空间复杂度：O(log n) 递归栈空间
- 不稳定排序
6. 计数排序 (Counting Sort)
- 时间复杂度：O(n + k) 其中k是范围
- 空间复杂度：O(n + k)
- 稳定排序
7. 基数排序 (Radix Sort)
- 时间复杂度：O(d(n + k)) 其中d是位数，k是基数（通常10）
- 空间复杂度：O(n + k)
- 稳定排序
链表排序总结表
排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最佳时间复杂度 | 空间复杂度 | 稳定性 |
冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
归并排序 | O(n log n) | O(n log n) | O(n log n) | O(log n) | 稳定 |
快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 |
计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 稳定 |
基数排序 | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 |
注意事项：
- 链表与数组排序的主要区别：
- 链表不支持随机访问，因此不能使用基于随机访问的算法（如堆排序、希尔排序）
- 链表插入/删除操作更高效，不需要移动大量元素
- 归并排序特别适合链表，因为不需要额外的空间来合并（数组归并需要O(n)空间）
- 推荐选择：
- 小规模数据：插入排序（实现简单且稳定）
- 大规模数据：归并排序（稳定且时间复杂度好）
- 特定场景：计数排序/基数排序（当数据范围有限时）
- 稳定性说明：
- 链表实现的选择排序通常是不稳定的，因为交换数据而非节点
- 如果通过重新链接节点而非交换数据来实现，某些算法可以变为稳定
Boyer-Moore 投票算法
来自力扣第 169 题：多数算法
给定一个长度为 n 的数组，保证非空，返回其中的多数元素，即出现次数大于 n/2 的元素。要求时间复杂度为 O(n)，空间复杂度为 O(1)。
线段树（Segment Tree）
用于处理区间查询和单点、区间更新
建树 O(n)，查询 O(log n)
并查集
用于高效管理动态连通性问题（合并集合、查询根节点）
时间复杂度为近似常数时间
技巧有路径压缩与按秩合并
第三部分 一些想法与技巧
树
对于树而言，最重要的思路就是递归，如何能将大的问题建模为不断通过小问题的递归来解决非常重要。可以先从最简单的情况想起，反向进行代码实际递归运行的过程。事实上问题基本都是对于树的左右子树分别递归来解决的，只要思考清楚左右子树的返回结果对于问题解决得影响。
例如力扣第236题，寻找给定的二叉树中两个节点的最近公共祖先，最简单的情况就是根节点为空或根节点恰好为给定的两个节点之一，这时，结果即为根节点。显然我们需要在一般情况下对于左右子树来进行递归，如果某一个子树中不存在给定的两个节点，这时公共祖先会存在于另一个子树中；如果两个子树中各存在一个给定的节点，则当前的根节点就是最近公共祖先。
动态规划
力扣第32题需要重做
动态规划的本质是避免重复计算，通过将复杂问题转化为重叠的子问题，并且通过记忆化、存储子问题的解来提升效率。
明确问题是否适用DP
- 重叠子问题：大问题能分解为多个重复出现的相同小问题（例如斐波那契数列）。
- 最优子结构：大问题的最优解由小问题的最优解组合而成（例如最短路径问题）。
- 无后效性：当前状态一旦确定，后续决策不受之前决策路径的影响。
其他注意事项
- 状态定义决定成败：多尝试不同角度（如结尾位置、区间长度）。
- 转移方程是核心逻辑：思考“当前状态如何由已知状态推导”。
- 画图辅助：用表格或DAG（有向无环图）表示状态依赖关系。
- 从暴力递归入手：先写递归再转化为DP（加记忆化）。
矩阵快速幂
在一个很基础的上楼梯的题目中，上 n 阶台阶的次数可以用一个矩阵的幂来表示：
我们只需要能够快速计算这里 的 n 次幂，就可以快速求得结果
cin 与 cout
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。
上一篇
关于本站
下一篇
Python学习（二）
Loading...