1.排序快速排序（AcWing785）主要思想：基于分治思想 l是待排序区间的左边界，r是右边界 确定分界点x，可以取左边界的值q[l]，或右边界的值q[r]，或者中间位置的值q[(l + r)/2] 根据基准值，调整区间，使得左半边区间的值全都...

2. 二分查找整数二分二分的本质不是单调性，有单调性一定可以二分，可以二分不一定有单调性 二分的本质是边界，假设给定一个区间，如果能够根据某个条件，将区间划分为左右两部分，使得左半边满足这个条件，右半边不满足这个条件（或者反之）。就可以用二分来查找左...

3.高精度主要有四种情况： A + B：两个大整数相加 A - B：两个大整数相减 A × b：一个大整数乘一个小整数 A ÷ b：一个大整数除以一个小整数 大整数的存储（加减乘除）：C++和C中不支持直接存储大整数，需要自己定义用数组存储，数字...

7.离散化主要思想： 有的数组，其元素的值域很大，比如数组中的元素范围很大，下标范围为[-10^9, 10^9]，但元素的个数很少，比如只有1000个元素。 有时（例如计数排序的思想），我们需要将元素的值，作为数组的下标来操作。此时不可能开一个2*1...

8.区间合并主要思想：给定很多个区间，若2个区间有交集，将二者合并成一个区间 先按照区间的左端点进行排序 然后遍历每个区间，根据不同情况进行合并，对于两个区间（后一个区间为i）可能有下面几种关系： 对于第一种情况，区间不变 对于第二种情况，e...

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

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

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

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

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