Algorithm

LeetCode 组队刷题活动

组队刷 LeetCode

介绍

代码仓库

 代码仓库的坐标:asdf2014 / algorithm

报名途径

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

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

参与方式

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

1
2
# 一键完成您的第一次代码提交
bash -c "$(curl -L https://raw.githubusercontent.com/asdf2014/algorithm/master/first_commit.sh)"

刷题频率

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

选题策略

 分为两个阶段:

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

其他

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

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

 同时,为了大家更加方便地交流,也欢迎加入算法 QQ 群 或者 Gitter 聊天室

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

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

迭代解

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]

进度

 截止目前为止,活跃的小伙伴数量:,已刷题:,覆盖的算法种类:,使用到的语言种类:,代码提交频率:,开源许可证:

排行榜

完成题目最多的小伙伴

最活跃的小伙伴

UserLatest Active Date
BlitheLou2019-11-13 09:18:54
BoCai2019-11-12 19:06:19
GinRyan2019-11-11 04:51:21
zsdostar2019-11-05 18:15:06
gracekoo2019-11-05 18:15:06
asdf20142019-10-24 10:43:01
P_fzr2019-10-24 10:43:01
gmywq3922019-10-14 15:57:26
fengxuanmo2019-09-20 18:40:10
lxycg2019-08-30 13:04:39
下文将总结归纳大家讨论交流的内容,不断地沉淀解题过程中思考的点滴

基础概念

复杂度

Complexity

(图片来源:wikipedia.org,已确认版权为 CC BY-SA 4.0 协议)
名称运行时间运行时间举例算法举例
常数时间$O(1)$10判断一个二进制数的奇偶
反阿克曼时间$O(\alpha (n))$并查集的单个操作的平摊时间
迭代对数时间$O(\log ^{\ast}n)$分布式圆环着色问题
对数对数时间$O(\log \log n)$有界优先队列的单个操作
对数时间$O(\log n)$$\log n$,$\log n^{2}$二分搜索
幂对数时间$(\log n)^{O(1)}$$(\log n)^{2}$
幂时间(小于 1 次)$O(n^{c})$,$0<c<1$$n^{\frac {1}{2}}$,$n^{\frac {2}{3}}$K-d 树的搜索操作
线性时间$O(n)$$n$无序数组的搜索
线性迭代对数时间$O(n\log ^ {\ast}n)$莱姆德·赛德尔的三角分割多边形算法
线性对数时间$O(n\log n)$$n\log n$最快的比较排序
二次时间$O(n^{2})$$n^{2}$冒泡排序、插入排序
三次时间$O(n^{3})$$n^{3}$矩阵乘法的基本实现
多项式时间$2^{O(\log n)}=n^{O(1)}$$n$,$n\log n$,$n^{10}$线性规划中的卡马卡算法,AKS 质数测试
准多项式时间$2^{(\log n)^{O(1)}}$关于有向斯坦纳树问题最著名的 $O(\log ^{2}n)$ 近似算法
次指数时间(第一定义)$O(2^{n^{\epsilon }})$,ε > 0$O(2^{(\log n)^{\log \log n}})$假设复杂性理论推测,BPP 包含在 SUBEXP 中
次指数时间(第二定义)$2^{o(n)}$$2^{n^{\frac1{3}}}$用于整数分解与图形同构问题的著名算法
指数时间$2^{O(n)}$$1.1^n$,$10^n$使用动态规划解决旅行推销员问题
阶乘时间$O(O!)$$n!$通过暴力搜索解决旅行推销员问题
指数时间$2^{poly(n)}$$2^n, 2^{n^2}$
双重指数时间$2^{2^{poly(n)}}$$2^{2^n}$在预膨胀算术中决定一个给定描述的真实性
(表格来源:wikipedia.org

经典算法

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)
palindrome-number

纯数学的方式

1
2
3
4
5
6
7
8
9
10
def palindrome_number(x):
if x < 0:
return False
elif x == 0:
return True
h, rev = x, 0
while h:
rev = rev * 10 + h % 10
h //= 10
return rev == x

字符串反转

1
2
def palindrome_number(x):
return x == 0 or (x > 0) and int(str(x)[::-1]) == x
roman-to-integer

纯数学的方式

1
2
3
4
5
6
7
8
9
10
11
12
d = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
def roman_to_integer(s):
res = 0
high = -1
for c in reversed(s):
now = d[c]
if now < high:
res -= now
else:
res += now
high = max(high, now)
return res

字符串替换

1
2
3
4
5
6
7
8
9
d = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
def roman_to_integer(s):
res = 0
s = s.replace("IV", "IIII").replace("IX", "VIIII")
s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
s = s.replace("CD", "CCCC").replace("CM", "DCCCC")
for c in s:
res += d[c]
return res
3sum

基于 2sum 的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def sum3(nums):
if len(nums) < 3:
return []
nums.sort()
res = []
for k, v in enumerate(nums[:-2]):
if k >= 1 and v == nums[k - 1]:
continue
cache = {}
for n in nums[k + 1:]:
if n not in cache:
cache[-v - n] = 1
else:
tmp = [v, -v - n, n]
if tmp not in res:
res += [tmp]
return res

预测算法

简易平均法

算术平均值

加权平均值

移动平均法

指数平滑法

参考

线性回归法

分类算法

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

  • 感知机追求最大程度正确划分,最小化错误,但相对容易造成过拟合
  • 支持向量机追求在大致正确分类的同时,最大化 margin,一定程度上避免了过拟合。但是由于 SVM 是借助二次规划来求解支持向量,而求解二次规划将涉及 m 阶矩阵的计算(m 为样本的个数),所以当 m 数目很大时,该矩阵的存储和计算将耗费大量的机器资源和运算时间

聚类算法

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

遗传算法

参考

人工智能

 详见,我的另一篇博客《人工智能

检索

序号标题分类
1Two SumHash
2Add Two NumbersLinked List
3Longest Substring Without Repeating CharactersSliding Window
4Median of Two Sorted ArraysBinary Search
5Longest Palindromic SubstringDynamic Programming
6ZigZag ConversionString
7Reverse IntegerMath
8String to Integer (atoi)Math & String
9Palindrome NumberMath
10Regular Expression MatchingString & Dynamic Programming & Backtracking
11Container With Most WaterArray & Two Pointers
12Integer to RomanMath & String
13Roman to IntegerMath & String
14Longest Common PrefixString
153SumArray & Two Pointers
163Sum ClosestArray & Two Pointers

资源

Wiki

Book

Github

Tool

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

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

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