数组模拟单链表
用数组模拟单链表,可以免去new占用的时间,加快算法执行速度。不过删除节点时会造成内存泄漏,但这一般是工程中考虑的问题,算法题跑时间就行了。
1 | // head 指向头节点, index 表示当前可用数组下标(只增) |
模拟栈和队列
栈只需要一个top指针,队列需要一个头指针一个尾指针。
1 | //*********************//栈 |
单调栈
给定一个数列,输出每个数左边离它最近的比它小的数,不存在输出-1.
1 | const int N = 1e5+10; |
堆(以小根堆为例)
定义:完全二叉树,且父节点小于等于左右子节点。
特性:左节点下标(2x),右节点下标(2x+1)。
操作:down(x) : x变大了,那么需要往下调整。up(x) :x变小了,需要往上调整。
建堆(O(n)做法)
从$n / 2$处,即倒数第2层开始,往跟节点遍历,对这些节点执行down操作。最后一层经历过上层的down操作一定是满足堆定义的。O(n) 证明如下:
倒数第二层有$ n / 4$个节点,则最多的操作的次数为:
1 | int heap[N], sz, m; |
并查集
朴素并查集
1 | // 并查集模板题,主要功能是合并两个集合、查找两个元素是否属于同一集合 |
维护数量的并查集
1 |
|
STL
- priority_queue与set的区别
其中优先队列是由堆实现的,适用于每次只取前面的数的情况。而set是由BST实现的,可以快速查询某个数是否在set中。
1 | ector, 变长数组,倍增的思想 |