数据结构篇

链表

用数组模拟链表，看该链表结构，有几个域则用几个数组分别存储
单链表是只知道下一个元素位置，双链表还知道上一个链表位置

单链表

双向链表

左移右移

栈

模拟栈

判断括号序列

队列

模拟队列

递归

集合和哈希

集合就是哈希表

哈希表的实现

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
在这里实现重复存储其实就是改变键值对里面值的数量，重复多少那么数量改为多少

单调栈

除了维护栈的后进先出，还要维护从栈顶到栈底的单调性

数的左右最值问题

维护的是下标序列，不是其数组中确切的值

• 因为维护的是下标序列，所以天然单调栈就满足是最左边
• 因为是单调栈，在后续判断中，当前元素称为新的栈顶，下面的数都比当前元素大，若当前元素比现在栈顶元素大，那么之前弹出的元素都要小于当前元素，所以弹出没有影响。
  
  

左右最值分为四种情况：左右只需要改变遍历顺序就可以，比其大或小则改变单调性即可

单调队列

滑动窗口最值问题

并查集

不相交集合的并问题

例题：连通块中点的数量

树状数组

单点修改，区间求和问题