Algorithm

LeetCode 组队刷题活动

组队刷 LeetCode

介绍

代码仓库

 代码仓库的坐标:asdf2014 / algorithm

报名途径

 只需要在《Algorithm》文末留言,即可随时参与

留言内容的话,至少要留一下自己的 Github 名称,方便我们这边统计汇总。另外,也可以说明下自己能接受的刷题频率、希望的选题策略,亦或者,对算法知识沉淀的模式有好的建议,都可以提出

参与方式

 每位参与的小伙伴,都会获得代码仓库的 Collaborators 权限,可以自由地提交代码。在 /Codes/${User} 目录下,每人都将拥有一个自己的代码库

刷题频率

 考虑到可能大家的闲暇时间并不多,我们暂定刷题频率为“一周一题”

选题策略

 分为两个阶段:

  • 前 100 题都是经典中的经典,所以我们第一阶段先将这些题目吃透
  • 第二阶段,通过程序进行随机选定,历史题库可以点击链接看到

其他

 操作 Git 时遇到问题的话,可以参考我的一篇博客《Git 高级玩法

也可以直接在文章最后留言。目前,支持 Gitalk + Disqus 两种留言系统,以便更好地服务于国内和海外的小伙伴

 同时,为了大家更加方便地交流,也欢迎加入算法 QQ 群,群号 128708857

但是,请不要在评论区讨论入群问题的答案,避免打广告的进入

 另外,因为大部分算法都会有很多实现思路,我们会尽可能地展现所有可能的解题方法。但为了文章的排版更加地紧凑,我们会将同一算法的不同实现,通过选项卡的形式展现。且默认展示的选项卡将会是最优解。这样的话,如果您想要快速阅读本文,则可以不用翻看其他的选项卡。实际效果如下:

迭代解

1
2
3
4
5
6
7
8
9
10
11
def solution(n):
if n <= 1:
return n
a = 0
b = 1
while n > 1:
n = n - 1
sum_ = a + b
a = b
b = sum_
return b

递归解

1
2
3
4
5
def solution(n):
if n <= 1:
return n
else:
return solution(n - 1) + solution(n - 2)

动态规划解

1
2
3
4
5
6
7
8
def solution(n):
if n <= 1:
return n
cache = [x for x in range(0, n + 1)]
cache[1] = 1
for i in range(2, n + 1):
cache[i] = cache[i - 1] + cache[i - 2]
return cache[n]

进度

截止目前为止,集结的小伙伴数量:,已刷题:,覆盖的算法种类:

下文将总结归纳大家讨论交流的内容,不断地沉淀解题过程中思考的点滴

经典算法

字符串匹配

朴素算法(Naive Algorithm)

Rabin-Karp 算法

有限自动机算法(Finite Automation)

KMP

 KMP,Knuth-Morris-Pratt 匹配算法

Boyer-Moore 算法

Simon 算法

Colussi 算法

Galil-Giancarlo 算法

Apostolico-Crochemore 算法

Horspool 算法

Sunday 算法

参考

Book
  • 《柔性字符串匹配》

Sorting Algorithm

参考

Dynamic Programming

定义

 动态规划DPDynamic Programming),是一种通过把原问题分解为相对简单的子问题,以求解复杂问题的方法

关键概念

状态

 用来描述该问题的子问题的解

状态转移方程

 状态和状态之间的关系式

 例如,斐波那契数列,可以表示为:

递推

 每个阶段只有一个状态

贪心

 每个阶段的最优状态,都是由上一个阶段的最优状态得到的

搜索

 每个阶段的最优状态,是由之前所有阶段的状态的组合得到的

动态规划

 每个阶段的最优状态,可以从之前某个阶段的某个或某些状态直接得到,而不管之前这个状态是如何得到的

最优子结构

 每个阶段的最优状态,可以从之前某个阶段的某个或某些状态直接得到

无后效性

 不管之前这个状态是如何得到的

参考

Hash

参考

预测算法

简易平均法

算术平均值

加权平均值

移动平均法

指数平滑法

参考

线性回归法

分类算法

贝叶斯(Bayes)

描述

 其中,$P(A \mid B)$ 是在 $B$ 发生的情况下 $A$ 发生的可能性,称为 $A$ 的后验概率。相应的,$P(B \mid A)$ 则称为 $B$ 后验概率;$P(A)$ 是不考虑任何 $B$ 方面的因素下 $A$ 发生的可能性,称为 $A$ 的先验概率(或边缘概率)。相应的,$P(B)$ 则称为 $B$ 的先验概率

种类

特征独立性

 按照特征之间独立性的强弱,可以分为 朴素贝叶斯、半朴素贝叶斯、(一般的)贝叶斯 等

分布情况

 按照属性和特征的分布情况,又可以分为 高斯贝叶斯、多项式贝叶斯、伯努利贝叶斯 等

离散程度

 按照训练集的离散程度,还可以分为 离散型贝叶斯、连续型贝叶斯、混合型贝叶斯 等

编码实战

 The set A contains 30 a and 10 b, and the set B contains 20 a and 20 b, then what is the value of P(A|a)?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
