详解布隆过滤器

一、引言假设我们想要开发一个邮件系统,那么如何实现垃圾邮件的过滤呢。 最简单的办法就是把确定为是垃圾邮件的地址都保存起来,存入黑名单中。当用户接收到黑名单地址的邮件时,直接将邮件归类到垃圾箱中。 垃圾邮件的地址数量可能是巨大的,因此除了被存储在数据库中,程序实际使用的时候一定是需要借助缓存的。不论是使用本地缓存还是内存缓存,当数据量达到一定数量级时,都是不太合适的。 咳咳,如果你的数量级连百万...

热度算法和个性化推荐

今日头条的走红带动了“个性化推荐”的概念,自此之后,内容型的产品,个性化算法就逐渐从卖点变为标配。伴随着“机器学习”,“大数据”之类的热词和概念,产品的档次瞬间提高了很多。而各种推荐算法绝不仅仅是研发自己的任务,作为产品经理,必须深入到算法内部,参与算法的设计,以及结合内容对算法不断“调教”,才能让产品的推荐算法不断完善,最终与自己的内容双剑合璧。 本文以新闻产品为例,结合了我之前产品从零积累用户...

字符串的模式匹配(KMP)算法

一、背景给定一个主串(以 S 代替)和模式串(以 P 代替),要求找出 P 在 S 中出现的位置,此即串的模式匹配问题。 Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。 在继续下面的内容之前,有...

波兰表达式与逆波兰表达式

常见的算术表达式,称为中缀表达式,例如: 15 + ( 6 – 4 / 2 ) * 3 波兰表达式波兰表达式也称为前缀表达式,以上面的例子为例,其波兰表达式为: 1+ 5 * - 6 / 4 2 3 中缀表达式转换前缀表达式的操作过程为: (1)首先设定一个操作符栈,从右到左顺序扫描整个中缀表达式: 如果是操作数,则直接归入前缀表达式; 如果是括号:如果是右括号,则直接将其入栈;如果是左括号,...

最长上升子序列(LIS)算法

理解:该子序列中后一项都比前一项大,例如有序列2 7 1 5 6 4 3 8 9,则最长上升子序列为2 5 6 8 9。 具体应用:用于确定一个代价最小的调整方案,使一个序列变为升序。只需要固定LIS中的元素,调整其他元素即可。 动态规划实现 O(n2)我们将序列存入数组a中,定义一个dp数组,存放最大长度。 2 7 1 5 6 4 3 8 9 我们能够得出一个规律: dp[i] = 前面v...

最长公共子序列(LCS)算法

一、最长公共字串与最长公共子序列1.1 最长公共子串(Longest Common Substirng)子串是串的一个连续的部分,子串中字符的位置必须连续。 例如:有两个字符串ABCBDAB 和 BDCABA,则它们的最长公共子串是:AB。 1.2 最长公共子序列(Longest Common Subsequence,LCS)子序列是从串中去掉任意的元素而获得新的序列,子串中字符的位置不必连续。 ...

最小生成树(Prim)算法

算法思想 假设G=<V,E>是连通图,TE是G上最小生成树中边的集合。 算法从U={u0}(u0∈V),TE={ }开始,任取一个顶点u0作为开始点。 重复执行下述操作:在所有u∈U, v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止。 注意:选择最小边时,可能有多条同样权值的边可选,此时任选其一。 代码实现12345...
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×