算法题笔记

发表于 | 更新于 | 评论数： | 阅读次数：

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
35
def 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
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
PRIME = 72057594037927931 # < 2^{56} 
DOMAIN = 128
def roll_hash(old_val, out_digit, in_digit, last_pos):
    val = (old_val - out_digit * last_pos + DOMAIN * PRIME) % PRIME 
    val = (val * DOMAIN) % PRIME
    return(val + in_digit) % PRIME

def matches(s, t, i, j, k): 
    for d in range(k):
        if s[i + d] != t[j + d]: 
            return False
    return True

def rabin_karp_matching(s, t): 
    hash_s = 0
    hash_t = 0
    len_s = len(s)
    len_t = len(t)
    last_pos = pow(DOMAIN, len_t - 1) % PRIME 
    if len_s < len_t :
        return -1
    for i in range(len_t): # 预计算
        hash_s = (DOMAIN * hash_s + ord(s[i])) % PRIME
        hash_t = (DOMAIN * hash_t + ord(t[i])) % PRIME 
    for i in range(len_s - len_t + 1):
        if hash_s == hash_t : # 逐个比较字符 if matches(s, t, i, 0, len_t):
            return i
        if i < len_s - len_t:
            hash_s = roll_hash(hash_s, ord(s[i]), ord(s[i+len_t]), last_pos) 
    return -1

print(rabin_karp_matching("abcdefg", "ef"))

字符串的最长回文子串: Manacher 算法

以‘#’添加到字符之间，更新一个p数组，p[i]表示以i为中心的回文串最大半径，时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def manacher(s):
    assert '$' not in s and '^' not in s and '#' not in s 
    if s == "":
        return(0, 1)
    t = "^#" + "#".join(s) + "#$" 
    c = 0
    d = 0
    p = [0] * len(t)
    for i in range(1, len(t) - 1):
    # -- 相对于中心 c 翻转下标 i 
        mirror = 2 * c - i # = c - (i-c)
        p[i] = max(0, min(d - i, p[mirror]))
    # -- 增加以 i 为中心的回文子串的长度 
        while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
            p[i] += 1 
        #-- 必要时调整中心点 
        if i + p[i] > d:
            c = i
            d = i + p[i]
    (k, i) = max((p[i], i) for i in range(1, len(t) - 1)) 
    return((i - k) // 2, (i + k) // 2) # 输出结果上下界

print(manacher("13abbacdg"))

列文斯登距离

给定两个序列x和y，需要多少次增、删、改的操作，才能把x变成y？

1
2
3
4
5
6
7
8
9
10
11
def levenshtein(x, y): 
    n = len(x)
    m = len(y)
    # 初始化第0行和第0列
    A = [[i + j for j in range(m + 1)] for i in range(n + 1)] 
    for i in range(n):
        for j in range(m):
            A[i + 1][j + 1] = min(A[i][j + 1] + 1, A[i+1][j]+1, A[i][j]+int(x[i]!=y[j])) # 插入 # 删除 # 替换  
    return A[n][m]

print(levenshtein("abc1", "a2"))

最长公共子序列

动态规划方法，复杂度为O(mn)，m和n为两个序列的长度

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
def longest_common_subsequence(x, y): 
    n = len(x)
    m = len(y)
# -- 计算最优长度
    A = [[0 for j in range(m + 1)]  for i in range(n + 1)] 
    for i in range(n):
        for j in range(m): 
            if x[i] == y[j]:
                A[i + 1][j + 1] = A[i][j] + 1
            else:
                A[i + 1][j + 1] = max(A[i][j + 1], A[i + 1][j]) # -- 输出结果
    # 找出最长的子串字符
    sol = []
    i, j = n, m
    while A[i][j] > 0:
        if A[i][j] == A[i - 1][j]: 
            i -= 1
        elif A[i][j] == A[i][j - 1]: 
            j -= 1
        else: 
            i-= 1
            j -= 1
            sol.append(x[i]) 
    return ''.join(sol[::-1])
        # 列表反转

print(longest_common_subsequence("abdcadvbbc", "abdecbab"))

最长升序子序列

定义数组tmp记录当前最大升序子串（∴tmp必然升序），用tmp的末位元素对比目标序列nums[1]开始的每个元素，若当前nums元素 > tmp末位元素，当前nums元素插入tmp。否则用当前nums元素替换tmp中合理位置元素即可。

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
// 此为O(nlog(n))方法
int lengthOfLIS_02(int* nums, int numsSize) {
    // 长度若为0或1，无须比较直接返回
    if (numsSize < 2) {
        return numsSize;
    }
    // 声明临时数组，赋值首元素，当前lenght = 1
    int tmp[numsSize], position;
//    printf("OriginalArray:");
//    printArray(nums, numsSize);
//    // 此for循环只是为了log美观 无意义
//    for (int i =0; i < numsSize; i++) {
//        tmp[i] = 0;
//    }
    tmp[0] = nums[0];
    int length = 1;
    // 遍历nums[1]~nums[numsSize-1]
    for (int i = 1; i < numsSize; i++) {
        // 若当前nums元素 > tmp最大元素，插入tmp，length++
        if (nums[i] > tmp[length - 1]) {
            tmp[length] = nums[i];
            length++;
//            printf("Part-A i=%2d len=%2d Arr:", i, length);
        } else {
            // 二分定位 用当前nums元素 替换 tmp中合理位置元素
            position = binarySearch(tmp, length, nums[i]);
            tmp[position] = nums[i];
//            printf("Part-B i=%2d pos=%2d Arr:", i, position);
        }
//        printArray(tmp, numsSize);
    }
//    printf("Finished\n");
//    printArray(tmp, numsSize);
    return length;
}

python二分查找模块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import 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存在于列表中，返回左侧位置１
print x_insert_point
 
x_insert_point = bisect.bisect_right(L,x)  #在L中查找x，x存在时返回x右侧的位置，x不存在返回应该插入的位置..这是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
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import copy

class Node:
    def __init__(self, name, weight):
        self.name = name #节点名
        self.weight = weight #节点权重
        self.left = None #节点左孩子
        self.right = None #节点右孩子
        self.father = None # 节点父节点
    #判断是否是左孩子
    def is_left_child(self):
        return self.father.left == self

#创建最初的叶子节点
def create_prim_nodes(data_set, labels):
    if(len(data_set) != len(labels)):
        raise Exception('数据和标签不匹配!')
    nodes = []
    for i in range(len(labels)):
        nodes.append( Node(labels[i],data_set[i]) )
    return nodes


# 创建huffman树
def create_HF_tree(nodes):
    #此处注意，copy()属于浅拷贝，只拷贝最外层元素，内层嵌套元素则通过引用，而不是独立分配内存
    tree_nodes = nodes.copy() 
    while len(tree_nodes) > 1: #只剩根节点时，退出循环
        tree_nodes.sort(key=lambda node: node.weight)#升序排列
        new_left = tree_nodes.pop(0)
        new_right = tree_nodes.pop(0)
        new_node = Node(None, (new_left.weight + new_right.weight))
        new_node.left = new_left
        new_node.right = new_right
        new_left.father = new_right.father = new_node
        tree_nodes.append(new_node)
    tree_nodes[0].father = None #根节点父亲为None
    return tree_nodes[0] #返回根节点

#获取huffman编码
def get_huffman_code(nodes):
    codes = {}
    for node in nodes:
        code=''
        name = node.name
        while node.father != None:
            if node.is_left_child():
                code = '0' + code
            else:
                code = '1' + code
            node = node.father
        codes[name] = code
    return codes


if __name__ == '__main__':
    labels = ['a','b','c','d','e','f']
    data_set = [9,12,6,3,5,15]
    nodes = create_prim_nodes(data_set,labels)#创建初始叶子节点
    root = create_HF_tree(nodes)#创建huffman树
    codes = get_huffman_code(nodes)#获取huffman编码
    #打印huffman码
    for key in codes.keys():
        print(key,': ',codes[key])

背包问题

给定 n 个权重为 p0,…, pn-1 的对象，其各自对应的值为 v0,…, vn-1，另设一个整数 C 作为背包的容量。我们希望知道如何得到一个对象值总和最大的子集，同时权重和不超过 C。这是一个 NP复杂问题

动态规划：
dp[i][j] 表示前i个对象在j作为最大容量下的最大值的总和

找零问题

各种面值的硬币，要求组成一个给定的钱数，且硬币数目最少

  1. 如果硬币面值类似：1,2,5,10,20,50,100。这种题可以用贪心来做，因为前n-1项的和都不超过第n项的值，所以符合贪心的规则。
  2. 如果硬币面值类似：1,2,4,5,10。此时则不可以用贪心算法，而是应该用动态规划。因为此时前n-1项之和不再小于第n项的值，所以贪心不再成立。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int main(){
	vector<int>v={1,2,4,5,10};
	int n;
	cin >> n;
	int a[n+1];
	for(int i = 0; i <= n; i++){
		a[i] = i;//初始化为i。任意金额都可以由一元组成
	}
	for(int i = 0; i < v.size(); i++){
		a[v[i]]= 1;//如果当前金额为现有货币币种，那一张就够。
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < v.size(); j++){
			if(v[j] > i)continue;
			a[i] = min(a[i], a[i-v[j]] + 1);//当前金额i是否可以通过一张面额为v[j]的币种和金额为i-v[j]的数量组成更小的张数。
		}
	}
	cout << a[n] << endl;
}

