B树 B树(有时候也叫 B- 树)与 AVL 树一样是平衡树。比如各种文件系统,可能需要把一些已经排过序的数据存放在离散的节点之中。如果使用其他的树,例如二叉搜索树,如果插入的是顺序的数据,那么二叉搜索树就会退化为线性的查找(深度太大)。每次访问某个非叶子节点,就需要...

 2018年4月21日 -  649次阅读 -  0条评论

网络流问题与线性规划 网络流 假设一个最大流的图例: 设 G=(V,E) 是一个网络流,设 s 为源点,t 为汇点。G 的流的一个实值函数 f: VxV -> R,对所有点 v 和 u ,满足以下的性质: 容量限制:f(u, v) <= c(u, v) 一条边的流不超过它的容量 反对称性:f(u,v)...

 2018年4月18日 -  719次阅读 -  0条评论

Alphabet 类 这个类是处理各种字符串所需要用的字符串组成要素(字符集合)的抽象描述。具体的实现参见 Github。部分接口: 方法 说明 方法 说明 Alphabet() 构造,默认的字符编码范围[0, 256) Alphabet(int R) 构造,默认默认编码范围[0,R) Alpha...

 2018年4月18日 -  659次阅读 -  0条评论

最短路径 Bellman-Ford 以及SPFA 算法 边的松弛:放松边 v->w 意味着检查从 s 到 w 的最短路径是否先从 s 到 v,然后再由v -> w。如果是,则需要更新数据。 如果一个图出现了负的环,那么从 s 到 v,期间如果有点是属于负权环的话,则从 s 到 v 没有最短路径,应...

 2018年3月17日 -  1126次阅读 -  0条评论

红黑树的性质 节点是红色或黑色。 根是黑色。 所有叶子都是黑色(叶子是NIL节点)。 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。) 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 红...

 2017年9月23日 -  748次阅读 -  0条评论

1.二叉树的性质: 第i层最多有2^(i-1)个节点,当然i>=1的。 深度为k的二叉树最多有2^k-1个节点。 对任何一棵二叉树T,如果其终端的节点为n0,度为2的节点为n2,则n0=n2+1。也就是叶子结点的数量=有两个儿子的非叶子节点+1。总的分支线为(n-1)条。n-1=2*n...

 2017年4月21日 -  546次阅读 -  0条评论

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

 2017年4月16日 -  570次阅读 -  0条评论

1.概述: 原题感觉不是很难,但是一开始很难想到。而且实现起来也会有些需要想到的问题。我觉得这道题对于有些利用DP算法的题目的理解具有很大的帮助。比如Floyd算法的理解,可以看看我的另一篇文章哦。 2.题目的意思: 首先N个字符组成的序列,插入K个乘号,要求...

 2017年4月15日 -  441次阅读 -  0条评论

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

 2017年4月15日 -  467次阅读 -  0条评论

1.Dijkstra算法 逻辑结构: 对于一个无向有权图(邻接矩阵存储的): 索引值 0 1 2 3 4 5 6 7 8 A: 0 0 4 10 ∞ 3 ∞ ∞ ∞ ∞ B: 1 4 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ C: 2 10 ∞ 0 ∞ ∞ ∞ ∞ ∞ 55 D: 3 ∞ ∞ ∞ 0 1 ∞ ...

 2016年12月31日 -  778次阅读 -  0条评论