算法专题_并查集

并查集可以高效的维护数据的分组信息,并可以快速完成以下操作:

  • 查询元素a和元素b是否属于同一个组
  • 合并元素a和元素b所在的组

并查集使用一棵树来维护一个分组的信息,多棵树构成的森林表示这个完整的数据结构。如果查询a和b是否属于同一组,只需要向上搜索直到树根,看a和b的树根是否一样就可以了。如果要合并a和b所在的分组,只需要把a和b连在一起就可以了,通常是把a和b所在树的树根连在一起。

Ler Mais

算法专题_线段树

线段树是一棵二叉树,他的每个节点包含了两个额外的属性startend用于表示该节点所代表的区间。start和end都是整数,并按照如下的方式赋值:

根节点的 startendbuild 方法所给出。 对于节点 A 的左儿子,有 start=A.left, end=(A.left + A.right) / 2。 对于节点 A 的右儿子,有 start=(A.left + A.right) / 2 + 1, end=A.right。 如果 start 等于 end, 那么该节点是叶子节点,不再有左右儿子。 实现一个 build 方法,接受 start 和 end 作为参数, 然后构造一个代表区间[start, end]的线段树,返回这棵线段树的根。

Ler Mais

Hexo中使用gist存储代码片段

以前都是直接把代码用代码块的形式写在markdown里面,这样有的时候代码太长,文件就会变得很长,不方便阅读。最近发现了GitHub上面的gist,能不限量的存储代码块,而且可以方便的引用和分享。就想着以后Hexo博客里面的代码直接放在Gist里面再引用好了。这样代码片段都可以保存在一起,还有代码管理功能,修改起来也方便。

Ler Mais

四等分数组

题目

1
2
3
4
5
6
对于一个长度为N的整型数组A, 数组里所有的数都是正整数,对于两个满足0<=X <= Y <N的整数,
A[X], A[X+1] … A[Y]构成A的一个切片,记作(X, Y).
用三个下标 m1, m2, m3下标满足条件0 < m1, m1 + 1 < m2, m2 +1 < m3 < N – 1。
可以把这个整型数组分成(0, m1-1), (m1+1, m2-1), (m2+1, m3-1), (m3+1, N-1) 四个切片。
如果这四个切片的整数求和相等,称作“四等分”。 编写一个函数,求一个给定的整型数组是否可以四等分
要求: 函数的计算复杂度为O(N),使用的额外存储空间(除了输入的数组之外)最多为O(N)。

Ler Mais