蓄水池算法的分析与python实现

题目描述

现在有一组数,不知道这组数的总量有多少,请描述一种算法能够在这组数据中随机抽取k个数,使得每个数被取出来的概率相等。

给出一个数据流,这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法,使得数据流中所有数据被选中的概率相等。

Read More

位运算简介及基本技巧

什么是位运算

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作。比如,and运算本来是一个逻辑运算符,但整数与整数之间也可以进行and运算。举个例子,6的二进制是110,11的二进制是1011,那么6 and 11的结果就是2,它是二进制对应位进行逻辑运算的结果(0表示False,1表示True,空位都当0处理):

110 AND 1011 --> 0010(b) --> 2(d)

Read More

字符串匹配KMP算法

字符串匹配是计算机的基本任务之一。

朴素的模式匹配算法

算法思想

举例来说,有一个字符串”BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含另一个字符串”ABCDABD”?

BBC ABCDAB ABCDABCDABDE
x
ABCDABD

Read More

最长回文子串——Manacher 算法

问题定义

最长回文子串问题:给定一个字符串,求它的最长回文子串长度。

Manacher 算法

首先用一个非常巧妙的方式,将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度:在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。

Read More