主页 · 11

空间换时间 时间复杂度O（n log n）sort排序

定义：在有向图中，顶点表示活动，有向边表示活动Vi必须先于活动Vj进行 特性：必须是有向无环图

定义：图中的边有方向性，用箭头表示。 表示：边 (A, B) 与 (B, A) 是两条不同的边。

定义：快速插入和查询字符串的数据结构 特点：利用字符串的公告前缀，将字符串组成树形结构 优势：相比map，可以高效查找公共前缀

问题一分为二 —递归(DFS)-合并答案 时间优化：O(nn)-O(n log n)

思路 猜一个排序依据（比如按重量、按 deadline、按权值差等） 任取相邻两项 i, j 假设顺序错了，写出交换前/后只与这两头有关的代价/收益表达式 令“交换后更优”得不等式，化简成key(i) key(j)这个 key 就是 so…

解集具“二段性”即可用：前一段不满足，后一段一定满足，或反之

核心思想 right 一直往右走（不回退） left 只在“窗口非法”时被迫右移（也不回退） 时间优化：两层for-一层while; 模板（最长合法窗口）

rbtree的泛型设计：通过第二个模板参数Value决定红黑树节点中存储的数据类型 set实例化rbtree时：Value = Key map实例化rbtree时：Value = pair

栈（Stack） 存储非静态局部变量、函数参数、返回值 向下增长（从高地址向低地址） 自动分配和释放 堆（Heap） 动态内存分配区域 向上增长（从低地址向高地址） 手动管理（malloc/free, new/delete） 数据段/静态…