Bo2SS

掌舵：还用说？ 传送门 高级数据结构 二叉排序树、AVL 树 红黑树 哈夫曼树与哈夫曼编码 字符串匹配算法（上）：BF、KMP、SUNDAY、SHIFT-AND、Hash 字符串匹配算法（下）：Trie、AC、DAT 面试笔试算法下 从递推到动态规划（上） 从递推到动态规…

多模匹配问题，与字符串匹配相关的数据结构 多模匹配问题 有多个模式串的匹配问题，常规思路如下： Step1：多个模式串，建立成一棵字典树 Step2：和文本串的每一位对齐匹配，模拟暴力匹配的过程 Trie 又名字典树、单词查找树，顾名思作用 看图理解 思考树…

掌舵：光哥 传送门 从递推到动态规划（上） 从递推到动态规划（下） 单调队列与单调栈 线段树 树状数组 树状数组、线段树练习题 有问题多多指点！

一些经典、绝伦的单模匹配相关算法 相关定义 单模匹配问题：在文本串 $s$ 中查找某个模式串 $t$ 是否出现过 多模匹配问题：查找多个模式串 $t$ 文本串 / 母串：被查找串 $s$ 模式串：待查找串 $t$ 文本串长度为 $m$，模式串长度为 $n$ 暴力匹配法 所…

线段树知识请跳转：《面试笔试算法下》——4 线段树 树状数组知识请跳转：《面试笔试算法下》——5 树状数组 Lost_cows 样例输入 Copy 5 1 2 1 0 样例输出 Copy 2 4 5 3 1 思路 【问题 1】得到的答案是否唯一❓√ 从后往前，反着来观察…

前缀和数组与差分数组 【假设】原数组 $a$：$a_i,\ i\in [0,\ n]$，注意 $a_0=0$[否则差分数组的前缀和不等于原数组] 【可得】 前缀和数组 $S$：$S_i = \sum_{k=0}^{i}{a_i}$，易得 $a_i = S_i - S…

问题引入 $RMQ (x, y)$ 函数：查询数组 $[x, y]$ 区间内部的最小值，参考RMQ——OI Wiki 如果固定询问区间的尾部，例如：$RMQ (x,7)$ 最少记录如下 4 个蓝色元素，即可满足 $RMQ (x,7)$ 的所有需求 并且这 4…

三类优化方法 ① 状态转移过程的优化 不改变状态定义，使用一些特殊的数据结构或者算法专门优化转移过程 举例：扔鸡蛋 V2 ② 程序实现的优化 状态定义没变、转移过程也没有变 例如：0/1 背包问题，钱币问题 [滚动数组] ③ 状态定义的优化 大量训练才能培养出来的能力…

递推算法👉动态规划 递推 兔子繁殖问题 [引入] 题意理解：幼年兔子出生后，过一个月变成成年兔子，再过一个月生下一对幼年兔子 [即第三个月] 本月数量 f (n)= 本月成年 + 本月幼年 👇 本月成年 = 上个月成年 + 上个月幼年 =上个月数量 f (n…

[学习数据结构主要关注解决的是什么问题] 前置知识 解决的问题是什么？区间的修改与查询 [针对积性函数——Wiki] 问题背景 单点修改、区间查询（基础版） Modify (ind, val)：修改 ind 位置的值为 val Query (start, end…

直观了解哈夫曼树和哈夫曼编码，证明哈夫曼编码是最优的变长编码 前置知识 什么是编码 最先听到编码是在什么地方？ASCII 码 'a' = (97)10 = (0110 0001)2 '0' = (48)10 = (0011 0000)2 8 位二进制编码，一字节 注意…

掌舵：光哥 传送门 二叉排序树、AVL 树 红黑树 哈夫曼树与哈夫曼编码 字符串匹配算法（上）：BF、KMP、SUNDAY、SHIFT-AND、Hash 字符串匹配算法（下）：Trie、AC、DAT 有问题多多指点！

工程实现中应用非常广泛 <5 个平衡条件> 结点非黑即红 根结点是黑色 [头发] 叶结点 (NIL) 是黑色 [不洗脚] 通常不用画出来，也不用考虑 NIL 结点，默认是黑色 红色结点的两个子结点都是黑色⭐ 红色结点不能接红色结点 从根结点到所有叶结点的路径上…

数据结构，就是定义一种性质，并且维护这种性质 BS 树👉AVL 树 二叉排序树 [又叫二叉搜索树、二叉查找树] 基础知识 性质：对于任意一个三元组，左子树 < 根结点 < 右子树 用途：解决与查找、排名相关的检索需求 【为什么树形结构的查找入口一定是根结点？】 首先明白点…

掌舵：于船 传送门 顺序表与链表 栈与队列 树与二叉树 排序与查找 堆与优先队列 森林与并查集 有问题多多指点！

并查集：合并集合 [建立连通关系]、查找集合中的连通关系 [判断某两个点是否连通] 连通性问题 规则：已经具有连通关系的点不能重复连接 将所有点分成了 2 个集合：①、② [PS] 点与点的关系 (合并、判断连通)→也可以是→集合与集合的关系 Quic…

回顾 [完全二叉树] 完全二叉树默认从 1 开始编号 这样可以保证左孩子、右孩子编号简洁 [否则] 左孩子编号需为 2 * i + 1，右孩子编号需为 2 * i + 2 可编号的性质→可用顺序结构存储，而不需要保存下一个结点的地址 二叉树→数组的转换…

排序 四象限原则：稳定 / 非稳定、内部 / 外部 稳定：相同元素在排序前后的相对位置不变 内部：需要将数据整个加载到内存中进行排序 【考虑从小到大排序】 稳定排序 插入（内部） 前：已排序区；后：待排序区 后面的数在前面找位置插空 一个一个比较、交换，实现…