Algorithm

LeetCode 组队刷题活动

组队刷 LeetCode

介绍

代码仓库

 代码仓库的坐标:asdf2014 / algorithm

报名途径

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

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

参与方式

 每位参与的小伙伴,都会获得代码仓库的 Collaborator 权限,可以自由地提交代码(不限制语种)。在 /Codes/${User} 目录下,每人都将拥有一个自己的代码库。留下 Github 名称后,将很快会收到邀请函,大家可以在 asdf2014 - algorithm - invitations 链接中认领

刷题频率

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

选题策略

 分为两个阶段:

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

其他

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

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

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

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

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

迭代解

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]

进度

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

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

经典算法

String Matching

种类

朴素算法(Naive Algorithm)
Rabin-Karp 算法
有限自动机算法(Finite Automation)
KMP

 KMP,Knuth-Morris-Pratt 匹配算法

Boyer-Moore 算法
Simon 算法
Colussi 算法
Galil-Giancarlo 算法
Apostolico-Crochemore 算法
Horspool 算法
Sunday 算法

实战

string-to-integer-atoi

正则匹配解

1
2
3
4
5
6
import re
patten = '^(([+|-]\\d+)|\\d+)'
def string_to_integer_atoi(s):
match = re.search(patten, s.strip())
res = int(match.group()) if match else 0
return max(min(res, 2 ** 31 - 1), -2 ** 31)

参考

Book
  • 《柔性字符串匹配》

Sorting Algorithm

参考

Dynamic Programming

定义

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

关键概念

状态

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

状态转移方程

 状态和状态之间的关系式

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

递推

 每个阶段只有一个状态

贪心

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

搜索

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

动态规划

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

最优子结构

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

无后效性

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

实战

longest-palindromic-substring

S(n) = $O(1)$ 解

1
2
3
4
5
6
7
8
9
10
11
12
13
def longest_palindromic_substring(s):
res = ""
for i in range(len(s)):
odd = find(s, i, i)
even = find(s, i, i + 1)
res = max(res, odd, even, key=len)
return res

def find(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]

参考

Hash

哈希冲突

开放式寻址
  • 线性探测

    从发生冲突的地址起,依次判断下一个地址是否为空,直到碰到空闲的地址

  • 直接定址法

    取关键字 $k$ 或者 $k$ 的某个线性函数值($a \cdot k + b$)作为哈希地址

  • 二次探测

    以关键字 $k$ 或者 $k$ 加上某个常数的平方($k + 1^2$、$k + 2^2$、$k + 3^2$ $\dots$)作为哈希地址

  • 伪随机数法

    采用一个伪随机数当作哈希函数

  • 双重哈希

    双重哈希是用于开放寻址最好的方法之一,散列函数如下:

    为了能查找整个散列表,值 $h_2(k)$ 需要与表的大小 $T$ 互质。为确保这一条件成立,可采用以下两种方法

    • 取 $T$ 为 2 的幂,并设计一个总产生奇数的 $h_2$
    • 取 $T$ 为质数,并设计一个总是产生较 $T$ 小的正整数的 $h_2$
关键字分析
  • 数字分析法

    提取关键字中取值比较均匀的数字作为哈希地址

  • 平方取中法

    如果关键字各个部分的分布都不均匀的话,可以先求出它的平方值,然后按照需求取中间的几位作为哈希地址

  • 分段叠加法

    按照哈希表地址位数将关键字分成位数相等的几部分,其中最后一部分可以比较短。然后将这几部分相加,舍弃最高进位后的结果,即可作为该关键字的哈希地址

冲突转移
  • 拉链法

    拉链法,又称链接地址法,是将哈希值相同的元素构成一个同义词的单链表

  • 公共溢出区

    将哈希表分为公共区和溢出区,当溢出发生时,将所有溢出数据统一写入到溢出区

实战

two-sum

T(n) = S(n) = $O(n)$ 解