situations = dict()


def priori_probability(situation, probability):
situations[situation] = probability # P(A), P(B)


def posterior_probability(situation, probability):
old_prob = situations[situation]
situations[situation] = old_prob * probability # P(A)P(a|A), P(B)P(a|B)


def normalize():
count = 0
for situation in situations.values():
count += situation # P(A)P(a|A) + P(B)P(a|B)
for situation, probability in situations.items():
# P(A)P(a|A)/(P(A)P(a|A) + P(B)P(a|B)), P(B)P(a|B)/(P(A)P(a|A) + P(B)P(a|B))
situations[situation] = situations[situation] / count


def prob(hypothis):
return situations[hypothis] # P(A|a), P(B|a)


priori_probability('A', 0.5) # P(A)=1/2
priori_probability('B', 0.5) # P(B)=1/2

posterior_probability('A', 0.75) # P(a|A)=3/4
posterior_probability('B', 0.5) # P(a|B)=1/2

normalize()
prob = prob('A') # P(A|a)
print('The probability of getting `a` that belongs to set `A`: %s' % prob)
# P(a|A): 从 A 中获取 a
# P(A|a): 获取 a,并且 a 恰巧是属于 A 的
# 这两个描述的场景完全不同,对应的概率也因而不同

补充

 当存在多个特征变量时,表达式可扩展为

 其中,$\frac{1}{Z}$ 是一个只与 $F_i$ 相关的缩放因子,且当特征变量的值固定时,$\frac{1}{Z}$ 为常量

支持向量机(SVM)

聚类算法

K-means

介绍

 输入聚类个数 k,以及包含 n 个数据对象的数据库,输出满足方差最小标准 k 个聚类的一种算法

步骤

  • 从 n 个数据对象任意选择 k 个对象作为初始聚类中心
  • 根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分
  • 重新计算每个(有变化)聚类的均值(中心对象)
  • 计算标准测度函数,当满足一定条件,如函数收敛时,则算法终止;如果条件不满足则回到第二步

基数估算

非概率算法

BitMap

Roaring Bitmap

Bloom filter

双层字典码

概率算法

Count-Mean-Min Sketch

LogLog Counting

Linear Counting

LogLog Counting

Adaptive Counting

HyperLogLog Counting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
m = 2 ^ b  # with b in [4...16]

if m == 16:
alpha = 0.673
elif m == 32:
alpha = 0.697
elif m == 64:
alpha = 0.709
else:
alpha = 0.7213 / (1 + 1.079 / m)

registers = [0] * m # initialize m registers to 0

##############################################################################################
# Construct the HLL structure
for h in hashed(data):
register_index = 1 + get_register_index(h, b) # binary address of the rightmost b bits
run_length = run_of_zeros(h, b) # length of the run of zeroes starting at bit b+1
registers[register_index] = max(registers[register_index], run_length)

##############################################################################################
# Determine the cardinality
DV_est = alpha * m ^ 2 * 1 / sum(2 ^ -register) # the DV estimate

if DV_est < 5 / 2 * m: # small range correction
V = count_of_zero_registers(registers) # the number of registers equal to zero
if V == 0: # if none of the registers are empty, use the HLL estimate
DV = DV_est
else:
DV = m * log(m / V) # i.e. balls and bins correction

if DV_est <= (1 / 30 * 2 ^ 32): # intermediate range, no correction
DV = DV_est
if DV_est > (1 / 30 * 2 ^ 32): # large range correction
DV = -2 ^ 32 * log(1 - DV_est / 2 ^ 32)

HyperLogLog++

MinHash

HyperLogLog++ & Inclusion-exculsion principle

HyperLogLog++ & MinHash

参考

Blog

Github

数据库相关

二叉查找树

平衡二叉树

AVL 树

红黑树

B 树

B+ 树

参考

SnapTreeMap

参考

LSM tree

参考

前缀树

Tire Tree + Double Array + Aho-Corasick

参考

Patricia Tree

SlimTire

参考

图论

图计算

概念

 图计算是以图论为基础的对现实世界的一种结构的抽象表达,以及在这种数据结构上的计算模式。通常,在图计算中,基本的数据结构表达就是:

 $G = (V, E, D)$,其中,V = vertex(顶点或者节点),E = edge(边),D = data(权重)

 比如说:对于一个消费者的原始购买行为,有两类节点:用户和产品,边就是购买行为,权重是边上的一个数据结构,可以是购买次数和最后购买时间。对于许多我们面临的物理世界的数据问题,都可以利用图结构的来抽象表达:比如社交网络,网页链接关系,用户传播网络,用户网络点击、浏览和购买行为,甚至消费者评论内容,内容分类标签,产品分类标签等等

参考

加密

GPG

1
2
3
4
5
$ brew install gpg
$ export GPG_TTY=$(tty)
$ gpg --gen-key
$ gpg --list-keys
$ git config --global user.signingkey xxx

遗传算法

参考

资源

Doc

Book

Blog

Github

Tool

欢迎加入我们的技术群,一起交流学习

人工智能 (高级)& (进阶)| BigData | 算法