Shu Wang

Silence maks big money

(数据结构)- B树

B树

B树(有时候也叫 B- 树)与 AVL 树一样是平衡树。比如各种文件系统,可能需要把一些已经排过序的数据存放在离散的节点之中。如果使用其他的树,例如二叉搜索树,如果插入的是顺序的数据,那么二叉搜索树就会退化为线性的查找(深度太大)。每次访问某个非叶子节点,就需要比较它的键值(这个时候就需要访问磁盘,进一步增加了查找的时间)。所以我们需要减小深度,但是查找的次数是不变的,这样的话我们就必须要减小“向下”访问子树的次数,在当前的节点中比较尽可能多的东西。B树就是一个多路搜索树。

Read more

(算法) – 网络流

网络流问题与线性规划

网络流

假设一个最大流的图例:

设 G=(V,E) 是一个网络流,设 s 为源点,t 为汇点。G 的流的一个实值函数 f: VxV -> R,对所有点 v 和 u ,满足以下的性质:

  • 容量限制:f(u, v) <= c(u, v) 一条边的流不超过它的容量
  • 反对称性:f(u,v) = -f(v,u)。
  • 流量守恒:除非 u=s 或 u=t,否则从 u 流入流出的总和必须是 0。

f(u,v) 为从 u 发送到顶点 v 的流量(flow)。流的值定义为 |f|=从源点 s 到 t 的最大流。

Read more

(算法)- 模式匹配

Alphabet 类

这个类是处理各种字符串所需要用的字符串组成要素(字符集合)的抽象描述。具体的实现参见 Github。部分接口:

Read more

(算法&数据结构) – 图论最短路径 2

最短路径 Bellman-Ford 以及SPFA 算法

  • 边的松弛:放松边 v->w 意味着检查从 s 到 w 的最短路径是否先从 s 到 v,然后再由v -> w。如果是,则需要更新数据。
  • 如果一个图出现了负的环,那么从 s 到 v,期间如果有点是属于负权环的话,则从 s 到 v 没有最短路径,应该是负无穷。(只要绕着这个环转圈)

Read more

(算法&数据结构) – 红黑树

红黑树的性质

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是NIL节点)。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
  6. 红链接均为左链接(这种树被称为:Left Lean RedBlack Tree)

这些性质保证了:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。

Read more

(二叉树)- 二叉搜索树

1.二叉树的性质:

  • 第i层最多有2^(i-1)个节点,当然i>=1的。
  • 深度为k的二叉树最多有2^k-1个节点。

Read more

(DFS) – 特别一点的DFS系列 POJ3009

1.原题:http://poj.org/problem?id=3009。题意是冰壶游戏,给定若干组的地图,W表示宽度(列数)H表示高度(行数)。然后接下来的H行W列就是地图数据。0表示没有障碍 1表示障碍 2表示起点 3表示终点。程序的目的是给定一个起点和一个终点,求出满足下列规则的最小的移动数目。

Read more

(DP) – 乘积最大 TJPUACM

1.概述:

原题感觉不是很难,但是一开始很难想到。而且实现起来也会有些需要想到的问题。我觉得这道题对于有些利用DP算法的题目的理解具有很大的帮助。比如Floyd算法的理解,可以看看我的另一篇文章哦。

Read more

(贪心) – POJ1328

1.概述

原题的意思是,给定两个整型数字n(1<=n<=1000)和一个d(表示雷达的识别距离)。然后接下来的n行分别有两个数x,y表示岛I(i)的坐标(x,y)其中个i(1<=i<=n),你的目标是求可以覆盖所有岛屿的最少的雷达数量(雷达只能放在x轴上)。

Read more