1
2
3
4
5
6
7
8
9
10
11
def two_sum(nums, target):
nums_len = len(nums)
if nums_len < 1:
return False
cache = {}
for i in range(nums_len):
n = nums[i]
if n in cache:
return [cache[n], i]
else:
cache[target - n] = i

Linked List

种类

单向链表

单向链表

(图片来源:wikipedia.org,已确认无版权)
快慢指针法

 该方法常用于解决查找单向链表的中点、判断链表是否存在环等问题。大体思路便是,设计一快一慢两个指针,记做 fastslow。同时,控制 fast 的速度是 slow 的两倍(如,fast = fast.next.next; slow = slow.next)。这样,可以保证当 fast 到达链表尾部的时候,slow 刚好在链表中间

双向链表

双向链表

(图片来源:wikipedia.org,已确认无版权)
循环链表

循环链表

(图片来源:wikipedia.org,已确认无版权)

性能对比

Linked listArrayDynamic arrayBalanced treeRandom access listHashed array tree
Indexing$O(n)$$O(1)$$O(1)$$O(\log n)$$O(\log n)$$O(1)$
Insert/delete at beginning$O(1)$N/A$O(n)$$O(\log n)$$O(1)$$O(n)$
Insert/delete at end$O(1)$ when last element is known;
$O(n)$ when last element is unknown
N/A$O(1)$ amortized$O(\log n)$$O(\log n)$ updating$O(1)$ amortized
Insert/delete in middlesearch time + $O(1)$N/A$O(n)$$O(\log n)$$O(\log n)$ updating$O(n)$
Wasted space (average)$O(n)$0$O(n)$$O(n)$$O(n)$$O(\sqrt{n})$
(表格来源:wikipedia.org

种类

add-two-numbers

T(n) = $O(n)$ 解

1
2
3
4
5
6
7
8
9
10
11
12
def add_two_numbers(left, right):
carry = 0
tmp = ListNode(0)
root = tmp
while left or right:
total = carry + left.val + right.val
left = left.next
right = right.next
carry = total // 10
tmp.next = ListNode(total % 10)
tmp = tmp.next
return root.next

Sliding Window

说明

 滑动窗口算法,主要用于解决数组或者字符串的子元素问题。它可以将嵌套的循环问题,转换为单循环问题,从而降低时间复杂度

实战

longest-substring-without-repeating-characters

T(n) = S(n) = $O(n)$ 解

1
2
3
4
5
6
7
8
9
10
11
def longest_substring_without_repeating_characters(s):
begin = 0
res = 0
cache = {}
for i, c in enumerate(s):
if c in cache and begin <= cache[c]:
begin = cache[c] + 1
else:
res = max(res, i - begin + 1)
cache[c] = i
return res

Math

实战

reverse-integer

纯数学的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
def reverse_integer(x):
sign = (x > 0) - (x < 0)
x *= sign
size = len(str(x))
res = 0
for i in range(1, size + 1):
remaining = x % 10
refactor = 10 ** (size - i)
res += remaining * refactor
x //= 10
if res > 2 ** 31 - 1:
return 0
return sign * res

字符串切片

1
2
3
4
def reverse_integer(x):
sign = (x > 0) - (x < 0)
res = int(str(x * sign)[::-1])
return sign * res * (res < 2 ** 31)

预测算法

简易平均法

算术平均值

加权平均值

移动平均法

指数平滑法

参考

线性回归法

分类算法

贝叶斯(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
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

数据库相关

 二分查找(Binary Search,也称折半搜索、对数搜索),是一种在有序数组中查找某一特定元素的搜索算法

Binary Search

(图片来源:wikipedia.org,已确认无版权)
时间复杂度T(n) / S(n)
平均$O(\log n)$
最优$O(1)$
最坏$O(\log n)$
最坏迭代:$O(1)$;递归:$O(\log n)$(无尾调用消除)

二叉查找树

平衡二叉树

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

遗传算法

参考

检索

资源

Wiki

Book

Github

Tool

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

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

Benedict Jin wechat
Subscribe to my blog by scanning my public wechat account.