KMP模式匹配算法
算法复杂度O(n+m),n为S长度,m为模式串T长度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
35def get_next(T):
i = 0 # 指向主串的指针
j = -1 # 指向模式串的指针,一开始
next_val = [-1] * len(T) # 要返回的next数组
while i < len(T)-1: # next[0]=-1,只需要求后面的m-1个值即可
if j == -1 or T[i] == T[j]: # 匹配成功,相同前缀长度增加1;找不到时直接开始下一位
i += 1
j += 1
if i < len(T) and T[i] != T[j]:
next_val[i] = j
else: # 如果字符重复则跳过
next_val[i] = next_val[j]
else: # 匹配不成功则在前面的子串中继续搜索,直至找不到
j = next_val[j]
return next_val
def kmp(T, S):
# 在字符串S中匹配模式串T
next_arr = get_next(T)
s_index = 0
t_index = 0
while s_index < len(S):
if S[s_index] == T[t_index]:
s_index += 1
t_index += 1
if t_index == len(T):
return s_index-t_index
else:
if next_arr[t_index] == -1:
s_index += 1
else:
t_index = next_arr[t_index]
return -1
print(kmp("abc", "aabcdefg"))
Rabin-Karp匹配算法
利用散列值匹配,时间复杂度为O(m+n),最差为O(mn)
1 | PRIME = 72057594037927931 # < 2^{56} |
字符串的最长回文子串: Manacher 算法
以‘#’添加到字符之间,更新一个p数组,p[i]表示以i为中心的回文串最大半径,时间复杂度为O(n)
1 | def manacher(s): |
列文斯登距离
给定两个序列x和y,需要多少次增、删、改的操作,才能把x变成y?
1 | def levenshtein(x, y): |
最长公共子序列
动态规划方法,复杂度为O(mn),m和n为两个序列的长度
1 | def longest_common_subsequence(x, y): |
最长升序子序列
定义数组tmp记录当前最大升序子串(∴tmp必然升序),用tmp的末位元素对比目标序列nums[1]开始的每个元素,若当前nums元素 > tmp末位元素,当前nums元素插入tmp。否则用当前nums元素替换tmp中合理位置元素即可。
1 | // 此为O(nlog(n))方法 |
python二分查找模块1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16import bisect
L = [1,3,3,6,8,12,15]
x = 3
x_insert_point = bisect.bisect_left(L,x) #在L中查找x,x存在时返回x左侧的位置,x不存在返回应该插入的位置..这是3存在于列表中,返回左侧位置1
print x_insert_point
x_insert_point = bisect.bisect_right(L,x) #在L中查找x,x存在时返回x右侧的位置,x不存在返回应该插入的位置..这是3存在于列表中,返回右侧位置3
print x_insert_point
x_insort_left = bisect.insort_left(L,x) #将x插入到列表L中,x存在时插入在左侧
print L
x_insort_rigth = bisect.insort_right(L,x) #将x插入到列表L中,x存在时插入在右侧
霍夫曼编码
1 | import copy |
背包问题
给定 n 个权重为 p0,…, pn-1 的对象,其各自对应的值为 v0,…, vn-1,另设一个整数 C 作为背包的容量。我们希望知道如何得到一个对象值总和最大的子集,同时权重和不超过 C。这是一个 NP复杂问题
动态规划:
dp[i][j] 表示前i个对象在j作为最大容量下的最大值的总和
找零问题
各种面值的硬币,要求组成一个给定的钱数,且硬币数目最少
- 如果硬币面值类似:1,2,5,10,20,50,100。这种题可以用贪心来做,因为前n-1项的和都不超过第n项的值,所以符合贪心的规则。
- 如果硬币面值类似:1,2,4,5,10。此时则不可以用贪心算法,而是应该用动态规划。因为此时前n-1项之和不再小于第n项的值,所以贪心不再成立。
1 |
|
给定总和值的子集
给定 n 个正整数 x0,…, xn-1,我们希望知道是否存在一个整数和等于给定值 R 的子集
动态规划:维护一个bool 数组,dp[i]表示是否存在由x0,…,xi中元素组成的子集之和为R
1 | def subset_sum(x, R): |
当R很大n很小的时候,动态规划效率低下,复杂度为O(2^(n/2))的算法:
我们把输入 X = {x0,…, xn-1} 切分成两个不相交的部
分 A 和 B,两部分最大为 [n/2]。如果 SA(SB)是 A(B)每个子集元素的总和,我们建立一个集合 Υ = SA 和集合Z = R - SB,两者包含着R - v 数值对,其中v描述了SB。我们只需测试Υ和Z是 否有一个非空交集。
最大公约数
辗转相除法
1 | def pgcd(a, b): |
计算素数
1 | def eratosthene(n): |
约瑟夫环
约瑟夫问题是个著名的问题:N个人围成一圈,第一个人从1开始报数,报M的将被杀掉,下一个人接从1开始报。如此反复,最后剩下一个,求最后的胜利者。
例如只有三个人,把他们叫做A、B、C,他们围成一圈,从A开始报数,假设报2的人被杀掉。
递推公式f(N, M) = (f(N-1, M) + M) % N
1 | int cir(int n,int m) |
排序
原地排序:就是指在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序(冒泡,选择,插入,希尔,快排,堆排)
稳定排序:能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同(冒泡,插入,归并,基数)
受限玻尔兹曼机(RBM)
RBM的训练,实际上是求出一个最能产生训练样本的概率分布。也就是说,要求一个分布,在这个分布里,训练样本的概率最大。可以理解为最大似然函数
链接:https://www.jianshu.com/p/2e7ffe06fcdd?tdsourcetag=s_pcqq_aiomsg
深度玻尔兹曼机(DBM)和深度置信网络(DBN) https://cloud.tencent.com/developer/news/240089