给定总和值的子集

给定 n 个正整数 x0,…, xn-1，我们希望知道是否存在一个整数和等于给定值 R 的子集

动态规划：维护一个bool 数组，dp[i]表示是否存在由x0,…,xi中元素组成的子集之和为R

1
2
3
4
5
6
7
def subset_sum(x, R):
    b = [False] * (R + 1) 
    b[0] = True
    for xi in x:
        for s in range(R, xi - 1, -1): 
        b[s] |= b[s - xi]
    return b[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
2
def pgcd(a, b)：
    return a if b == 0 else pgcd(b, a%b)

计算素数

1
2
3
4
5
6
7
8
9
def eratosthene(n): 
    P = [True] * n
    answ = [2]
    for i in range(3, n, 2):
        if P[i]: 
            answ.append(i)
            for j in range(2 * i, n, i): 
                P[j] = False
    return answ

约瑟夫环

约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接从1开始报。如此反复，最后剩下一个，求最后的胜利者。

例如只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。

递推公式f(N, M) = (f(N-1, M) + M) % N

1
2
3
4
5
6
7
8
9
int cir(int n,int m)
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
        p=(p+m)%i;
    }
    return p+1;
}

排序

原地排序：就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序（冒泡，选择，插入，希尔，快排，堆排）

稳定排序：能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同（冒泡，插入，归并，基数）

受限玻尔兹曼机（RBM）

RBM的训练，实际上是求出一个最能产生训练样本的概率分布。也就是说，要求一个分布，在这个分布里，训练样本的概率最大。可以理解为最大似然函数

链接：https://www.jianshu.com/p/2e7ffe06fcdd?tdsourcetag=s_pcqq_aiomsg

深度玻尔兹曼机（DBM）和深度置信网络（DBN） https://cloud.tencent.com/developer/news/240089

Thank you for every coin~