Czar

1234567891011121314151617181920// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度求模式串的Next数组：for (int i = 2, j = 0; i <= m; i ++ ){ while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j ++ ; ne[i] = j;}// 匹配for (int i = 1, j = 0; i <= n; i ++ ){ while (j && s[i] != p[j + 1]) j = ne[j]; if (s[i] == p[j + 1]) j ++ ; if (j == m) { j = ne[j]; // 匹配成功后的逻辑 }}

数组模拟栈123456789101112131415161718public class Stack { final int N = 10010; int[] stk = new int[N]; int tt; //插入 stk[++tt] = x; //弹出 tt --; //判断栈是否为空 if (tt > 0) notempty; else isempty; //栈顶 stk[tt];} 单调栈常见模型：找出每个数左边离它最近的比它大/小的数 12345int tt = 0;for (int i = 0; i <= n; i++) { while (tt && check(stk[tt], i)) tt--; stk[++tt] = i;} 数组模拟队列123456789101112131415161718public class Queue { final int N = 10010; ...

用数组模拟单链表模拟最多的：邻接表（作用：存储图和树） 123456789101112131415161718192021222324252627282930public class Main { final int N = 10010; //head 表示头节点的下标 //idx 存储当前已经用到了那个点 //e[i] 表示节点i的值 //ne[i] 表示节点i的next指针是多少 int head, idx; int[] e = new int[N]; int[] ne = new int[N]; //初始化 public static void init() { head = -1; idx = 0; } //将x插入到头节点 public static void add_to_head(int x) { e[idx] = x, ne[idx] = head, head = idx++; } //将 ...

二叉树二叉树：在二叉树中，任意节点的度<=2 二叉树分类： 二叉查找树 平衡二叉树 红黑树 二叉查找树 每一个节点上最多有两个子节点 任意节点左子树上的值都小于当前节点 任意节点右子树上的值都大于当前节点 小的存左边，大的存右边，一样的不存 遍历方式： 前序遍历：当前节点，左子节点，右子节点 中序遍历：左子节点，当前节点，右子节点 后序遍历：左子节点，右子节点，当前节点 层序遍历：一层一层地去遍历 平衡二叉树任意节点左右字数高度差不超过1 旋转机制 左左 -> 右旋 左右 -> 局部左旋再右旋 右右 -> 左旋 右左 -> 局部右旋再左旋 红黑树添加节点的规则： 每一个节点是红色或黑色 根节点必须是黑色 叶节点（Nil）是黑色 两个红色节点不能相连 任意节点到所有后代叶节点的简单路径上，黑色节点数量相同 节点添加规律： 默认添加的节点是红色的 根 ​ 直接变成黑色 非根 父黑 不需要任何操作 父红 叔叔红 将父节点设置为黑，叔叔节点设置为黑 祖父节点设置为红 如果祖父节点是根，再变回红 如果祖父节点非根，再将祖父节点设 ...

List接口的实现类 ArrayList：动态数组实现，允许重复元素 LinkedList：双向链表实现，允许重复元素 Set接口的实现类 HashSet：基于哈希表实现，不允许重复元素 LinkedHashSet：基于哈希表和链表实现，不允许重复元素，保持插入顺序 TreeSet：基于红黑树实现，不允许重复元素，元素自动排序 CollectionCollection是单列集合的祖宗接口，它的功能是全部单列集合都可以继承使用的 collection方法 把给定的对象添加到当前集合中 1. 如果我们向List系列集合中添加数据，那么方法永远会返回true，因为List系列是允许元素重复 2.如果我们向Set系列集合中添加数据，那么方法会根据是否存在而返回true或false，因为Set系列是不允许元素重复的 12Collection<E> coll = new ArrayList<> ();coll.add(e); 清空集合中所有的元素 123Collection<E> coll = new ArrayList<> () ...

Java中的泛型（Generics）是一种支持泛型编程的工具，它允许程序员在编译时提供类型信息，从而提高代码的复用性和安全性。泛型的应用统一了数据类型，把运行时期的问题提前到了编译期间，避免了强制类型转换可能出现的异常，应为在编译阶段类型就能确定下来。 泛型中的细节 泛型中不能写基本数据类型(int,float,double,boolean,byte,char,short,long) 指定泛型的具体类型后，传递数据时，可以传入该类型和他的子类类型 如果不写泛型，类型默认是Object 泛型的种类 泛型类： 允许你定义一个类，该类可以操作任意类型的数据，而不需要在代码中使用具体的类型 123456789public class Box<T> { private T t; public void set(T t) { this.t = t; } public T get() { return t; }} 泛型接口： 允许你定义一个接口，该接口可以操作任意类型的数据 123public interface ...

区间合并12345678910111213141516171819private static int[][] merge(int[][] a) { if (a == null || a.length == 0 || a[0].length == 0) { return new int[0][2]; } Arrays.sort(a, Comparator.comparingInt(item -> item[0])); List<int[]> res = new ArrayList<>(); for (int[] arr : a) { int left = arr[0]; int right = arr[1]; if (res.size() == 0 || res.get(res.size() - 1)[1] < left) { res.add(new int[]{left, r ...

离散化123456789101112131415161718// 去重 + 排序 List<Integer> distinctSorterAlls = alls.stream().distinct().sorted().collect(Collectors.toList()); // 离散化映射，把离散化的下标映射到连续的数组下标 + 1for (int[] item : add) { int index = Collections.binarySearch(distinctSorterAlls, item[0]) + 1; a[index] += item[1]; } // 前缀和 for (int i = 0; i < distinctSorterAlls.size(); i++) { s[i + 1] = s[i] + a[i]; } // 离散化映射，把离散化的下标映射到连续的数组下标 + 1for (int[] item : query) { int l = Co ...