当前位置：首页 > article >正文

数据结构篇

article 2025/2/21 18:57:43

链表

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

单链表

请添加图片描述

双向链表

请添加图片描述

左移右移

请添加图片描述

栈

模拟栈

请添加图片描述

判断括号序列

请添加图片描述

队列

请添加图片描述

模拟队列

请添加图片描述

递归

请添加图片描述

集合和哈希

请添加图片描述

集合就是哈希表

哈希表的实现

请添加图片描述

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) {
        // 创建一个默认的 Multiset
        Multiset<String> ms1 = new Multiset<>();
        ms1.add("apple");
        ms1.add("banana");
        ms1.add("apple");

        // 创建一个带有自定义比较器的 Multiset
        Comparator<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)，比较逻辑被反转了，从而实现了降序排序。