Category Archives: 算法&数据结构

[转载]基于用户投票的排名算法

这是 阮一峰 写的系列的文章,共6篇,对于投票类的排名计算,非常有意义,由于图、公式比较多,就直接贴出原文链接了。

基于用户投票的排名算法(一):Delicious和Hacker News

基于用户投票的排名算法(二):Reddit

基于用户投票的排名算法(三):Stack Overflow

基于用户投票的排名算法(四):牛顿冷却定律

基于用户投票的排名算法(五):威尔逊区间

基于用户投票的排名算法(六):贝叶斯平均

数据结构重读 – 哈希表

无论是折半查找、二叉排序树查找还是B树,性能都依赖于查找中的比较次数。

一种理想情况是不经过任何比较,一次直接定位索要查找的记录,即:若数据结构中存在关键字和K相等,则其必定在f(K)的存储位置上,我们称这个对应关系f为哈希函数

冲突(Collision):对不同的关键字,可能得到同一哈希地址,即存在key1!=key2,但f(key1)=f(key2)。此时称为冲突或碰撞。

由于在实际应用中,哈希函数都是压缩函数,所以冲突只能尽可能的减少,很难完全避免。

哈希表:根据[……]

继续阅读

后缀数组 – 扫盲篇

一、后缀的定义

后缀数组,做为后缀树的替代品,可以解决很多棘手的字符串处理问题。

长度为n的String[0, 1…n-1]

定义后缀Suffix(i)=sub_string[i…n-1]。

例如字符串aabaaaab,Suffix[1] = abaaaab,Suffix[7]=b。

考虑到空间问题,以及C系列语言中,Suffix[i]非常好求得(&str[i]即可)。一般不会保存Suffix[i]这个数组。

二、后缀数组sa和逆运算数组ran[……]

继续阅读

蓄水池算法

问题描述

要求从N个元素中随机的抽取k个元素,其中N无法确定(N是个流,可能无穷大)。

这种应用的场景一般是数据流的情况下,由于数据只能被读取一次,而且数据量很大,并不能全部保存,因此数据量N是无法在抽样开始时确定的;但又要保持随机性,于是有了这个问题。所以搜索网站有时候会问这样的问题。

这里的核心问题就是“随机”,怎么才能是随机的抽取元素呢?我们设想,买彩票的时候,由于所有彩票的中奖概率都是一样的,所以我们才是“随机的”买彩票。那么要使抽取数据也随机,必须使每一个数据被抽样出[……]

继续阅读

数据结构重读 – 键树、字典树

键树,又称数字查找树(Digital Search Trees)是一棵度>=2的树,每个结点只含有组成关键字的符号。

键树有两种存储结构:

1、树的孩子-兄弟链表来表示键树。

每个Node有三个域:first指向第一棵子树的根指针;next指向右兄弟;info(可选的)记录附加数据。如下图:

查找过程是,从根结点出发,顺着first查找,如果相等,继续下一个first。否则沿着next查找。直到到了空指针为止。此时若仍未完成key的匹配,查找不成功。[……]

继续阅读