2.栈与队列1）数组模拟栈主要思想：先进后出，设置一个数组存储数据，一个栈顶指针指向栈顶（初始化为0） 注意：数据出栈，只是指针单纯前移，无需在意数组还存储数据造成浪费 AcWing 828.模拟栈12345678910111213141516171...

1.链表主要思想：使用数组实现链表（而不用结构体，结构体代码更长，后续图论也是基于数组实现），即静态链表。因为动态链表使用new申请空间需要较多的时间，而算法要求的是以较少的时间完成任务。 单链表，最主要用单链表写邻接表，用邻接表存储图或者树 双链...

3.KMP KMP算法主要用在字符串匹配上。 比如我们从字符串”acfacfgded”（需要在哪里找的字符串称为“文本串”）找其中是否包含字符串”acfg”（需要从文本串里找的字符串我们叫做“模式串”），我们一般会想到的解法是暴力求解，两层for循环...

4.Trie树（字典树）Trie树，又称字典树，是用来高效存储和查找字符串集合的一种数据结构查找时，可以高效的查找某个字符串是否在Trie树中出现过，并且可以查找出现了多少次 利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效...

6.堆堆的基本操作（以小根堆为例，大根堆相反） 插入一个数 求集合当中的最小值 删除最小值 删除任意一个元素 修改任意一个元素 基本结构是一颗完全二叉树。以小根堆为例，每个节点都要小于其左右两个子树种的所有节点，根节点即为集合中的最小值。 用数组...

5.并查集并查集结构能够支持快速进行如下的操作： 将两个集合合并 询问两个元素是否在一个集合当中 并查集可以在近乎O(1)的时间复杂度下，完成上述2个操作 并查集的基本原理：用树的形式来维护一个集合。用树的根节点来代表这个集合。对于树中的每个节点...

4.前缀和与差分1.一维前缀和一维前缀和：S[i]=a1+a2+a3+a4+…..+ai，要求a从a1开始，且S[0]=0 前缀和的作用：给定一组序列数据，可以计算任意第l个数到第r个数的和，S[r]-S[l-1]（这里就解释了...

5.双指针算法主要思想： 针对单一序列使用两个指针，如快速排序 针对不同的两个序列使用两个指针，如归并排序 双指针算法可以实现对暴力（朴素）算法的优化，使时间复杂度由O(n^2)优化到O(n)，要求序列有单调关系 代码模板 123456for(i...

6.位运算主要思想： 获取一个数的二进制的第k位：x>>k & 1，将x右移k位即第k位就移动到最低有效位，每次右移后的数与1做按位与运算，只会保留最低有效位即第k位的二进制数。如x=10111，x>>2，...

8.C++中的STL(标准模板库)（1）vector, 变长数组，倍增的思想 头文件 #include <vector> ​ size() 返回元素个数 ​ empty() 返回是否为空 ​ clear(...