公司网站的制作公司,双语网站建设网站,汕尾海丰建设规划局网站,wordpress 注册验证码链表 用数组模拟链表#xff0c;看该链表结构#xff0c;有几个域则用几个数组分别存储 单链表是只知道下一个元素位置#xff0c;双链表还知道上一个链表位置 单链表 双向链表 左移右移 栈
模拟栈 判断括号序列 队列 模拟队列 递归 集合和哈希 集合就是哈希表 哈希表的实现…链表 用数组模拟链表看该链表结构有几个域则用几个数组分别存储 单链表是只知道下一个元素位置双链表还知道上一个链表位置 单链表 双向链表 左移右移 栈
模拟栈 判断括号序列 队列 模拟队列 递归 集合和哈希 集合就是哈希表 哈希表的实现 N要设置为其数据的2倍多一些 取模大于那个数就可以了。 q10的五次方所以取模mod大于这个数就可以了N数组设为其2倍多10. 记住 哈希表解决查询x是否在集合中出现过以及插入。选择合适的方法插入。 Java提供的Set集合 Map哈希表键值对按键查找 离散化 首先是有序且不重复所以使用TreeMap它存入后就是自动排序先把所有数读入放在a数组再把a数组存入mp中mp中的就是排好序的而a是原数组。因为mp中的是按自然顺序排好的那么从头到尾遍历就是从小到大此时让其数值和排名构成键值对数值为键最后将原数组顺序a的数值去mp中通过get方法获取对应值也就是排名替代原数组。最后就是最终答案
优先队列
优先队列的使用 堆排序很重要一年一次 最后要输出一个换行符
multiset实现优先队列
可排序有删除操作那应该用这个因为map中删除的复杂度为0n) 这段代码定义了一个名为 Multiset 的类该类使用 TreeMap 来实现一个多集合multiset其中元素可以重复。以下是代码的详细解释
代码解释 声明变量:
TreeMapT, Integer multiset;
int len 0;TreeMapT, 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) {// 创建一个默认的 MultisetMultisetString ms1 new Multiset();ms1.add(apple);ms1.add(banana);ms1.add(apple);// 创建一个带有自定义比较器的 MultisetComparatorString cmp (s1, s2) - s2.compareTo(s1); // 逆序比较MultisetString ms2 new Multiset(cmp);ms2.add(apple);ms2.add(banana);ms2.add(apple);System.out.println(ms1); // 输出{apple2, banana1}System.out.println(ms2); // 输出{banana1, apple2} 因为比较器是逆序的}
}通过这种方式你可以根据需要创建不同类型的多集合并控制元素的排序方式。
这段代码定义了一个Comparator类型的比较器用于对字符串进行逆序排序从Z到A。让我们拆解一下这个表达式来理解它的含义
ComparatorString 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 在这里实现重复存储其实就是改变键值对里面值的数量重复多少那么数量改为多少
单调栈
除了维护栈的后进先出还要维护从栈顶到栈底的单调性
数的左右最值问题 维护的是下标序列不是其数组中确切的值
因为维护的是下标序列所以天然单调栈就满足是最左边因为是单调栈在后续判断中当前元素称为新的栈顶下面的数都比当前元素大若当前元素比现在栈顶元素大那么之前弹出的元素都要小于当前元素所以弹出没有影响。 左右最值分为四种情况左右只需要改变遍历顺序就可以比其大或小则改变单调性即可 单调队列
滑动窗口最值问题 并查集
不相交集合的并问题 例题连通块中点的数量 树状数组
单点修改区间求和问题
