网站版块策划谷歌搜索引擎在线
链表
用数组模拟链表，看该链表结构，有几个域则用几个数组分别存储
单链表是只知道下一个元素位置，双链表还知道上一个链表位置
单链表
双向链表
左移右移
栈
模拟栈
判断括号序列
队列
模拟队列
递归
集合和哈希
集合就是哈希表
哈希表的实现
N要设置为其数据的2倍多一些， 取模大于那个数就可以了。
q<=10的五次方，所以取模mod大于这个数就可以了，N数组设为其2倍多10.
记住
哈希表解决查询x是否在集合中出现过以及插入。选择合适的方法插入。
Java提供的Set集合
Map哈希表（键值对，按键查找）
离散化
- 首先是有序，且不重复，所以使用TreeMap
- 它存入后就是自动排序
- 先把所有数读入放在a数组，再把a数组存入mp中，mp中的就是排好序的，而a是原数组。
- 因为mp中的是按自然顺序排好的，那么从头到尾遍历就是从小到大，此时让其数值和排名构成键值对
- 数值为键，最后将原数组顺序a的数值去mp中通过get方法获取对应值也就是排名替代原数组。
- 最后就是最终答案
优先队列
优先队列的使用
堆排序（很重要，一年一次）
最后要输出一个换行符
multiset实现优先队列
可排序有删除操作，那应该用这个，因为map中删除的复杂度为0（n)
这段代码定义了一个名为 Multiset 的类，该类使用 TreeMap 来实现一个多集合（multiset），其中元素可以重复。以下是代码的详细解释：
代码解释
声明变量:
TreeMap<T, Integer> multiset;
int len = 0;
TreeMap<T, Integer> multiset;: 声明一个 TreeMap 对象 multiset，键类型为 T（泛型类型），值类型为 Integer。这个 TreeMap 用于存储多集合中的元素及其出现次数。泛型类型根据传入的数据的类型来确定，没有严格的要求。
int len = 0;: 声明一个整型变量 len，初始化为 0，用于记录多集合中元素的总数。
无参构造函数:
Multiset() {multiset = new TreeMap<>();
}
这个构造函数创建一个新的 TreeMap 实例，并将其赋值给 multiset 变量。默认情况下，TreeMap 使用自然顺序对键进行排序。(默认是升序）
带比较器的构造函数:
Multiset(Comparator cmp) {multiset = new TreeMap<>(cmp);
}
这个构造函数接受一个 Comparator 对象 cmp 作为参数，并创建一个新的 TreeMap 实例，使用指定的比较器对键进行排序。
代码功能总结
多集合（Multiset）: 多集合是一种数据结构，允许元素重复出现，并且每个元素都有一个计数表示其出现次数。
使用 TreeMap: TreeMap 是一种有序映射，它保证了键的有序性，并且提供了高效的插入、删除和查找操作。
构造函数: 提供了两种构造函数，一种是默认构造函数，使用自然顺序对键进行排序；另一种是带比较器的构造函数，允许用户自定义键的排序方式。
示例用法
假设你有一个 Multiset 类，你可以这样使用它：
public class Main {public static void main(String[] args) {// 创建一个默认的 MultisetMultiset<String> ms1 = new Multiset<>();ms1.add("apple");ms1.add("banana");ms1.add("apple");// 创建一个带有自定义比较器的 MultisetComparator<String> cmp = (s1, s2) -> s2.compareTo(s1); // 逆序比较Multiset<String> ms2 = new Multiset<>(cmp);ms2.add("apple");ms2.add("banana");ms2.add("apple");System.out.println(ms1); // 输出：{apple=2, banana=1}System.out.println(ms2); // 输出：{banana=1, apple=2} （因为比较器是逆序的）}
}
通过这种方式，你可以根据需要创建不同类型的多集合，并控制元素的排序方式。
这段代码定义了一个Comparator类型的比较器，用于对字符串进行逆序排序（从Z到A）。让我们拆解一下这个表达式来理解它的含义：
Comparator<String> cmp = (s1, s2) -> s2.compareTo(s1);
语法解释
Comparator: 这是Java中的一个泛型接口，用于定义如何比较两个对象以便进行排序。在这里，它专门用于比较String类型的对象。
cmp: 这是你给这个特定的Comparator实例起的名字。
(s1, s2): 这部分定义了lambda表达式的参数列表。在本例中，有两个参数s1和s2，它们都是String类型的对象。Lambda表达式提供了一种简洁的方式来实现只有一个抽象方法的接口（在这种情况下，是Comparator接口的compare方法）。
->: Lambda表达式中的箭头符号，用来分隔参数列表和表达式体。
s2.compareTo(s1): 这是lambda表达式的主体部分，它定义了比较逻辑。这里使用了String类自带的compareTo方法来进行比较，但与常规的升序排列不同的是，这里是s2.compareTo(s1)而不是s1.compareTo(s2)，这就导致了降序排列的结果。
工作原理
通常情况下，String的compareTo方法按照字典顺序比较两个字符串，返回：
小于0的数：如果调用该方法的字符串小于参数字符串（按字典顺序）；
等于0的数：如果两个字符串相等；
大于0的数：如果调用该方法的字符串大于参数字符串。
在标准的升序排序中，你会直接使用s1.compareTo(s2)。然而，在这里，通过交换参数位置为s2.compareTo(s1)，比较逻辑被反转了，从而实现了降序排序。
Multiset的代码实现
getOrDefault表示若是有的话那么就返回该键对应的值，若是没有那么就返回0
在这里实现重复存储其实就是改变键值对里面值的数量，重复多少那么数量改为多少
单调栈
除了维护栈的后进先出，还要维护从栈顶到栈底的单调性
数的左右最值问题
维护的是下标序列，不是其数组中确切的值
- 因为维护的是下标序列，所以天然单调栈就满足是最左边
- 因为是单调栈，在后续判断中，当前元素称为新的栈顶，下面的数都比当前元素大，若当前元素比现在栈顶元素大，那么之前弹出的元素都要小于当前元素，所以弹出没有影响。
左右最值分为四种情况：左右只需要改变遍历顺序就可以，比其大或小则改变单调性即可
单调队列
滑动窗口最值问题
并查集
不相交集合的并问题
例题：连通块中点的数量
树状数组
单点修改，区间求和问题
