Q1主动回忆难度 3
1/10
算法与数据结构 · 高级 05
记忆强度
算法与数据结构高级题库第 5 组，共 10 张卡片。
算法与数据结构 · 高级 05
红黑树是一种带颜色约束的二叉查找树。
朴素字符串匹配会把模式串与文本的每个可能起点对齐，并从左向右逐字符比较。
最小生成树针对连通、无向、带权图：需要选择 V-1 条边连接全部顶点，使总权重最小且不存在环。
BM 算法用于在主串中查找模式串，它与朴素匹配最大的区别是：每次把模式串与主串的某个窗口对齐后，从模式串末尾向前比较。
Dijkstra 算法用于求带权图中从一个源点到其他顶点的最短路径，核心前提是所有可达边的权重非负。
最短路径问题是在图中寻找从起点到其他顶点或指定终点的最小总代价路径。
莱文斯坦距离衡量把字符串 source 转换为字符串 target 所需的最少单字符编辑次数，允许的基本操作通常是插入、删除和替换，并令每次操作成本为一。
基于比较的排序只能通过元素之间的大于、小于或相等关系获取顺序信息，其一般模型下的最坏时间复杂度下界是 O(n log n)。
AC 自动机是面向多模式串匹配的数据结构，可以理解为在 Trie 树上补充失配转移。
最直接的分片方法是计算 hash(key) % nodeCount，再把数据交给对应编号的节点。