4.1k 字 4 分钟

记录一下慕课学习的笔记，以及例题代码 # 一。递归到动规的一般转化方法 递归函数有 n 个参数就定义一个 n 维的数组， 数组的下标是递归函数参数的取值范围。 这样就可以从边界值开始逐步填充数组，相当于计算递归函数值的逆过程。eg：例题 1 数字三角形 # 二。动规解题的一般思路 # 1. 将原问题分解为子问题 将原问题分解为若干个子问题，与原问题的形式相同或类似，只不过规模小了。 子问题都解决，原问题即解决。 子问题的解一旦求出就会被保存，所以每个子问题只要求解一次。 # 2....
6.8k 字 6 分钟

# 一、图 # 1. 什么是图 表示 “多对多” 的关系，包含了： 一组顶点：通常用 V (Vertex) 表示顶点集合 一组边：通常用 E (Edge) 表示边的集合 无向边是顶点对：(v，w) ∈ E，其中 v，w∈V 有向边 <v,w> 表示从 v 指向 w 的边 (单行线) 不考虑重边和自回路 # 抽象数据类型定义 类型名称：图 (Graph) 数据对象集：G (V,E) 由一个非空的有限顶点集合 V 和一个有限边集合 E 组成。 操作集：对于任意图 G ∈ Graph, 以及 v ∈ V，e ∈ E Graph Create ():...
3.9k 字 4 分钟

# 一、堆 # 1. 堆是什么 堆（Heap), 是一个可以被看做一棵完全二叉树的数组对象，有以下性质： 任意节点的值是其子树所有结点中的最大值 / 最小值（有序性） 堆总是一棵用数组表示的完全二叉树。 # 2. 最大堆的操作函数 定义 typedef struct HeapStruct *MaxHeap;struct HeapStruct { ElementType *Elements;// 存储堆元素的数组 int Size;// 当前元素个数 int Capacity;// 最大容量};# (1) 空最大堆的创建 (Create...
10k 字 9 分钟

上篇说到 RMQ 问题可以用 ST 表算法处理，但需要在线修改的时候，线段树是更好的选择。 如图，很明显线段树是个二叉搜索树 要注意的点如下： 线段树用数组存储，数组空间简单的就一般开到原数组的 4*n 倍（准确的说是将 n 向上扩充到 2 的幂次方然后乘 2，如 5->8->16） 线段树数组存储中，某个结点的编号为 n，则其左子结点编号为 2 n（表示成 n << 1）, 右子节点编号为 2n+1 (表示为 n << 1 | 1) 规定根节点为 1 #...
8.1k 字 7 分钟

# 一、二叉搜索树 # 1. 二叉搜索树是什么 二叉搜索树（BST，Binary Search Tree), 又称二叉排序树或二叉查找树，是一棵二叉树，可以为空，当不为空时满足以下性质： 非空左子树的所有键值小于其根结点的键值 非空右子树的所有键值大于其根结点的键值 左、右子树都为二叉搜索树 # 2. 二叉搜索树的操作函数 # (1) 二叉搜索树的查找操作 Find 要查找的值为 X 从根结点开始查找，若树为空，则返回 NULL 若搜索树非空，则将 X 与根节点的键值进行比较并进行以下处理 若 X 小于根结点键值，则在左子树中搜索 若 X 大于根结点键值，则在右子树中搜索 若 X...
1.5k 字 1 分钟

# ST 表是什么 ST 表是一个用来解决区间最值问题查询的算法 它用 O (nlogn) 复杂度预处理，可以实现 O (1) 复杂度的查询。 缺点：无法支持在线修改 模板题：ST 表 - 洛谷 # 1. 预处理 用一个二维数组 dp [i][j] 表示下标为 i ~ i + 2j - 1 的最值（最大 or 最小值） 则 ①易知边界条件 dp [i][0] 为 a [i]，既 i~i 的最大值为其本身 ②接下来是状态转移方程，如图 # 1 << j 相当于 2j 初始化代码 void init(int n) { for (int i = 0;...
3.3k 字 3 分钟

# 一、什么是树 # 1. 树的定义 树（Tree）：n（n≥0）个结点构成的有限集合。 当 n=0 时，称为空树； 对于任一棵非空树（n>0）, 它具备以下性质： 树中有一个称为 “根（Root）” 的特殊结点，用 r 表示。 其余结点可分为 m（m>0）个互不相交的有限集 T1，T2，……，Tm, 其中每个集合本身又是一棵树，称为原来树的 “子树（SubTree）”。 子树是不相交的 除了根结点外，每个结点有且仅有一个父结点； 一个 N 个结点的树有 N-1 条边。 # 2. 树的一些基本术语 1. 结点的度（Degree）： 结点拥有子结点的数量 2....
2.6k 字 2 分钟

# 一、队列的抽象数据类型描述 类型名：队列（Queue） 数据对象集：一个有 0 个或多个元素的有穷线性表 操作集：长度为 MaxSize 的堆栈 Q∈Queue, 队列元素 item∈ElementType 1. 生成长度为 MaxSize 的空队列 Queue CreatQueue (int MaxSize); 2. 判断队列 Q 是否已满 bool IsFullQ (Queue Q, int MaxSize); 3. 将数据元素 item 插入队列 Q 中 bool AddQ (Queue Q, ElementType item); 4. 判断队列 Q 是否已空 bool...
2.3k 字 2 分钟

# 一、堆栈的抽象数据类型描述 类型名：堆栈（Stack） 数据对象集：一个有 0 个或多个元素的有穷线性表 操作集：长度为 MaxSize 的堆栈 S∈Stack, 堆栈元素 item∈ElementType 1. 生成空堆栈，其最大长度为 MaxSize; Stack CreateStack(int MaxSize); 2. 判断堆栈 S 是否已满 int IsFull (Stack S, int MaxSize); 3. 将元素 item 压入堆栈 void Push (Stack S, ElementType item); 4. 判断堆栈 S 是否已空 int IsEmpty...
633 字 1 分钟

# 一、广义表 是线性表的推广 对于线性表而言，n 个元素都是基本的单元素 广义表中，这些元素不仅可以使单元素也可以是另一个广义表 > typedef struct GNode *GList; struct GNode {> int Tag; // 标志域：0 表示结点是单元素，1 表示结点是广义表> union { // 子表指针域 SubList 域单元素数据域 Data 复用，共用存储空间> ElementType Data;> GList SubList;> } URegion;>...