网站建设怎样创建链接,太原网站设计,营销推广的平台,北京国际建设集团网站基础数据结构 目录 • 线性结构 • 二叉堆 • 并查集 • 哈希表 • 应用举例 一、线性结构 基础知识 • 数组 • 带头结点的双链表 – He a d 结点 : 虚拟头结点 – Fir s t 结点 : 第一个有实际内容的结点 • 队列 : 循环队列与 Open-Close 表 例 1. 最… 基础数据结构 目录 • 线性结构 • 二叉堆 • 并查集 • 哈希表 • 应用举例 一、线性结构 基础知识 • 数组 • 带头结点的双链表 – He a d 结点 : 虚拟头结点 – Fir s t 结点 : 第一个有实际内容的结点 • 队列 : 循环队列与 Open-Close 表 例 1. 最小值 • 实现一个 n 个元素的线性表 A 。每次可以修 改其中一个元素也可以询问闭区间 [p, q] 中元素的最小值。 • 1n,m100000 分析 • 利用二级检索的思想 – 设块长为 L, 则一共有 n/L 个块 – 维护数组 B, 保存每个块的最小值 • Modify(x, y) – A[x] y O(1) – 重算 x 所在块的最小值 ( 更新 B) O(L) 9 10 11 12 13 14 15 16 8 7 6 5 4 3 1 2 13~16 9~12 5~8 1~4 Min 操作 • Min(a, b) – 把区间 [a, b] 分成若干部分 – 完整块 : 一共最多 n/L 个块 O(n/L) – 非完整块 : 首尾各最多 L-1 个元素 O(L) • 每次操作时间复杂度 : O(n/LL) – 设 LO(n 1/2 ) 则渐进时间复杂度为 O(n 1/2 ) √ √ √ √ √ √ 例 2. 最接近的值 • 给一个 n 个元素的线性表 A 对于每个数 A i 找到它之前的数中和它最接近的数。即 对于每个 i 计算 C i min{| A i - A j | | 1 j i } • 规定 C 1 0 。 分析 • 问题的关键 : 你只需要解决 离线 问题 – 在线问题 : 每输入一个 A i , 立刻输出 C i – 离线问题 : 在给出任何输出之前得到所有 A i • 预处理 : 用 O(nlogn) 时间给所有 A i 排序 – 很快就会学到了 ☺ • 主算法 – 根据从小到大的顺序构造双向链表 – 依次计算 C n , C n-1 , …, C 1 在线问题可能么 ? 主算法 • A{2, 6, 5, 10, 4, 7}, 依次计算 C 6 , C 5 , C 4 – 每次计算 C i 时 , 链表中恰好是 计算 C i 需要的元素 – 计算 C i 只需比较两个元素然后删除 A i O(1) 2 2 4 4 5 5 6 6 7 7 10 10 2 2 4 4 5 5 6 6 10 10 2 2 5 5 6 6 10 10 例 3. 移动窗口 • 有一个长度为 n 的数组还有一个长度为 kn 的窗口。窗口一开始在最左边的位 置能看到元素 1, 2, 3, …k 。每次把窗口往 右移动一个元素的位置直到窗口的右边 界到达数组的元素 n 。 分析 • 考虑最小值。假设窗口从左往右移动 • 保存 5 是不明智的 , 因为从 现在 开始一直到 5 离开窗口 , 5 始终被 4“ 压制 ” 永远都不可能 成为最小值。删除 5 不会影响 结果 • 启发 算最小值的 有用 元素形成一个递增 序列最小值就是队首元素 • 关键 窗口右移操作 … 4 5 3 … 2 分析 • 窗口右移 队首出队新元素入队然后 在队列中删除它前面比它大的元素 • 实现 – 用链表储存窗口内 有用 元素 – 则窗口右移的时间和删除元素的 总 次数成正比 • 元素被删除后不会再次被插入因此每个 元素最多被删除一次总次数为 O(n), 即 算法时间总复杂度为 O(n) … 4 12 11 9 7 5 3 3 … 例 4. 程序复杂度 • 给出一段程序计算它的时间复杂度。这段程序 只有三种语句 – OP x 执行一条时间耗费为 x 的指令。这里的 x 为不 超过 100 的正整数。 – LOOP x 与 END 配套中间的语句循环 x 次其中 x 可以为规模 n 也可以是不超过 100 的正整数。 – EN D 与 LOOP 配套循环终止。 • 注意 OP 语句的参数不能为变量 n 而 LOOP 语 句的参数可以为变量 n 但不允许有其他名字的变 量。这样整个程序的时间复杂度应为 n 的多项 式。你的任务就是计算并显示出这个多项式。 例 4. 程序复杂度 • 输出仅包含一行即时间复杂度的多项 式。这个多项式应该按通常的方式显示处 理即不要输出 0n 这样的项 n 项也不要输 出为 n^1 等等。 OP 1 LOOP n LOOP 10 LOOP n OP 7 END OP 1 END END 70n^210n1 分析 • 考虑特殊情况没有变量 n 只有常数的情况 • 两种思路 – 递归求解不直接附加开销大 / – 基于栈的扫描算法实现简单明了效率高 ☺ • 扫描过程基本想法 – LO O P x 和 OP x, 把语句入栈 – END, 不断从栈里弹出语句直到弹出 LOOP • 弹出过程中累加操作数 x 然后乘以循环次数 y • 把 OP x*y 压入栈中相当于用一条 OP 等效一个 LOOP 分析 • 栈扫描算法的直接推广 – 栈里的每个操作数不是数而是多项式 – 多项式加法多项式与整数的乘积 – 所有通过至少一个数据的同学都采用此法 • 问题 – 多项式如何表示 – 多项式操作的时间复杂度是怎样的 复杂性 • 大部分数据涉及到高精度整数运算 • 高精度运算的复杂性 – 写起来相对麻烦 – 时间复杂度 O(n 2 ) (nlogn is possible, but…) – 空间复杂度 • 实际情况所有使用了高精度运算的同学 在时间 “ 爆 ” 掉之前空间先 “ 爆 ” 掉 – 每个数 10000 位 , n 次数可达 10000 或更多 – 栈里面可以有 10000 个多项式 10 12 1T !!!!! 空间 … 空间 … 空间 … • 是否可以找到一个空间需求比较小的算 法 哪怕时间效率略一点都可以 • 输出文件已经不小了需要尽量少的保存 中间结果因此最好不要栈 – 只要有栈最坏情况中间结果的空间大小就是 输出大小乘以栈的最大深度而输出 … “ 把括号展开 ” • 先想办法去掉所有 LOOP/END • 借助 当前乘数 确定这次 OP 的 最终 效果 OP 1 LOOP n LOOP 10 LOOP n OP 7 END OP 1 END END OP 1 * 1 OP (n*10*n) * 7 OP (n*10) * 1 基本算法 • 设当前乘数为 m, 结果多项式为 ans – 初始化 m 1, ans 0 • 主循环一条一条语句处理 – 遇到 LOOP x m m * x – 遇到 END m m / x – 遇到 OP x, ans ans m * x • 数据结构设 m an b 则用数对 (a, b) 表示 m a 是高精度整数 b 是 int 类型 • 除了结果多项式 ans 和 a 其他空间可忽略 二、二叉堆 堆 • 堆 (heap) 经常被用来实现优先队列 (priority queue): 可以把元素加入到优先队列中 , 也 可以从队列中取出 优先级最高 的元素 – Insert(T, x): 把 x 加入优先队列中 – DeleteMin(T, x): 获取优先级最高的元素 x, 并 把它从优先队列中删除 堆的操作 • 除了实现优先队列 , 堆还有其他用途 , 因此 操作比优先队列多 – Getmin(T, x): 获得最小值 – Delete(T, x): 删除任意已知结点 – DecreaseKey(T, x, p): 把 x 的优先级降为 p – Build(T, x): 把数组 x 建立成最小堆 • 显然 , 用堆很容易实现优先队列 堆的定义 • 堆是一个完全二叉树 – 所有叶子在同一层或者两个连续层 – 最后一层的结点占据尽量左的位置 • 堆性质 – 为空 , 或者最小元素在根上 – 两棵子树也是堆 存储方式 • 最小堆的元素保存在 heap[1..hs] 内 – 根在 heap[1] – K 的左儿子是 2k, K 的右儿子是 2k1, – K 的父亲是 [k/2] 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 删除最小值元素 • 三步法 – 直接删除根 – 用最后一个元素代替根上元素 – 向下调整 13 13 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 向下调整 • 首先选取当前结点 p 的较大儿子 . 如果比 p 大 , 调整 停止 , 否则交换 p 和儿子 , 继续调整 13 13 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 2 2 13 13 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 void swim(int p){ int q p1, a heap[p]; while(q aheap[q]){ heap[p]heap[q]; pq; qp1; } heap[p] a; } 插入元素和向上调整 • 插入元素是先添加到末尾 , 再 向上调整 • 向上调整 : 比较当前结点 p 和父亲 , 如果父亲比 p 小停止 ; 否则交换父亲和 p, 继续调整 void sink(int p){ int qp1, a heap[p]; while(qhs){ if(qhsheap[q1]heap[q])q; if(heap[q]a) break; heap[p]heap[q]; pq; qp1; } heap[p] a; } 堆的建立 • 从 下往上逐层 向下调整 . 所有的叶子无需调整 , 因此从 hs/2 开始 . 可用数学归纳法证明循环变量 为 i 时 , 第 i1, i2, …n 均为最小堆的根 void insert(int a) { heap[hs]a; swim(hs); } int getmin() { int rheap[1]; heap[1]heap[hs--]; sink(1); return r; } int decreaseKey(int p, int a ) { heap[p]a; swim(p); } void build() { for(int ihs/2;i0;i--) sink(i); } 时间复杂度分析 • 向上调整 / 向下调整 – 每层是常数级别 , 共 logn 层 , 因此 O(logn) • 插入 / 删除 – 只调用一次向上或向下调整 , 因此都是 O(logn) • 建堆 – 高度为 h 的结点有 n/2 h1 个 , 总时间为 lo g l o g 1 0 0 ( ) 2 2 n n h h h h n h O h O n ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦ ⎛ ⎞ ⎡ ⎤ × ⎜ ⎟ ⎢ ⎥ ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ∑ ∑ 例 1. k 路归并问题 • 把 k 个有序表合并成一个有序表 . • 元素共有 n 个 . 分析 • 每个表的元素都是从左到右移入新表 • 把每个表的当前元素放入二叉堆中 , 每次删 除最小值并放入新表中 , 然后加入此序列的 下一个元素 • 每次操作需要 logk 时间 , 因此总共需要 nlogk 的时间 例 2. 序列和的前 n 小元素 • 给出两个长度为 n 的有序表 A 和 B, 在 A 和 B 中 各任取一个 , 可以得到 n 2 个和 . 求这些和最 小的 n 个 分析 • 可以把这些和看成 n 个有序表 : – A[1]B[1] A[1]B[2] A[1]B[3] … – A[2]B[1] A[2]B[2] A[2]B[3] … – … – A[n]B[1] A[n]B[2] A[n]B[3] … • 类似刚才的算法 , 每次 O(logn), 共取 n 次最 小元素 , 共 O(nlogn) 例 3. 轮廓线 • 每一个建筑物用一个三元组表示 (L, H, R), 表示 左边界 , 高度和右边界 • 轮廓线用 X, Y, X, Y… 这样的交替式表示 • 右图的轮廓线为 : (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0) • 给 N 个建筑求轮廓线 分析 • 算法一 : 用数组记录每一个元线段的高度 – 离散化 , 有 n 个元线段 – 每次插入可能影响 n 个元线段 , O(n), 共 O(n 2 ) – 从左到右扫描元线段高度 , 得轮廓线 • 算法二每个建筑的左右边界为事件点 – 把事件点排序 , 从左到右扫描 – 维护建筑物集合 , 事件点为线段的插入删除 – 需要求最高建筑物 , 用堆 , 共 O(nlogn) 例 4. 丑数 • 素因子都在集合 {2, 3, 5, 7} 的数称为 ugly number • 求第 n 大的丑数 分析 • 初始把 1 放入优先队列中 • 每次从优先队列中取出一个元素 k 把 2k, 3k, 5k, 7k 放入优先队列中 • 从 2 开始算取出的第 n 个元素就是第 n 大的 丑数 • 每取出一个数插入 4 个数因此任何堆里 的元素是 O(n) 的时间复杂度为 O(nlogn) 例 5. 赛车 • 有 n 辆赛车从各不相同的地方以各种的速度 ( 速度 0v i 100) 开始往右行驶不断有超车现象发生。 • 给出 n 辆赛车的描述位置 x i 速度 v i 赛车已 按照位置排序 x 1 x 2 …x n • 输出超车总数以及按时间顺序的前 m 个超车事件 V 3 V 4 V 1 V 2 X 2 X 3 X 4 X 1 分析 • 事件个数 O(n 2 ), 因此只能一个一个求 • 给定两辆车超越时刻预先可算出 • 第一次 超车 可能 在哪些辆车之间 – 维护所有车的前方相邻车和追上时刻 • 局部此时刻不一定是该车下个超车时刻 • 全局所有时刻的 最小值 就是下次真实超车时刻 • 维护超车以后有什么变化 – 相对顺序变化 … 改变三个车的前方相邻车 – 重新算追上时刻调整三个权 – 简单的处理方法删除三个再插入三个 例 6. 可怜的奶牛 • 农夫 John 有 n n ≤ 100 000 头奶牛可是由于 它们产的奶太少农夫对它们很不满意决定每 天把产奶最少的一头做成牛肉干吃掉。但还是有 一点舍不得 John 打算如果不止有一头奶牛产奶 最少当天就大发慈悲放过所有的牛。 • 由于 John 的奶牛产奶是周期性的 John 在一开始 就能可以了解所有牛的最终命运不过他的数学 很差所以请你帮帮忙算算最后有多少头奶牛 可以幸免于难。每头奶牛的产奶周期 T i 可能不 同但不会超过 10 。在每个周期中奶牛每天产 奶量不超过 200 。 分析 • 如果采用最笨的方法每次先求出每头牛的产奶 量再求最小值则每天的复杂度为 O(n) 总复 杂度为 O(Tn) 其中 T 是模拟的总天数。由于周期 不超过 10 如果有的牛永远也不会被吃掉那么 我们需要多模拟 2520 天 1 2 3 … 10 的最 小公倍数才能确定 • 周期同为 t 的奶牛在没有都被吃掉之前每天的最 小产奶量也是以 t 为周期的。因此如果把周期相同 的奶牛合并起来每天只需要比较 10 类奶牛中每 类牛的 最小产奶量就可以了每天的复杂度为 O(k) 其中 k 为最长周期 分析 • 假设周期为 6 的牛有 4 头每次只需要比较 k 组牛的 “ 代表 ” 就可以了每天模拟的时间复 杂度为 O ( k ) 。 项 目 第 6 n 1 天 第 6 n 2 天 第 6 n 3 天 第 6 n 4 天 第 6 n 5 天 第 6 n 6 天 牛 1 2 5 3 5 7 4 牛 2 3 1 6 7 5 4 牛 3 5 3 3 5 3 9 牛 4 4 4 3 8 8 2 合 并 结 果 2 牛 1 1 牛 2 3 多 5 多 3 牛 3 2 牛 4 分析 • 只要周期为 6 的牛都不被吃掉 这个表一直是有效 的 。但是在吃掉一头奶牛后我们需要修改这个 表使它仍然记录着每天的最小产奶量 – 方法一 : 重新计算时间 O(h) 其中 h 是该组的牛数 – 方法二 : 把 一个周期中每天 的最小产奶量组织成堆每 次删除操作的复杂度是 O(klogh) • 由于每头奶牛最多被吃掉一次因此用在维护 “ 最 小产奶量结构 ” 的总复杂度不超过 O(nklogn) 。每 天复杂度为 O(k) 总复杂度为 O(Tknklogn) 例 7. 黑匣子 • 我们使用黑匣子的一个简单模型。它能存 放一个整数序列和一个特别的变量 i 。在初 始时刻黑匣子为空且 i 等于 0 。这个黑匣子 执行一序列的命令。有两类命令 • AD D ( x ) 把元素 x 放入黑匣子 • GE T i 增 1 的同时输出黑匣子内所有整数 中第 i 小的数。牢记第 i 小的数是当黑匣子中 的元素以非降序排序后位于第 i 位的元素 例 7. 黑匣子 编 号 命 令 i 黑 匣 子 内 容 输 出 1 A D D ( 3 ) 0 3 2 G E T 1 3 3 3 A D D ( 1 ) 1 1, 3 4 G E T 2 1, 3 3 5 A D D ( - 4 ) 2 - 4, 1, 3 6 A D D ( 2 ) 2 - 4, 1, 2, 3 7 A D D ( 8 ) 2 - 4, 1, 2, 3, 8 8 A D D ( - 1 0 0 0 ) 2 - 1 0 0 0, - 4, 1, 2, 3, 8 9 G E T 3 - 1 0 0 0, - 4, 1 , 2, 3, 8 1 1 0 G E T 4 - 1 0 0 0, - 4, 1, 2 , 3, 8 2 1 1 A D D ( 2 ) 4 - 1 0 0 0, - 4, 1, 2, 2, 3, 8 分析 • 降序堆 H ≥ 和升序堆 H ≤ 如图放置 • H ≥ 根节点的值 H ≥ [1] 在堆 H ≥ 中最大 H ≤ 根节点的值 H ≤ [1] 在堆 H ≤ 中最小 , 并满足 – H ≥ [1] ≤ H ≤ [1] – siz e [ H ≥ ] i • ADD( x ): 比较 x 与 H ≥ [1] 若 x ≥ H ≥ [1] 则将 x 插入 H ≤ 否则从 H ≥ 中 取出 H ≥ [1] 插入 H ≤ 再将 x 插入 H ≥ • GE T: H ≤ [1] 就是待获取的对象。输 出 H ≤ [1] 同时从 H ≤ 中取出 H ≤ [1] 插入 H ≥ 以维护条件 (2) 三、并查集 并查集 • 并查集维护一些不相交集合 S{S 1 , S 2 , …, S r }, 每个集合 S r 都有一个特殊元素 rep[S i ], 称为集合代表 . 并查集支持三种操作 – Make-Set(x): 加入一个集合 {x} 到 S, 且 rep[{x}] x. 注意 , x 不能被包含在任何一个 S i 中 , 因为 S 里任何两个集合应是不相交的 – Union(x, y): 把 x 和 y 所在的两个不同集合合并 . 相当于从 S 中删除 S x 和 S y 并加入 S x US y – Find-Set(x): 返回 x 所在集合 S x 的代表 rep[S x ] 链结构 • 每个集合用双向链表表示 , rep[S i ] 在链表首部 • Make-Set(x): 显然是 O(1) 的 • Find-Set(x): 需要不断往左移 , 直到移动到首部 . 最坏情况下是 O(n) 的 • Union(x, y): 把 S y 接在 S x 的尾部 , 代表仍是 rep[S x ]. 为了查找链表尾部 , 需要 O(n) 增强型链结构 • 给每个结点增加一个指回 rep 的指针 • Make-Set(x): 仍为常数 • Find-Set(x): 降为常数 ( 直接读 rep) • Union(x, y): 变得复杂 : 需要把 S y 里所有元素的 rep 指针设为 rep[Sx]! 增强型链结构的合并 • 可以把 x 合并到 y 中也可以把 y 合并在 x 中 技巧 1: 小的合并到大的中 • 显然 , 把小的合并到大的中 , 这一次 Union 操 作会比较节省时间 , 更精确的分析 ? • 用 n, m, f 分别表示 Make-Set 的次数 , 总操作 次数和 Find-Set 的次数 , 则有 • 定理 : 所有 Union 的总时间为 O(nlogn) • 推论 : 所有时间为 O(m nlogn) • 证明 : 单独考虑每个元素 x, 设所在集合为 S x , 则修改 rep[x] 时 , S x 至少加倍 . 由于 S x 不超过 n, 因此修改次数不超过 log 2 n, 总 nlogn 树结构 • 每个集合用一棵树表示 , 根为集合代表 树结构的合并 • 和链结构类似 , 小的合并到大的中 技巧 2: 路径压缩 • 查找结束后顺便把父亲 设置为根 , 相当于有选择 的设置 rep 指针而不像链 结构中强制更新 所有 rep 路径压缩的分析 • 设 w[x] 为 x 的子树的结点数 , 定义势能函数 • Union(x i , x j ) 增加势能 . 最多会让 w[rep[xi]] 增加 w[rep[xj]]n, 因此势能增加不超过 logn • Find-Set(x) 减少势能 . 把路径压缩看作是从根到 结点 x 的向下走过程 , 则除了第一次外的其他向下 走的步骤 p Æ c 会让 c 的子树从 p 的子树中移出 , 即 w[p] 减少 w[c], 而其他点的 w 值保持不变 路径压缩的分析 • Find-Set 除了第一次外的其他向下走的步骤 p Æ c 会让 c 的子树从 p 的子树中移出 – 情况一 : w[c]w[p]/2, 则势能将至少减少 1 – 情况二 : w[c]w[p]/2, 这种情况最多出现 logn 次 , 因为 w[p] 最多进行 logn 次除 2 操作就会得到 1 • Union 操作积累起来的 mlogn 的势能将被 Find-Set 消耗 , 情况一最多消耗 mlogn 次 , 情 况二本身不超过 mlogn 次 , 因此 • 定理 : Find-Set 的总时间为 O(mlogn) 路径压缩的分析 • 定理 : 如果所有 Union 发生在 Find-Set 之前 , 则所有操作的时间复杂度为 O(m) • 证明 : 每次 Find-Set 将会让路径上除了根的 所有结点为根的儿子 . 所有结点只会有一次 改变因此总时间复杂度为 O(m) • 也就是说 – 只使用技巧 1( 启发式合并 ): O(mnlogn) – 只使用技巧 2( 路径压缩 ): O(mlogn) • 同时使用呢 ? Ackermann 函数及其反函数 树结构的完整结论 • 定理 : m 个操作的总时间复杂度为 ( ( ) ) O m α n void makeset(int x){ rank[x] 0; p[x]x; } int findset(int x){ int i, px x; while (px ! p[px]) px p[px]; while (x ! px) { i p[x]; p[x] px; x i; } return px; } void unionset (int x , int y){ x findset(x); y findset(y); if(rank[x] rank[y]) p[y] x; else { p[x] y; if(rank[x] rank[y]) rank[y]; } } 例 1. 亲戚 • 或许你并不知道你的某个朋友是你的亲戚。他 可能是你的曾祖父的外公的女婿的外甥女的表姐 的孙子。如果能得到完整的家谱判断两个人是 否亲戚应该是可行的但如果两个人的最近公共 祖先与他们像个好几代使得家谱十分庞大那 么检验亲戚关系实非人力所能及。在这种情况 下最好的帮手就是计算机。 • 为了将问题简化你将得到一些亲戚关系的信 息如同 Marry 和 Tom 是亲戚 Tom 和 Ben 是亲 戚等等。从这些信息中你可以推出 Marry 和 Ben 是亲戚。请写一个程序对于我们的关于亲 戚关系的提问以最快的速度给出答案。 分析 • 本质 : 是否在图的同一个连通块 • 问题 : 图太庞大 , 每次还需要遍历 • 解决 : 用并查集 例 2. 矩形 • 在平面上画了 N 个长方形每个长方形的边平行 于坐标轴并且顶点坐标为整数。我们用以下方式 定义印版 – 每个长方形是一个印版 – 如果两个印版有公共的边或内部那么它们组成新的 印版否则这些印版是分离的 • 数出印版的个数 . 左图有两个右图只有一个 分析 • 把矩形看作点有公共边的矩形连边问 题转化为求连通分量的个数 • 判断方法 Y ( X 2 , Y 2 ) ) , ( 2 2 ′ ′ Y X ( X 1 , Y 1 ) ) , ( 1 1 ′ ′ Y X X 例 3. 代码等式 • 由元素 0 和 1 组成的非空的序列称为一个二进制代 码。一个代码等式就是形如 x 1 x 2 .. x l y 1 y 2 .. y r , 这里 x i 和 y j 是二进制的数字 0 或 1 或者是一个变量如 英语中的小写字母 • 每一个变量都是一个有固定长度的二进制代码 它可以在代码等式中取代变量的位置。我们称这 个长度为变量的长度 • 对于每一个给出的等式计算一共有多少组解。 • 例 : a,b,c,d,e 的长度分别是 4,2,4,4,2, 则 1bad1 acbe 有 16 组解 分析 • 长度为 k 的变量拆成 k 个长度为 1 的变量 • 每位得到一个等式 – 11 或者 00 冗余等式 – 10 或者 01 无解 – ab a 和 b 相等 a 为变量 b 可以为常数 • 相等关系用并查集处理最后统计集合数 为 n 答案为 2 n 。 例 4. 围墙 • 按顺序给出 M 个整点组成的线段找到最小 的 k 使得前 k 条线段构成了封闭图形。 任意两条线段只可能在端点相交 分析 • 将所有出现过的坐标用整数表示初始时 候每个独立成树。读入连接 A 和 B 的线段 后将 A 、 B 所在的树和并。如果 A 、 B 在同 一棵树那么就出现了封闭图形因为 x 个 点 x 条边的图必定出现圈 • 把坐标转换成编号的步骤可以通过对坐 标进行排序再删除重复。 • 时间 : O(MlogM) 例 5. 可爱的猴子 • 树上挂着 n 只可爱的猴子 n ≤ 2*10 5 。 • 猴子 1 的尾巴挂在树上 • 每只猴子有两只手每只手可以抓住最多一只猴 子的尾巴也可以不抓。猴子想抓谁一定抓得到 • 所有猴子都是悬空的因此如果一旦脱离了树 猴子会立刻掉到地上。 • 第 0 1 … m 1 ≤ m ≤ 400 000 秒中每一秒 都有某个猴子把他的某只手松开因此常有猴子 掉在地上 • 请计算出每个猴子掉到地上的时间 分析 • 并查集 • “ 时光倒流 ” • 如何标记每只猴子的时间 – 枚举并查集的元素 – 需要访问兄弟 / 儿子 – 链表即可 – 不用指针 例 6. 奇数偶数 • 你的朋友写下一个由 0 和 1 组成的字符串并 告诉你一些信息即某个连续的子串中 1 的个 数是奇数还是偶数。你的目标是找到尽量小 的 i 使得前 i1 条不可能同时满足 – 例如序列长度为 10 信息条数为 5 – 5 条信息分别为 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd • 正确答案是 3 因为存在序列 (0,0,1,0,1,1) 满 足前 3 条信息但是不存在满足前 4 条的序列 分析 • 部分序列 – 可以从 s 的奇偶性恢复整个序列 – a b even 等价于 s[b], s[a-1] 同奇偶 – a b odd 等价于 s[b], s[a-1] 不同奇偶 • 一开始每个 s[i] 自成一集合 – a b even Æ 合并 s[b], s[a-1] – a b odd Æ ??? • 矛盾的标志 例 7. 团伙 • 如果两个认识 , 那么他们要么是朋友要么是 敌人 , 规则如下 – 朋友的朋友是朋友 – 敌人的敌人是敌人 • 给出一些人的关系 ( 朋友、敌人 ), 判断一共 最多可能有多少个团伙 例 8. 船 • 给一个 01 矩阵 , 黑色代 表船 . 右图有一个 29 吨 的 , 3 个 7 吨的 , 两个 4 吨 的和三个一吨的 . • 输入行数 N(30000) 和 每行的黑色格子 ( 区间 数和每个区间 ) • 输出每种重量的个数 • 一共不超过 1000 个船 , 每个的重量不超过 1000 例 9. 离线最大值 • 设计一个集合 , 初始为空每次可以插入一 个 1~n 的数 (1~n 各恰好被插入一次 ), 也可以 删除最大值 , 要求 m 次操作的总时间尽量小 . 分析 • 在最后加入 n-m 次虚拟的 MAX 操作 , 并记第 i 个 MAX 操作为 M i , 记 M 1 之前的插入序列为 S 1, M i-1 (1im) 和 M i 之间的插入序列为 S i • 如果 n 在 S j 中被插入则 M j 的输出一定是 n. 然后删除 M j 即 把 S j 合并到 S j1 中 然后再 查找 n-1 所在的序列 S k 则 M k 的输出为 n- 1… 如此下去从 n 到 1 依次查找每个数所在 序列就可以得到它后面的 MAX 操作的结 果 , 并把它和紧随其后的序列合并 例 10. 合并队列 • 初始时 n 个数 1~n 各在单独的一列中 , 需要执 行两个操作 – Move(i, j): 把 i 所在列接到 j 所在列的尾部 – Check(i, j): 询问 i 和 j 是否在同一列 , 如果是 , 输 出二者之间的元素个数 分析 • 每个数 i 的 p[i] 表示 i 和 p[i] 在同一队列 , 且 p[i] 是 i 之前的第 d[i] 个元素 • 对于队首 x, 有 p[x]x, 附加变量 tot[x] 表示以 x 为首的队列一共有多少个元素 – Mo v e 需要进行两次查找和一次合并 – Ch e c k 需要两次查找 • FIN D: 修改 p[i] 时要修改 d[i] • ME R G E: 可以启发式合并么 ??? 四、哈希表 哈希表 • 哈希表 (Hash table) 经常被用来做字典 (dictionary), 或称符号表 (symbol-table) 直接存取表 • 直接存取表 (Direct-access table) 的基本思 想是 : 如果 key 的范围为 0~m-1 而且所有 key 都不相同 , 那么可以设计一个数组 T[0..m-1], 让 T[k] 存放 key 为 k 的元素 , 否则为空 (NIL) • 显然 , 所有操作都是 O(1) 的 • 问题 : key 的范围可能很大 ! 64 位整数有 18,446,744,073,709,551,616 种可能 , 而字 符串的种类将会更多 ! 解决方案 : 哈希函数 哈希函数的选取 • 严格均匀分布的哈希函数很难寻找 , 但一般 说来有三种方法在实际使用中效果不错 – 取余法 : 取 h(k) k mod m – 乘积法 : 取 h(k) (A*k mod 2 w ) rsh (w-r) – 点积法 : 随机向量 a 和 k 的 m 进制向量做点积 • 实践中经常采用取余法 取余法 • 一般来说不要取 m2 r , 因为它只取决于 k 的后 r 位 • 一般取 m 为不太接近 2 或 10 的幂 乘积法 • 取 m2 r , 计算机字长为 w, 则 H(k) (A*k mod 2 w ) rsh (w-r) • 其中 rsh 表示右移位 , A 是满足 2 w-1 A2 w 的 奇数 . 注意 : A 不应该太接近于 2 w . 由于乘法 并对 2 w 取余是很快的 ( 自然就会丢弃高位 ), 而算术右移也很快因此函数计算开销小 冲突解决 • 不同的 key 映射到同一个数 , 称为冲突 (collision), 冲突的两个元素显然不可能放在 哈希表的同一个位置 • 通常有两种冲突解决方案 (resolving collisions) – 链方法 (chaining): 把 key 相同的串成链表 – 开放地址法 (open addressing): 自己的位置被 占了 , 就去占别人的 链地址法 • Ke y 相同的元素形成一个链表 链地址法的查找效率 • 链地址法的时间效率取决于 hash 函数的分布 . 我 们假设每个 k 将等可能的被映射到任意一个 slot, 不管其他 key 被映射到什么地方 • 设 n 为 key 的数目 , m 为不同的 slot 数 , 装载因子α n/m, 即每个 slot 平均的 key 数 , 则 • nO(m) 时期望搜索时间是 O(1) 的 开放地址法 • 开发地址法只使用表内的空间 . 如果冲突产生 , 计 算出第二个可能的位置 , 如果那里也有其他元素 , 再看第三个可能的位置 … 即按一个 探测序列 查找 • 位置应该是 key 和探测的次数 (probe number) 的函 数 , 第 i 次探测位置为 slot h(k,i) • 每个 slot 都应能被探测到 , 因此每个 k 的探测序列 h(k,0), h(k,1), h(k,2), …,h(k,m-1) • 都应是 {0,1,…,m-1} 的排列 • 注意 : 开放地址法不容易 删除 元素 开放地址法示例 探测方法 • 线性探测 : • 虽然很简单 , 但是容易形成元素堆积 • 二次哈希 : 组合两个哈希函数 • 一般效果会好很多但应保证 h 2 (k) 和 m 互素 , 比如 取 m 为 2 的幂而让 h 2 (k) 只产生奇数 开放地址法的查找效率 • 假设每个 key 等概率的把 m! 个排列中的任何 一个作为它的探测序列 , 则有 • 定理 : 装载因子α 1 时 , 不成功查找的期望 探测次数为 1/ (1- α) • 证明 : 第 i 次探测到非空 slot 的概率为 (n-i)/(m-i) n/m α • 下面各种情况按概率加权计算期望 开放地址法的查找效率 • 各种情况按概率加权 , 得期望的探测次数为 查找效率比较 • 把开放地址法说通俗一点就是 – 装载因子为常数时 , 期望查找次数为常数 – 一半装满时 , 期望查找次数为 1/(1-0.5)2 – 装满 90% 时 , 期望查找次数为 1/(1-0.9)10 • 装得比较满 ( 尤其是 nm) 时 , 使用链地址法 – 在哈希表里保存每个 key 的第一个元素 first[0..m-1], – 在一个数组 data[1..n] 里装着所有元素和下一个 元素 next[1..n] 链地址法参考代码 • 在实际应用中推荐使用链地址法 – first[i] 表示 哈希函数值为 i 的第一个数据下标 – ke y [i] 和 next[i] 表示 第 i 个 数据的 key 和下一个 int find(int k){ int h hash(k); int p first[h]; while (p){ if(key[p] k) return p; p next [p]; } return 0; } void insert(int x){ int h hash(key[x]); next[x] first[h]; first[h] x; }
